Concurrent Data-flow Analysis

The Static Single Assignment (SSA) form of programs is a popular intermediate representation of sequential programs that is widely used in optimizing compilers. A more general version of this form, called the Sparse Data-flow Evaluator Graph (SDEG) can be used to solve many data-flow problems efficiently. Both the SSA form and the SDEG can be computed very efficiently using the optimal solution to the Roman Chariots Problem given by Bilardi and Pingali.

One limitation of the traditional formulation of SSA is that it only models sequential programs. Programs with explicit parallelism (e.g., Java, which has thread), cannot be safely modeled with this formulation.

Some work has been done on what is called Concurrent SSA. However, the particular formulation of Concurrent SSA found in the referenced paper does not incorporate the ideas from SDEG's or the optimal algorithm for computing SSA.

The goal of this project is to merge all of these threads of research into a new Concurrent SDEG representation, which

Can be used to model Java programs, like Concurrent SSA,
Can be used for many different optimization algorithms, like the sequential SDEG's, and
Can be computed optimally using the Roman Chariots algorithm.

Also, you must,

Implement your new algorithm for computing Concurrent SDEG's,
Implement several "Dragon Book" style optimizations (e.g., constant propagation, dead-code elimination, partial-redundant code elimination) on top of your Concurrent SDEG's, and
using your system, measure the benefits of this approach for several threaded Java applications.

References

You can find some relevant papers here.

Paul Stodghill

Last modified: Mon Feb 8 21:36:47 EST 1999