Automated derivation of parametric data movement lower bounds for affine programs
Automated derivation of parametric data movement lower bounds for affine programs
复制标题
自动推导仿射程序的参数数据移动下限
DOI：
10.1145/3385412.3385989
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rastello, Fabrice
中科院分区：
文献类型：
--
作者：
Olivry, Auguste;Langou, Julien;Pouchet, Louis-Noël;Sadayappan, P.;Rastello, Fabrice
长期以来，研究人员和实践者一直致力于提高算法的计算复杂度，重点是减少执行计算所需的操作数量。然而，如今的硬件趋势清楚地表明，数据移动的性能和能源成本高于计算：高质量的算法必须尽可能减少数据移动。算法的理论操作复杂度是必须执行的操作总数的函数，而不管它们实际执行的顺序如何。但理论上的数据移动（或I/O）复杂性是根本不同的：必须考虑所有可能的操作的法律的时间表，以确定可实现的数据移动的最小数量，这是一个主要的理论挑战。I/O复杂性已经通过复杂的手动证明进行了研究，例如，Hong & Kung将缓存大小S上矩阵乘法的Ω（n3/nS）改进为2n 3/nS by Smith et al.虽然渐近复杂性可能足以比较广泛不同算法之间的I/O潜力，但推理的准确性取决于这些I/O下限的紧密性。准确地说，暴露常数是必不可少的，使不同的算法之间的精确比较：例如，2n 3/Slower界允许展示最优的面板面板平铺矩阵multiply.We提出的第一个静态分析，自动推导出非渐近参数表达式的数据移动下限与缩放常数，任意仿射计算。我们的方法是全自动的，帮助算法设计者推理I/O复杂性，并对算法的替代方案做出明智的决定。
Researchers and practitioners have for long worked on improving the computational complexity of algorithms, focusing on reducing the number of operations needed to perform a computation. However the hardware trend nowadays clearly shows a higher performance and energy cost for data movements than computations: quality algorithms have to minimize data movements as much as possible.The theoretical operational complexity of an algorithm is a function of the total number of operations that must be executed, regardless of the order in which they will actually be executed. But theoretical data movement (or, I/O) complexity is fundamentally different: one must consider all possible legal schedules of the operations to determine the minimal number of data movements achievable, a major theoretical challenge. I/O complexity has been studied via complex manual proofs, e.g., refined from Ω(n3/√S) for matrix-multiply on a cache sizeSby Hong & Kung to 2n3/√Sby Smith et al. While asymptotic complexity may be sufficient to compare I/O potential between broadly different algorithms, the accuracy of the reasoning depends on the tightness of these I/O lower bounds. Precisely, exposing constants is essential to enable precise comparison between different algorithms: for example the 2n3/√Slower bound allows to demonstrate the optimality of panel-panel tiling for matrix-multiplication.We present the first static analysis to automatically derive non-asymptotic parametric expressions of data movement lower bounds with scaling constants, for arbitrary affine computations. Our approach is fully automatic, assisting algorithm designers to reason about I/O complexity and make educated decisions about algorithmic alternatives.
登录
查看更多内容
DOI：
10.1007/3-540-48224-5_11
发表时间：
2001-07
期刊：
--
影响因子：
--
作者：
G. Bilardi;E. Peserico
通讯作者：
G. Bilardi;E. Peserico
DOI：
10.1016/0743-7315(92)90027-k
发表时间：
1992
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
J. Ramanujam;P. Sadayappan
通讯作者：
P. Sadayappan
DOI：
10.1145/1463768.1463780
发表时间：
2008
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
J. Savage;M. Zubair
通讯作者：
M. Zubair
二项式和 FFT 计算图的强 I/O 下界
DOI：
10.1007/978-3-642-22685-4_12
发表时间：
2011
期刊：
Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis
影响因子：
--
作者：
D. Ranjan;J. Savage;M. Zubair
通讯作者：
M. Zubair
卵石游戏
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Donald Gropman
通讯作者：
Donald Gropman