ALGORITHMS: Performance Programming for Advanced Cache Architectures

认识到传统高速缓存层次结构的缺点，特别是对于不规则应用程序，已经导致了一种新类型的处理器的出现，其允许在应用程序级别直接操纵高速缓存层次结构。基于对应用程序数据访问行为的了解，“智能”编程可以显著提高性能。该项目将探索一种用于高级高速缓存体系结构的性能编程的新方法，该方法基于应用程序级别的显式内存层次管理。我们的研究将集中在：(I)定义一个分离的空间/时间缓存和显式缓存控制的通用模型。该模型将从程序员的角度抽象可用的体系结构功能。实现了一个基于该模型的高级仿真器。(Ii)开发规则和非规则应用内核的缓存识别算法。内核将进行优化，以利用空间和时间缓存结构、数据预取以及模型中抽象的其他功能。性能改进将通过在Intel IA-和Sun UltraSPARC III Cu等真实架构平台上的低级别模拟和实验来验证。(Iii)为主存中的编译时数据放置创建数学基础，以最大限度地减少运行时的高速缓存未命中，使用On Perfect拉丁方(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.