A Cost-Effective Implementation of Multilevel Tiling
A Cost-Effective Implementation of Multilevel Tiling
复制标题
多层平铺的经济高效实施
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Agustín Fernández
中科院分区：
文献类型：
--
作者：
M. Jiménez;J. Llabería;Agustín Fernández
针对以仿射函数为界的环巢（非矩形环巢），提出了一种计算多层平铺精确环界的高效算法。传统上，没有执行精确的循环边界计算，因为它的复杂性是多层平铺代码中循环数量的双指数，因此，对于某些类型的循环（即非矩形循环巢），可能非常耗时。虽然在只对缓存级别进行平铺时，精确循环边界的计算不是很重要，但当平铺包括寄存器级别时，它是至关重要的。本文提出了一种多层平铺的有效实现方法，它计算精确的循环边界，并且比传统技术的复杂性低得多。为了实现这种较低的复杂性，我们的技术同时处理所有要平铺的关卡，而不是像通常那样逐级进行平铺。对于以非常简单的仿射函数为界的环巢，结果表明我们的方法比传统技术快15到28倍。对于没有这么简单边界的循环巢，我们测量到的加速高达2300。此外，我们的技术允许有效地消除冗余界限。结果表明，对于典型的线性代数程序，我们的方法消除冗余边界的速度比传统方法快22到11倍。
This paper presents a new cost-effective algorithm to compute exact loop bounds when multilevel tiling is applied to a loop nest having affine functions as bounds (nonrectangular loop nest). Traditionally, exact loop bounds computation has not been performed because its complexity is doubly exponential on the number of loops in the multilevel tiled code and, therefore, for certain classes of loops (i.e., nonrectangular loop nests), can be extremely time consuming. Although computation of exact loop bounds is not very important when tiling only for cache levels, it is critical when tiling includes the register level. This paper presents an efficient implementation of multilevel tiling that computes exact loop bounds and has a much lower complexity than conventional techniques. To achieve this lower complexity, our technique deals simultaneously with all levels to be tiled, rather than applying tiling level by level as is usually done. For loop nests having very simple affine functions as bounds, results show that our method is between 15 and 28 times faster than conventional techniques. For loop nests caving not so simple bounds, we have measured speedups as high as 2,300. Additionally, our technique allows eliminating redundant bounds efficiently. Results show that eliminating redundant bounds in our method is between 22 and 11 times faster than in conventional techniques for typical linear algebra programs.