Keshav K. Pingali
Associate Professor
Ph.D. MIT, 1986

My research group works in programming languages and compilers for high-perfor-mance architectures.

In the Bernoulli project, we are implementing a system that will permit scientists and engineers to prototype simulations rapidly by using high-level abstractions, without giving up code efficiency. We are targeting simulations that can be posed as systems of differential equations. These systems are usually solved numerically using techniques like the finite-element method that reduce the problem of solving differential equations to the problem of solving large systems of equations. Since most of the computational time is spent in solving equations, our system focuses on compiling high-performance, parallel code for these solvers. The difficulty is the need to deal with sparse matrices. Existing restructuring compiler technology has been developed for codes that access dense matrices in regular ways, in which all array subscripts are simple linear functions of loop induction variables. Since sparse matrices are stored in special formats, sparse array subscripts cannot be analyzed by standard compiler technology. We cut this Gordian knot by giving the compiler high-level descriptions of solver algorithms, together with information about the sparsity structure of matrices. Using an arsenal of techniques from a variety of areas ranging from integer linear programming to relational query optimization, our compiler generates parallel code customized to exploit the sparsity of data structures in the problem. Currently, our target is the 512-processor IBM SP-2 at the Cornell Theory Center.

Another aspect of the Bernoulli project is runtime support for adaptive scientific computations. Many problems, such as the simulation of shock wave propagation, require solution methods whose computational requirements are dynamic and cannot be predicted statically by the compiler. To run well on parallel machines, efficient communication and dynamic load balancing are essential. Our work in this area is being performed as part of the PORTS consortium effort to develop portable runtime systems.

The Bernoulli project builds on our earlier work on restructuring compilation techniques for dense matrix programs. Our group implemented one of the first compilers that generated code for distributed memory machines, from sequential shared memory programs. This research introduced techniques called runtime resolution and owner-computes-rule, which have now become standard tools of the trade. Our work on linear loop transformations was incorporated by a major workstation manufacturer into its entire compiler product line. We also developed fast algorithms for program analysis problems such as the control dependence relation, the static single assignment form of a program, and sparse dataflow analyses, which have been incorporated into a number of commercial and research compilers.

University Activities

Professional Activities



Return to:
1995-1996 Annual Report Home Page
Departmental Home Page

If you have questions or comments please contact:

Last modified: 2 November 1996 by Denise Moore (