SHF: Small: Data Movement Complexity: Theory and Optimization

随着计算变得越来越强大，内存越来越大，越来越复杂，数据移动越来越成为时间和精力成本的主要来源。然而，测量问题并没有得到很好的解决。程序员必须在机器上运行程序来测量数据的移动。在测量之后，他们通常会得到一组数字，它们之间的关系并不清楚。在并行执行中，结果也不能重现。本研究首先提出一种抽象的内存成本测量方法，称为数据移动距离（DMD）。此外，它还创建了数据移动复杂性理论，可用于有效的程序和算法优化。编程技术应保证软件的可移植性；因此，现代软件并不明确地对数据移动进行编程。有了新的理论，数据移动的成本被精确量化，更高的精度使新的软件优化能够更有效地降低这一成本。由于新的度量是抽象的，而不是特定于机器的，因此新的优化是与机器无关的，因此可移植。最后，在新理论的基础上开发了多种优化技术。通过专注于降低数据移动的成本，本研究的目标是现代计算机、数据中心和计算基础设施中能耗最大的原因。为了应对日益加速的气候变化，迫切需要减少计算机消耗的能源。本研究提出了一种抽象的内存成本测量方法，称为数据移动距离（DMD）。内存复杂度由DMD衡量，时间复杂度由操作次数衡量。本研究分为三个部分。第一类是DMD复杂度分析，它具有符号性和渐近性。DMD是没有Big-O的复杂性。在比较算法时，DMD复杂性可以精确地识别DMD之间的常数因子差异。其次是循环并行化使用的并行局部性分析。缓存性能长期以来一直是理解并行计算极限的基本问题，在实践中也很重要。新的分析方法用于并行代码的自动缩放。虽然自动并行化节省了创建可移植并行代码的编程工作，但自动缩放节省了获得可移植并行性能的测试和调优时间。最后，开发了另外两种程序优化技术：Rust中的安全结构拆分和程序共生，以提高共享缓存中的性能。当这些技术一起使用时，这些技术让算法和程序设计在不同的层次上以抽象数据移动为目标，所有这些都由DMD测量，因此可以跨软件层进行与机器无关的联合优化。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.