ALGORITHMS: Performance Programming for Advanced Cache Architectures

认识到传统缓存层次结构的缺点，特别是对于不规则应用程序，导致出现了一种新的处理器，它允许在应用程序级别直接操作缓存层次结构。基于对应用程序数据访问行为的了解，“智能”编程可以显著提高性能。该项目将探索一种基于应用程序级别显式内存层次管理的高级缓存架构的性能编程新方法。我们的研究将集中在：(i)定义一个用于分割空间/时间缓存和显式缓存控制的广义模型。这个模型将从程序员的角度抽象出可用的体系结构特性。在此基础上实现了一个高级仿真器。（ii）为常规和不规则应用程序内核开发缓存识别算法。将对内核进行优化，以利用空间和时间缓存结构、数据预取和模型中抽象的其他特征。性能改进将通过在真实架构平台（如Intel IA-64和Sun UltraSPARC III Cu）上的低级模拟和实验来验证。（iii）为编译时数据在主存中的放置创建一个数学基础，以减少运行时的缓存丢失，使用完全拉丁平方（PLS）来减少缓存冲突。（iv）使用上述技术来优化用于数据库存储和访问（搜索）、树遍历、非结构化网格计算和图形问题的算法的性能。我们设想，我们的研究将补充正在进行的缓存架构的进展，并导致创建一个新的计算模型，为下一代通用处理器编程。

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.