A Loop Transformation Theory and an Algorithm to Maximize Parallelism
这篇论文研究如何组合循环变换,在 general loop nests 中暴露最大并行度。这里的并行度指 DOALL 循环的数量,即可并行执行的循环层数;DOALL 要求该循环不承载迭代间依赖。它不是线程数或程序加速比。(§III-B,p. 456)
Michael E. Wolf、Monica S. Lam,IEEE TPDS 2(4),1991,pp. 452–471。论文 DOI · Zotero PDF。下文页码均为期刊页码。
Introduction
Interchange 改变循环嵌套顺序,reversal 反转遍历方向,skewing 将一个循环坐标与另一个坐标线性组合,tiling 将迭代空间分块。这些变换可用于并行化和提高数据局部性,困难在于如何组合它们:一个变换可能只是为后续变换创造条件,无法逐步按即时收益决定;skewing 又有无穷多个整数系数,不能穷举所有组合。(§I,p. 452)
已有矩阵方法适用于依赖能由一组固定整数距离向量表示的循环,包括许多稠密线性代数代码以及作者所讨论的 systolic array 算法。在这一模型下,
Unimodular Transformations
用整数列向量
Interchange、reversal 和 skewing 可分别表示为整数矩阵;组合变换是这些矩阵按执行顺序相乘。它们统一为幺模变换:
对固定距离向量集合
因此可以直接判断最终组合的合法性,无须要求每个中间步骤都合法。原文的例子中,依赖
Direction Vectors
一般依赖可能只知道某维距离的方向,而不知道固定距离。作者用整数区间表示每个分量:精确距离
一个方向向量
作者定义区间加法和整数倍乘,使
精确变换后的集合为
Fully Permutable Nests 与 Wavefront
一个完全可置换循环组(fully permutable nest)允许组内循环任意交换顺序而保持合法。判断时只需考虑尚未由更外层循环满足的依赖;这些依赖在组内各维的分量必须非负。完全可置换不等于已可并行,它提供了可以进一步集中依赖的结构。(§II-C,定理 2.2,p. 455)
对于有限的、字典序为正的距离向量集合,可以由外向内 skew 内层循环,把负分量补为非负,最终使整个循环巢完全可置换。原文例子
对
简化算例(AI 补充):取
两条依赖分别变成
Canonical Form 与并行化算法
含方向信息时,整个循环巢未必能成为一个完全可置换组。规范形式因此是一系列嵌套的完全可置换组,并让每个外层组尽可能大。算法先找最大外层组,固定后递归处理剩余循环;进入内层时,只保留尚未由外层满足的依赖。再对各组进行 wavefront 变换,提取各组的 DOALL 维度。(§V-B,p. 460)
作者的最优性论证依赖于最大外层组的结构:任意两个合法外层完全可置换组所张成的行空间,都能包含在某个共同的合法外层组中。因而可先构造最大外层组,再递归求内层,而不会损失幺模变换所能暴露的最大 DOALL 数量。这是给定依赖模型与变换空间内的结论。(§V-B;附录 B,定理 B.5–B.6,p. 470)
求最大外层组是最困难的步骤。实用算法 Find_FPNest 按以下顺序缩小问题:
- 排除 serializing loops。 若某循环维度在当前依赖集合中既出现负向无界分量,又出现正向无界分量,那么构造外层完全可置换组的矩阵行在该维的系数只能为零。这些循环暂时不能进入当前外层组,但外层满足部分依赖后,内层问题会重新判断。(§VI-A,定理 6.1,p. 461)
- 用 SRP 扩充组。 尝试 permutation、reversal、skewing 的组合
,将更多循环的相关依赖分量变为非负。 是置换矩阵, 的对角元为 , 是单位对角的下三角矩阵。只需最终组合合法,单独应用 可能不合法。(§VI-B,p. 462) - 对剩余循环使用 time-cone 方法。 寻找与各非零依赖内积为正的时间方向,使依赖由新的外层循环承载。二维情形中,把时间向量
约成互素整数,利用扩展 Euclid 算法求整数 满足 ,即可补成幺模矩阵;再用 skewing 形成完全可置换组。(§VI-C,pp. 462–463,Fig. 6)
理论上的规范形式最优性与高效算法的保证范围不同。 作者推荐只对剩余问题使用二维 time-cone 方法:剩余待处理循环不超过两层时最优,更多时按循环对尝试属于启发式。整体复杂度为
并行粒度、Tiling 与代码生成
Wavefront 自然把 DOALL 循环放在串行时间循环内,适合细粒度并行。粗粒度并行则希望尽量把 DOALL 放到外层,使一个并行任务包含更多计算、减少同步。对距离向量,若某行向量
若每个 wavefront 都做全局 barrier,同步粒度仍可能过细。完全可置换组也可以安全 tiling:先分块,再对 tile 的 controlling loops 做 wavefront,让每次同步之间执行一个 tile 的工作;或者在 tile 层使用 DOACROSS,以依赖 tile 之间的局部同步代替整条波前的全局 barrier。块内仍可提取细粒度并行,有跨迭代数据复用时也可改善局部性。Tiling 本身不是幺模变换:它引入额外的块级循环,通常将
确定组合矩阵后,循环体通过 min、max 和取整除法构成的指定边界形式,非单位步长需先规范化;不能满足边界形式的循环不能参与这套变换。生成结果可能含冗余边界计算或没有实际循环体执行的外层迭代,因此暴露更多 DOALL 层数并不直接给出运行时间收益。(§VII,pp. 463–465)