• Parallelizing Irregular Applications
• Lonestar Benchmark Suite

• Compiling for Distributed Memory Computers
• Control Dependence Computation
• Empirical Optimization
• Fault Tolerance
• Fractal Symbolic Analysis
• Functional Languages with Logic Variables
• Memory Hierarchy Optimizations
• Model Checking for Hierarchical State Machines
• Program Representation
• Static Single Assignment Form
• Synthesis of Irregular Codes
• Web Services for Distributed Scientific Computing

Program Representation

Compilers use a variety of intermediate representations of programs, such as abstract syntax trees, control flow graphs, and def-use chains etc. Most of these representations were developed in the context of traditional optimizing compilers, and are not adequate for complex program manipulation problems such as slicing. The program dependence graph (PDG) can be used for these purposes, but it is difficult to use the PDG directly to prove the correctness of analysis and restructuring algorithms because the PDG does not have a formal semantics.

To overcome these problems, we developed a representation called the dependence flow graph (DFG) which is an intermediate program representation unifying control flow and dataflow. The DFG has a precise operational semantics based on the dataflow model of computation, so it can be used to perform provably correct program manipulations.

Here are some people who use DFGs.

• Kemal Ebcioglu's VLIW group at IBM Yorktown Heights uses DFGs as the intermediate language for their VLIW compiler.
• Miriam Leeser at Northeastern University uses DFGs in design tools for performing high-level logic synthesis.

Publications:

• Richard Johnson Efficient Program Analysis using Dependence Flow Graphs Cornell Computer Science Department PhD Thesis, 08/01/1994
• Richard Johnson, Wei Li, and Keshav Pingali An Executable Representation of Distance and Direction Languages and Compilers for Parallel Computing, 08/01/1991
• Micah Beck, Richard Johnson, and Keshav Pingali From Control Flow to Dataflow Journal of Parallel and Distributed Computing ?, 03/16/1991
• Keshav Pingali, Micah Beck, Richard Johnson, Mayan Moudgill, and Paul Stodghill Dependence Flow Graphs: An Algebraic Approach to Program Dependencies Principles of Programming Languages, 01/01/1991
• Micah Beck and Keshav Pingali From Control Flow to Dataflow International Conference on Parallel Processing, 08/01/1990
• Keshav Pingali, Micah Beck, Richard Johnson, Mayan Moudgill, and Paul Stodghill Dependence Flow Graphs: An Algebraic Approach to Program Dependencies Languages and Compilers for Parallel Computing, 01/01/1990