faculty.gif (20410 bytes)
choices.gif (4488 bytes)

Keshav K. Pingali

Associate Professor

PhD MIT, 1986

My 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.

pingali.tif (273798 bytes)

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


  • 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.


  • 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).