ALGORITHMS: Performance Programming for Advanced Cache Architectures

算法：高级缓存架构的性能编程

• 批准号: 0305763
• 负责人: Viktor Prasanna
• 金额: $ 39.24万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0305763&HistoricalAwards=false
• 关键词: ALGORITHMS; Performance; Programming; Advanced; Cache

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.

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