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 的法定使命，并被认为值得通过以下方式获得支持：使用基金会的智力价值和更广泛的影响审查标准进行评估。

项目成果

Beyond time complexity: data movement complexity analysis for matrix multiplication

超越时间复杂度：矩阵乘法的数据移动复杂度分析

• DOI: 10.1145/3524059.3532395
• 发表时间: 2022-06
• 期刊: 2022 International Conference on Supercomputing (ICS ’22
• 作者: Smith, Wesley;Goldfarb, Aidan;Ding, Chen
• 通讯作者: Ding, Chen

Cache-coherent CLAM (WIP)

缓存一致性 CLAM (WIP)

• DOI: 10.1145/3519941.3535073
• 发表时间: 2022-06
• 期刊: 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

过去的爆炸：最少预期使用 (LEU) 缓存替换与统计历史记录

• DOI: 10.1145/3591195.3595267
• 发表时间: 2023-06
• 期刊: ACM SIGPLAN International Symposium on Memory Management
• 作者: Chakraborti, Sayak;Zhang, Zhizhou;Bertram, Noah;Ding, Chen;Dwarkadas, Sandhya
• 通讯作者: Dwarkadas, Sandhya

Cache Programming for Scientific Loops Using Leases

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

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