SHF: Small: Automated Analysis and User Feedback on Data Movement Bottlenecks in Programs

在当前的计算机系统中，相对于执行算术运算的成本，在时间和能量方面，通过存储器层次结构的数据移动的成本非常高。预计它将在未来的计算机系统中变得更加主导。因此，优化数据访问成本在未来几年将变得越来越重要。这对这类系统的算法设计和实现有很大的影响。数据访问复杂性的特征目前只对几类算法已知，例如密集线性代数，并且需要使用特定于问题的分析技术。这一建议为开发自动化工具和技术提供了新的想法，以表征任意算法固有的数据访问复杂性。程序数据访问复杂性的自动化通用方法将对获得高效的算法及其实现、理解未来体系结构对算法设计的影响、以及旨在提高程序数据访问成本的编译器的进步具有重要影响。该提议为解决日益重要的基本问题开辟了新的思路--开发工具和技术来表征算法固有的数据访问复杂性。这项工作的进展如下：(I)第一个统一的方法，用于在一个公共的底层理论模型下为CDAG固有的数据访问复杂性建立上下限；(Ii)一种方法，以消除当前流行的重用距离分析度量的基本限制；(Iii)一个可扩展的、通用的动态分析基础设施，供应用程序开发人员、编译器编写人员和体系结构设计人员使用。

The cost of data movement through the memory hierarchy is very high in current computer systems, relative to the cost of performing arithmetic operations, both in terms of time and energy. It is expected to become even more dominant in future computer systems. Therefore optimizing data access costs will become increasingly critical in the coming years. This has great impact on algorithm design and implementation on such systems. A characterization of data access complexity is only known today for a few classes of algorithms, such as dense linear algebra, and has required the use of problem-specific analysis techniques. This proposal presents novel ideas for developing automated tools and techniques to characterize the inherent data access complexity of arbitrary algorithms. An automatable general approach for data access complexity of programs will have significant impact on deriving highly effective algorithms and their implementations, understanding the impact of future architectures on algorithm design, and on advances in compilers aimed at improving data access costs of programs.The proposal develops novel ideas to address a fundamental problem of increasing importance -- developing tools and techniques for characterization of the inherent data access complexity of algorithms. The work develops the following: (i) the first unifying approach for developing both upper and lower bounds for the inherent data access complexity of a CDAG under a common underlying theoretical model; (ii) an approach to remove a fundamental current limitation in the use of the popular reuse distance analysis metric; (iii) a scalable and versatile dynamic analysis infrastructure of use to application developers, compiler writers and architecture designers.