Challenges in CISE: TUNE: System Support for Memory-Friendly Programming

Trivedi, Kishor Board, John A. Duke University CISE: TUNE：内存友好编程的系统支持在基于微处理器的机器中普遍使用多级内存层次结构，使得应用程序的性能主要由其内存映射决定，并且对其内存映射极其敏感，并且需要内存友好编程：仔细布局数据结构和重构代码以改进数据局域性。提高内存系统性能的技术体现在各个层次上，从高级算法和数据结构，到编译时分析和程序重构，再到允许应用程序更好地管理内存层次结构的特殊体系结构原语。由于缺乏用于改进数据局部性的自动工具，目前迫使许多应用程序程序员手动重构他们的代码。不幸的是，在现代科学计算中看到的复杂算法需要同样复杂的重构技术。这些技术需要计算机体系结构方面的专业知识，使程序员负担与程序正确性无关的冗长的特定于机器的细节，并降低重构代码的可读性、可维护性和可移植性。由于所有这些原因，手动重组任何规模的程序都是站不住脚的，并且需要某种类型的系统支持。该项目针对该问题的所有方面，从开发用于表示和操作数据局部性的相关数学技术，到实现交互式和自动数据局部性管理工具，再到为下一代系统提出创新的内存架构。结果系统的有效性将使用代表现代科学计算的程序进行演示，包括分而治之的科学计算，如n体求解器（例如，fastmultipole）和许多线性代数核（例如，Strassens的矩阵乘法算法）。

9726370 Trivedi, Kishor Board, John A. Duke University Challenges in CISE: TUNE: System Support for Memory-Friendly Programming The pervasive use of multi-level memory hierarchies in microprocessor-based machines makes the performance of an application primarily determined by and extremely sensitive to its memory mapping, and requires memory-friendly programming: careful layout of data structures and restructuring of code to improve data locality. Techniques for improving memory system performance manifest themselves at various levels, from high-level algorithms and data structures, through compile-time analysis and restructuring of programs, to special architectural primitives that allow an application to better manage the memory hierarchy. The lack of automatic tools for improving data locality currently forces many application programmers to manually restructure their codes. Unfortunately, the sophisticated algorithms seen in modern scientific computing require equally sophisticated restructuring techniques. These techniques require expertise in computer architecture, burden the programmer with tedious machine-specific details unrelated to program correctness, and reduce the readability, maintainability, and portability of the restructured code. For all these reasons, manual restructuring of programs of any significant size is untenable, and some kind of system support is necessary. This project targets all aspects of this problem, from developing the relevant mathematical techniques for representing and manipulating data locality, through implementing interactive and automatic data locality management tools, to proposing innovative memory architectures for future-generation systems. The efficacy of the resulting system will be demonstrated using programs representative of modern scientific computations including divide-and-conquer scientific computations such as N-body solvers (e.g., fastmultipole) and many linear algebra kernels (e.g., Strassens's matrix multiplication algo rithm).