ALGORITHMS: Performance Programming for Advanced Cache Architectures

University Of Southern California, Los Angeles CA

Investigators

Abstract

The recognition of drawbacks of traditional cache hierarchies, especially for irregular applications, has led to the emergence of a new breed of processors that allow the cache hierarchy to be directly manipulated at the application level. Based on the knowledge of the application's data access behavior, "intelligent" programming can lead to dramatic performance improvements. This project will explore a new approach towards performance programming for advanced cache architectures, based on explicit memory hierarchy management at the application level. Our research will focus on: (i) Definition of a generalized model for split spatial/temporal caches and explicit cache control. This model will abstract available architecture features from a programmer's perspective. A high-level simulator based on this model will be implemented. (ii) Develop cache cognizant algorithms for regular and irregular application kernels. The kernels will be optimized to exploit spatial and temporal cache structures, data prefetch, and other features abstracted in the model. Performance improvements will be validated through low-level simulations and experiments on real architecture platforms such as Intel IA-64 and Sun UltraSPARC III Cu. (iii) Create a mathematical foundation for compile-time data placement in main memory to minimize cache misses at run time, using on Perfect Latin Squares (PLS) to reduce cache conflicts. (iv) Use the above techniques to optimize performance of algorithms used for database storage and access (search), tree traversal, unstructured mesh computations, and graph problems. We envision that our research will complement the ongoing advances in cache architectures and lead to the creation of a new computation model for programming the next generation of general-purpose processors.