1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)


Keshav K. Pingali

Professor
pingali@cs.cornell.edu
http://www.cs.cornell.edu/home/pingali/pingali.html

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. 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 has been 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. 

We also participate in a large multi-disciplinary project concerned with fracture simulation on parallel computers. Other researchers working in this project are Tony Ingraffea (Civil Engineering), Steve Vavasis, Gao Guong-Rong (CS, Delaware), Nikos Chrisochoides (CS, Notre Dame), Paul Chew and Paul Stodghill. This group is developing guaranteed-quality parallel mesh
generators, new preconditioners for sparse linear systems solvers, sparse matrix compilation techniques, and multi-threaded runtime systems. 

University Activities  
  • Computing Policy Committee  
  • Cornell Theory Center Computing Allocation Committee 
Professional Activities  
  • Program Committee: 1999 ACM Conference on Principles and Practice of Parallel
    Programming (PPoPP 99);  1999 6th International Symposium on Solving Irregularly Structured Problems in Parallel ann (Irregular 99); 1998 High-Performance Parallel
    Computing (HiPC98); 1998 International Parallel Processing Symposium (IPPS98). 
  • Consultant: Silicon Graphics Inc.  
  • Referee/Reviewer: ACM TOPLAS, IEEE Trans. Computers, Journal Parallel and Distributed Computing, Journal Supercomputing, IEEE Computer, Software Practice and Experience  Editorial Board: Int. Journal Parallel Programming, Discrete Mathematics and Theoretical Computer Science
Lectures 
  • Automatic blocking. Dagstuhl Workshop on Tiling for Resource Management, Dagstuhl, Germany, Aug 1998.  
  • Data-centric compilation: a new approach to program restructuring. Keynote address,
    1998 International Conference on Advanced Computing (ADCOM98), Dec. 1998.  
  • —. Keynote address, High-Performance Parallel Computing '98 (HiPC98), Chennai, India, Dec. 1998.   
  • —. Computer Science, Brown Univ., Feb. 1999.  
  • —. Computer Science, Univ. of Illinois, Urbana Champaign, Mar. 1999.  
  • An experimental evaluation of tiling and shackling for memory hierarchy management.
    International Conference on Supercomputing (ICS99), Greece, June 1999. 
Publications 
  • Parallel and vector languages. Encyclopedia of Electrical and Electronics Engineering (John Webster, ed.), John Wiley (1998), 592-603.  
  • High-level semantic optimization of numerical codes. 1999 ACM International Conference on Supercomputing (ICS) (June 1999), 301-311 (with V. Menon). 
  • An experimental evaluation of tiling and shackling for memory hierarchy management. 1999
    ACM International Conference on Supercomputing (ICS)     (June 1999), 363-371, (with I.
    Kodukula, D. Maydan, and R. Cox).