IOOpt: automatic derivation of I/O complexity bounds for affine programs
IOOpt: automatic derivation of I/O complexity bounds for affine programs
复制标题
IOOpt：自动推导仿射程序的 I/O 复杂度界限
DOI：
10.1145/3453483.3454103
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Rastello, Fabrice
中科院分区：
文献类型：
--
作者：
Olivry, Auguste;Iooss, Guillaume;Tollenaere, Nicolas;Rountev, Atanas;Sadayappan, P.;Rastello, Fabrice
评估算法的复杂性是开发应用程序时的重要步骤，因为它会影响其时间和能量性能。计算复杂度是动态操作的数量，与执行顺序无关，很容易描述仿射程序的特征。数据移动（或，I/O）的复杂性是更复杂的评估，因为它是指，当考虑所有可能的有效时间表，到一个缓慢的（如主存储器）和一个快速的（如本地暂存器）storage location.This之间的I/O所需的最小数量提出IOOpt，一个全自动的工具，自动绑定的仿射（tilable）程序的数据移动。给定在DSL中描述的可平铺程序，它自动计算：1. I/O复杂度的下限，作为该高速缓存大小和程序参数的符号表达式; 2.上限，其允许评估下限的紧密性; 3.匹配上限的平铺推荐（循环置换和平铺大小）。对于可以应用于任何仿射程序的下界算法，已经做出了大量的努力来为神经网络提供尽可能紧密的边界：特别是，它扩展了Olivry等人以前的工作，以处理多维约简并暴露与卷积中存在的小维度相关的约束。对于在程序的tile band上推理的上限算法（例如，多面体编译器（如PluTo）的输出），所涉及的代数计算已经被调整为在张量计算（如直接张量收缩或直接卷积）上表现良好。作为奖励，上限算法，已扩展到多级缓存可以为程序员提供一个有用的平铺recommendations.We证明了我们的工具的有效性，通过推导几个张量收缩和卷积核的符号上下界。然后，我们使用Yolo 9000的卷积层和来自TCCG基准套件的代表性张量收缩来数值评估我们的边界的紧密性。最后，我们通过报告Yolo 9000卷积层推荐的平铺代码的运行时间来展示我们的I/O复杂性模型的相关性。
Evaluating the complexity of an algorithm is an important step when developing applications, as it impacts both its time and energy performance. Computational complexity, which is the number of dynamic operations regardless of the execution order, is easy to characterize for affine programs. Data movement (or, I/O) complexity is more complex to evaluate as it refers,when considering all possible valid schedules, to the minimum required number of I/O between a slow (e.g. main memory) and a fast (e.g. local scratchpad) storage location.This paper presents IOOpt, a fully automated tool that automatically bounds the data movement of an affine (tilable) program. Given a tilable program described in a DSL, it automatically computes: 1. a lower bound of the I/O complexity as a symbolic expression of the cache size and program parameters; 2. an upper bound that allows one to assess the tightness of the lower bound; 3. a tiling recommendation (loop permutation and tile sizes) that matches the upper bound. For the lower bound algorithm which can be applied to any affine program, a substantial effort has been made to provide bounds that are as tight as possible for neural networks: In particular, it extends the previous work of Olivry et al. to handle multi-dimensional reductions and expose the constraints associated with small dimensions that are present in convolutions. For the upper bound algorithm that reasons on the tile band of the program (e.g. output of a polyhedral compiler such as PluTo), the algebraic computations involved have been tuned to behave well on tensor computations such as direct tensor contractions or direct convolutions. As a bonus, the upper bound algorithm that has been extended to multi-level cache can provide the programmer with a useful tiling recommendation.We demonstrate the effectiveness of our tool by deriving the symbolic lower and upper bounds for several tensor contraction and convolution kernels. Then we evaluate numerically the tightness of our bound using the convolution layers of Yolo9000 and representative tensor contractions from the TCCG benchmark suite. Finally, we show the pertinence of our I/O complexity model by reporting the running time of the recommended tiled code for the convolution layers of Yolo9000.
登录
查看更多内容
关于评估和增强缓存有效性
DOI：
--
发表时间：
1991
期刊：
International Workshop on Languages and Compilers for Parallel Computing
影响因子：
--
作者：
J. Ferrante;Vivek Sarkar;W. Thrash
通讯作者：
W. Thrash
二项式和 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
矩阵乘法的严格 I/O 下界
DOI：
10.1145/3362694
发表时间：
2017
期刊：
ACM Transactions on Mathematical Software (TOMS)
影响因子：
--
作者：
T. Smith;R. A. van de Geijn
通讯作者：
R. A. van de Geijn
影响因子：
--
作者：
Wenlei Bao;S. Krishnamoorthy;L. Pouchet;P. Sadayappan
通讯作者：
P. Sadayappan
在高级综合中优化内存重用的分块大小选择
DOI：
--
发表时间：
2017
期刊：
International Conference on Field-Programmable Logic and Applications
影响因子：
--
作者：
Junyi Liu;John Wickerson;G. Constantinides
通讯作者：
G. Constantinides