Beyond time complexity: data movement complexity analysis for matrix multiplication
Beyond time complexity: data movement complexity analysis for matrix multiplication
复制标题
DOI：
10.1145/3524059.3532395
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Wesley Smith;Aidan Goldfarb;C. Ding
中科院分区：
文献类型：
--
作者：
Wesley Smith;Aidan Goldfarb;C. Ding
数据移动正在成为各种应用程序领域计算的时间和能源成本的主要贡献者。然而，时间复杂度不足以分析数据移动。这项工作扩展了最近提出的内存感知算法分析框架Data Movement Distance，通过1）证明其假设符合微架构趋势，2）将其应用于矩阵乘法的四种变体，以及3）显示它能够渐近区分具有相同时间复杂度但不同内存行为的算法，以及相同算法的局部优化与非优化版本。在这样做时，我们试图弥合理论和实践相结合的渐近时间复杂度与每操作的数据移动成本从分层内存结构所使用的操作计数分析。此外，本文还首次推导出了LRU缓存系统上递归矩阵乘法失败率曲线的完全精确、完全解析的形式。我们的研究结果表明，数据移动距离框架是一个强大的工具，工程师和算法设计师去理解层次记忆的算法含义。
Data movement is becoming the dominant contributor to the time and energy costs of computation across a wide range of application domains. However, time complexity is inadequate to analyze data movement. This work expands upon Data Movement Distance, a recently proposed framework for memory-aware algorithm analysis, by 1) demonstrating that its assumptions conform with microarchitectural trends, 2) applying it to four variants of matrix multiplication, and 3) showing it to be capable of asymptotically differentiating algorithms with the same time complexity but different memory behavior, as well as locality optimized vs. non-optimized versions of the same algorithm. In doing so, we attempt to bridge theory and practice by combining the operation count analysis used by asymptotic time complexity with per-operation data movement cost resulting from hierarchical memory structure. Additionally, this paper derives the first fully precise, fully analytical form of recursive matrix multiplication's miss ratio curve on LRU caching systems. Our results indicate that the Data Movement Distance framework is a powerful tool going forward for engineers and algorithm designers to understand the algorithmic implications of hierarchical memory.