Data-centric Program Restructuring

Keshav Pingali
Cornell University, Ithaca

Modern high-performance machines have deep memory hierarchies, and optimizing the flow of data through the memory hierarchy usually has a dramatic impact on program performance. Unfortunately, memory hierarchies complicate the programming model enormously (for example, arrays cannot be treated as though they were random-access data structures). Carefully hand-coded libraries, such as the LAPACK library for dense numerical linear algebra, are one solution, but the utility of a library is limited to the particular problem domain for which it was developed.

In a quest for general-purpose tools, the compiler community has explored the use of program transformations like tiling (preceded by linear loop transformations) to optimize programs for memory hierarchies. However, performance improvements from tiling may be quite limited even for relatively simple codes like Cholesky factorization.

We have developed a new approach to program transformation called "data-centric program restructuring", one application of which is the optimization of programs for memory hierarchies. In this talk, we will discuss this technology and present performance numbers obtained on SGI's Octane workstations which show the performance advantages of data-centric restructuring over tiling. A practical consequence of this work is that our data-centric approach to optimizing programs for memory hierarchies is being incorporated into SGI's compiler product line.

Further info and related paper(s):

• send mail to Keshav
• click here for transparencies.