Keshav K. Pingali
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
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.
Computing Policy Committee
Cornell Theory Center Computing Allocation
Computer Science Graduate Admissions Committee
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.
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).