SHF: Small: Data Movement Complexity: Theory and Optimization

SHF：小型：数据移动复杂性：理论与优化

• 批准号: 2217395
• 负责人: Chen Ding
• 金额: $ 57.15万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2217395&HistoricalAwards=false
• 关键词: SHF; Small; Data; Movement; Complexity

As computing becomes more powerful, memory is larger and more complex, and data movement increasingly a major source of cost in both time and energy. However, the measurement problem is not well solved. Programmers have to run a program on a machine to measure data movement. After measuring, they are often left with a set of numbers with unclear relationships between them. In parallel executions, the results are also not reproducible. This research first develops an abstract measure of the memory cost called Data Movement Distance (DMD). In addition, it creates a theory of data movement complexity, which can be used for effective program and algorithmic optimization. Programming technology should ensure software portability; therefore modern software does not program data movement explicitly. With the new theory, the cost of data movement is precisely quantified, and the greater precision enables new software optimization to more effectively reduce this cost. Since the new measure is abstract and not machine-specific, the new optimization is machine-agnostic and therefore portable. In the last part, the research develops multiple optimization techniques based on the new theory. By focusing on reducing the cost of data movement, this research targets the cause of the most energy consumption on modern computers, data centers, and computing infrastructure in general. Reducing the energy consumed by computing is urgently needed in response to accelerating climate change. This research develops an abstract measure of the memory cost called Data Movement Distance (DMD). Memory complexity is measured by DMD in the same way time complexity is by the operation count. The research has three parts. The first is DMD complexity analysis, which is both symbolic and asymptotic. DMD is complexity without Big-O. When comparing algorithms, DMD complexity discerns precise constant-factor differences between DMDs. The second is parallel locality analysis for use by loop parallelization. Cache performance has long been a problem both fundamental in understanding the limit of parallel computing and important in practice. The new analysis is used for auto-scaling of parallel code. While auto-parallelization saves the programming effort in creating portable parallel code, auto-scaling saves the testing and tuning time in obtaining portable parallel performance. Finally, two other program-optimization techniques are developed: safe structure splitting in Rust and program symbiosis to improve performance in the shared cache. When used together, these techniques let algorithm and program design target abstract data movement at different levels, all measured by DMD, and hence enable machine-agnostic joint optimization across software layers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

随着计算变得越来越强大，内存更大，更复杂，数据移动越来越多地是时间和能量的主要成本来源。 但是，测量问题无法很好地解决。 程序员必须在计算机上运行程序来衡量数据移动。 测量之后，它们通常会带有一组数字，它们之间的关系不清楚。 在并行执行中，结果也不可再现。 这项研究首先开发了一种称为数据运动距离（DMD）的记忆成本的抽象度量。 此外，它创建了数据运动复杂性的理论，可用于有效程序和算法优化。 编程技术应确保软件可移植性；因此，现代软件不会明确编程数据移动。 有了新的理论，数据移动的成本得到了精确量化，并且更高的精度使新的软件优化可以更有效地降低此成本。 由于新的度量是抽象的，而不是机器特定的，因此新的优化是机器不合时式的，因此是可移植的。 在最后一部分中，研究基于新理论开发了多种优化技术。 通过关注降低数据流动的成本，这项研究是针对现代计算机，数据中心和计算基础架构最多能量消耗的原因。 迫切需要减少计算消耗的能量，以加速气候变化。这项研究开发了一种称为数据运动距离（DMD）的记忆成本的抽象度量。 记忆复杂性通过DMD以相同的时间复杂度来衡量。 这项研究有三个部分。 第一个是DMD复杂性分析，既是符号和渐近性。 DMD是复杂的，没有大o。 在比较算法时，DMD复杂性辨别DMD之间的精确恒定因素差异。 第二个是平行的位置分析，用于通过循环并行化使用。 长期以来，缓存性能一直是理解并行计算的极限的基本问题，而在实践中很重要。 新的分析用于自动缩放并行代码。 虽然自动平行化保存了创建便携式并行代码的编程工作，但自动尺度可以节省测试和调谐时间，以获得便携式并行性能。 最后，开发了另外两种程序优化技术：生锈和程序共生中的安全结构分裂以提高共享缓存的性能。 当一起使用时，这些技术使算法和程序设计目标是以不同级别进行的抽象数据运动，所有这些都由DMD衡量，因此可以在软件层之间进行机器 - 不可能的关节优化。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子和更广泛的影响来评估的支持，并被认为是值得的。

项目成果

Cache-coherent CLAM (WIP)

缓存一致性 CLAM (WIP)

• DOI: 10.1145/3519941.3535073
• 发表时间: 2022
• 期刊: Cache-Coherent CLAM (WIP
• 作者: Ding, Chen;Reber, Benjamin;Patru, Dorin
• 通讯作者: Patru, Dorin

Blast from the Past: Least Expected Use (LEU) Cache Replacement with Statistical History

• DOI: 10.1145/3591195.3595267
• 发表时间: 2023-06
• 期刊: Proceedings of the 2023 ACM SIGPLAN International Symposium on Memory Management
• 作者: Sayak Chakraborti;Zhizhou Zhang;Noah Bertram;C. Ding;S. Dwarkadas

Beyond time complexity: data movement complexity analysis for matrix multiplication

• DOI: 10.1145/3524059.3532395
• 发表时间: 2022-03
• 期刊: Proceedings of the 36th ACM International Conference on Supercomputing
• 作者: Wesley Smith;Aidan Goldfarb;C. Ding

Cache Programming for Scientific Loops Using Leases

使用租约对科学循环进行缓存编程

• 发表时间: 2023
• 期刊: ACM transactions on architecture and code optimization
• 影响因子: 1.6
• 作者: Reber, Benjamin;Gould, Matthew;Kneipp, Alexander H.;Liu, Fangzhou;Prechtl, Ian;Ding, Chen;Chen, Linlin;Patru, Dorin
• 通讯作者: Patru, Dorin