Automatic tiling of iterative stencil loops
Automatic tiling of iterative stencil loops
复制标题
DOI：
10.1145/1034774.1034777
复制
发表时间：
2004-11
期刊：
影响因子：
--
通讯作者：
Zhiyuan Li;Yonghong Song
中科院分区：
文献类型：
--
作者：
Zhiyuan Li;Yonghong Song
迭代模板循环在科学程序中用于实现数值模拟和信号处理的松弛方法。这样的循环在不同的时间步长上迭代地修改相同的数组元素，这为编译器提供了通过循环平铺来提高时态数据局部性的机会。本文提出了一个编译器框架，用于自动平铺迭代模板循环，目的是提高该高速缓存的性能。文章首先提出了一种技术，它允许循环平铺，以满足数据的依赖性，尽管不完美的嵌套内部循环所造成的困难。它通过在时间步长上倾斜内部循环并将统一的倾斜因子应用于相同嵌套级别的所有循环来实现。基于内存成本分析，本文表明，为了最大限度地减少缓存未命中，必须在每个循环级别上最小化偏斜因子。提出了一种求最小偏斜因子的图论算法，该算法需要多项式时间。此外，存储器成本分析导出最小化容量未命中的瓦片大小。给定瓦片大小，应用有效且通用的阵列填充方案来移除冲突未命中。在16个测试程序上进行了实验，初步结果表明，这些测试程序的平均加速比为1.58，最大加速比为5.06。
Iterative stencil loops are used in scientific programs to implement relaxation methods for numerical simulation and signal processing. Such loops iteratively modify the same array elements over different time steps, which presents opportunities for the compiler to improve the temporal data locality through loop tiling. This article presents a compiler framework for automatic tiling of iterative stencil loops, with the objective of improving the cache performance. The article first presents a technique which allows loop tiling to satisfy data dependences in spite of the difficulty created by imperfectly nested inner loops. It does so by skewing the inner loops over the time steps and by applying a uniform skew factor to all loops at the same nesting level. Based on a memory cost analysis, the article shows that the skew factor must be minimized at every loop level in order to minimize cache misses. A graph-theoretical algorithm, which takes polynomial time, is presented to determine the minimum skew factor. Furthermore, the memory-cost analysis derives the tile size which minimizes capacity misses. Given the tile size, an efficient and general array-padding scheme is applied to remove conflict misses. Experiments were conducted on 16 test programs and preliminary results showed an average speedup of 1.58 and a maximum speedup of 5.06 across those test programs.