Keshav K. PingaliAssociate Professor PhD MIT, 1986My research group works on programming languages and compilers for high-performance architectures. Our goal is to develop the algorithms and tools that are required to generate efficient code for programs in a variety of application areas including scientific and engineering simulations. Currently, our focus is on dense and sparse matrix computations, since these are the most time-consuming parts of most simulations. |
 |
Our most recent work is on the theory and implementation of restructuring techniques for sparse matrix computations. We have developed new technology based on relational algebra techniques for compiling efficient code for these programs, and we have implemented this technology in the Bernoulli compiler. We are evaluating
this technology on the IBM SP-2 at the Cornell Theory Center. Exploiting locality is a key to obtaining good performance, even on modern uniprocessors. The compiler community has developed a number of techniques for restructuring programs to enhance locality, but the code they produce cannot compete with hand-optimized code in libraries like LAPACK. Our radical new approach, called data-centric transformation, addresses this problem. This technology is being incorporated into SGI's compiler product line.
These projects build on our earlier work on restructuring compilation technology. Our group implemented one of the first compilers that generated code for distributed memory machines, starting from sequential shared memory programs. We introduced techniques called runtime resolution and owner-computes-rule, which have now become standard in the area. Our work on linear loop transformations for enhancing parallelism and locality has been incorporated by Hewlett-Packard into its entire compiler product line. We also developed fast algorithms for program analysis problems such as computing the control dependence relation, the static single assignment form of a program, and dataflow analyses. Many of these algorithms have been incorporated into commercial and research compilers.
University Activities
Computing Policy Committee
Cornell Theory Center Computing Allocation Committee
Computer Science Graduate Admissions Committee
Professional Activities
Program Committee: 1998 Parallel Architectures and Compilation Techniques (PACT) Conf.; Int. Parallel Processing Symp. (IPPS), 1998
Consultant: Hewlett-Packard Labs, Intel Corp.
Referee/Reviewer: ACM TOPLAS, IEEE Trans. Computers, J. Parallel and Distributed Computing, J. Supercomputing, IEEE Computer, Software Practice and Experience
Editorial Board: Int. J. Parallel Programming
Lectures
Data-centric compilation: a new approach to program restructuring. Computer Science, MIT, Jan. 1998.
___. Computer Science, Univ. Delaware, Oct. 1997.
___.Computer Science, UC Santa Barbara, Nov. 1997.
___. Distinguished Lecturer Series, Computer Science, Univ. Illinois, Urbana-Champaign, Nov. 1997.
A relational approach to sparse matrix compilation. Computer Science, Univ. Versailles, France, July 1997.
___. Computer Science, Leiden Univ., Leiden, Holland, July 1997.
Compiler and run-time support for semi-structured applications. Int. Conf. Supercomputing, Vienna, Austria, July 1997.
Publications
Compiling parallel code for sparse matrix applications. Proc. ACM/IEEE SC '97 Conf., San Jose, CA (Nov. 1997) (with V. Kotlyar and P. Stodghill). Nominated for Best Student Paper Award.
A relational approach to the compilation of sparse matrix programs. Proc. Euro-Par (Aug. 1997), 318-327 (with V. Kotlyar and P. Stodghill).
Sparse code generation for imperfectly nested loops with dependences. Proc. 1997 Int. Conf. Supercomputing, Vienna, Austria (July 1997), 188-195 (with V. Kotlyar).
Compiler and run-time support for irregular and adaptive applications. Proc. Int. Conf. Supercomputing (July 1997), 229-236, Vienna, Austria (with N. Chrisochoides and I. Kodukula).