Mathematical Models and Transformations of Memory-Friendly Programming

Principal Investigator: Siddhartha Chatterjee
Funding Agency: Duke University (Indirect Defense Advanced Research Projects Agency) 
Agency Number: 98-SC-DARPA-1024

Abstract
The pervasive use of multi-level memory hierarchies in modern computers makes the performance of an application primarily determined by and extremely sensitive to its memory mapping, and requires "memory-friendly" programming: careful layout of data structures and restructuring of code and data access patterns to improve locality. Techniques for improving memory system performance manifest themselves at various levels, from high-level algorithms and data structures, through compile-time analysis and restructuring of programs, to special architectural primitives that allow an application to better manage the memory hierarchy. The lack of automatic tools for improving locality currently forces many application programmers to manually restructure their codes. Unfortunately, the sophisticated algorithms seen in modern scientific computing require equally sophisticated restructuring techniques. These techniques require expertise in computer architecture, burden the programmer with tedious machine-specific details unrelated to program correctness, and reduce the readability, maintainability, and portability of the restructured code. For all these reasons, manual restructuring of programs of any significant size is untenable, and some kind of system support is necessary. This project seeks to develop mathematical models and transformations for representing and manipulating locality for hierarchical tree-structured codes (such as fast n-body solvers) running on current and future computing platforms.