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是没有Big-O的复杂性。 在比较算法时，DMD复杂度可以精确地识别DMD之间的常数因子差异。 第二个是用于循环并行化的并行局部性分析。 高速缓存性能一直是理解并行计算极限的基础问题，也是实践中的重要问题。 新的分析用于并行代码的自动缩放。 虽然自动并行化在创建可移植并行代码时节省了编程工作量，但自动缩放在获得可移植并行性能时节省了测试和调优时间。 最后，开发了另外两种程序优化技术：Rust中的安全结构分割和程序共生，以提高共享缓存的性能。 当这些技术结合使用时，可以让算法和程序设计在不同层次上实现抽象数据移动，所有这些都由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

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

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