Multi-level tiling: M for the price of one
Multi-level tiling: M for the price of one
复制标题
DOI：
10.1145/1362622.1362691
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
DaeGon Kim;Lakshminarayanan Renganarayanan;D. Rostron;S. Rajopadhye;M. Strout
中科院分区：
文献类型：
--
作者：
DaeGon Kim;Lakshminarayanan Renganarayanan;D. Rostron;S. Rajopadhye;M. Strout
平铺是一种广泛使用的循环转换，用于公开/利用并行性和数据局部性。高性能实现使用多个级别的平铺来利用并行性和缓存/寄存器局部性的层次结构。多级平铺代码的高效生成对于有效使用多级平铺至关重要。参数化平铺代码（其中平铺大小不固定而是保留为符号参数）可以实现多种动态和运行时优化。先前的多级平铺循环生成解决方案仅限于平铺大小在编译时固定的情况。我们提出了一种算法，可以以与生成单级平铺循环相同的成本生成多级参数化平铺循环。我们的方法的效率在几个基准测试中得到了证明。我们还提出了一种在注册平铺中有用的方法，用于在任意平铺级别上分离部分平铺和完整平铺。我们实现的代码生成器可作为开源工具使用。
Tiling is a widely used loop transformation for exposing/exploiting parallelism and data locality. High-performance implementations use multiple levels of tiling to exploit the hierarchy of parallelism and cache/register locality. Efficient generation of multi-level tiled code is essential for effective use of multi-level tiling. Parameterized tiled code, where tile sizes are not fixed but left as symbolic parameters can enable several dynamic and run-time optimizations. Previous solutions to multi-level tiled loop generation are limited to the case where tile sizes are fixed at compile time. We present an algorithm that can generate multi-level parameterized tiled loops at the same cost as generating single-level tiled loops. The efficiency of our method is demonstrated on several benchmarks. We also present a method-useful in register tiling-for separating partial and full tiles at any arbitrary level of tiling. The code generator we have implemented is available as an open source tool.