TUNE: System Support for Memory-Friendly Programming

Principal Investigator: Siddhartha Chatterjee
Funding Agency: Duke University (Indirect National Science Foundation)
Agency Number: 98-SC-NSF-1016

Abstract
The widespread use of memory hierarchies in microprocessor-based machines forces many application programmers to manually restructure their codes to improve memory system performance. Unfortunately, many restructuring techniques are complicated, making them difficult to implement in sophisticated programs and reducing program readability and maintainability.

This project seeks to develop a system to aid (and automate when possible) the writing of portable memory-friendly programs. We plan to develop programming language extensions that allow the user or system to restructure computation sequencing and/or data layout for improved memory hierarchy performance. To obtain an accurate estimate of a particular transformations benefit we plan to utilize analytic models, simulation, and real execution time. In particular, we will develop new analytic models based on discrete-time Markov chains that can be incorporated into our automated system.

Our primary application domain is divide-and-conquer scientific computations, including N-body codes (e.g., fast-multipole) and many linear algebra kernels (e.g., Strassen's matrix multiply). For these applications, transformations must adhere to user-specified constraints, such as numerical stability. Therefore, we will investigate developing new algorithms that enable memory-friendly transformations while satisfying specified numerical criteria.

The final component of this project investigates techniques for extracting information from the program, when applying a transformation, that can be used in conjunction with new architectural mechanisms for managing the memory hierarchy (e.g. replacement decisions in a set-associative cache).