多面体编译的循环分块

1）循环分块，是性能优化的重要步骤

2）

基于多面体模型的循环变换是程序自动并行化的热点，是解决程序自动并
行变换的一种有效手段。循环变换将循环的迭代空间表示成空间多面体，并通
过多面体上的几何操作达到分析和优化程序的目的。循环变换包括循环分块，
循环交换，循环倾斜，循环合并等。

3）

循环分块是提升高速缓存命中率的一种有效变换策略，通过将大块的循环
迭代拆解成若干较小的循环迭代块，减少内存单元的数据重用周期，进而减少
片外访存开销。在多面体模型中使用ISL 算法进行程序变换。使用一维stencil
计算实例来说明循环分块，如图3.2 所示为一维stencil 计算实例和原始迭代空间。

4）

这个不是二维Stencil吗？

图3.2 表示原始调度的空间多面体，图中每个黑点表示一次循环迭代，表示
一个语句实例，箭头表示循环迭代之间的依赖。沿i 轴方向上的循环迭代之间不
存在依赖。在?0(?, ?) −> (?, ?)方向上对循环索引变量分别进行循环分块，实际上
是在计算一个新的调度。通过2.1.2 节中调度变换算法对程序进行循环变换，得
到如图3.3 所示循环分块图。

论文写得很好，很清楚 。

5）

沿坐标轴方向进行分块会导致分块后分块之间依旧存在依赖，所以，沿着
左上方向进行循环分块，图3.3 中绿色部分为各个分块，该方法不会导致任意方
向相邻两个分块之间的依赖环，分块在左上方向为并行的。多面体编译优化通
过ISL 算法中循环分块等循环变换方法对程序进行重调度的计算，提高了数据
的局部性。

在调度变换后，对于计算出的具有并行性的循环，为了实现将程序映射到
块和线程这两个层次上，对循环索引变量进行分块来确保循环中至少有两级并
行性。例如图3.4 中的矩阵乘实例。

6）

测试示例：

PolyBench 中并行计算性能测试差的实例

为了挖掘程序中存在的并行性，在多面体编译中使用基于Pluto 算法的ISL
算法进行调度变换。将计算出的调度表示为调度树（Schedule Tree）的形式，调
度树的构造是一个整数仿射函数，规定了实例的执行顺序，这些仿射函数可以
组合成带节点，使用仿射调度将循环嵌套转换为可分块的并行循环，这样的并
行循环为一个并行带，并行带中对应调度维度的循环是并行的，一个带节点中
至少有一个循环是并行的。

7）

感谢《基于多面体模型的国产DCU源源编译优化技术研究_牛靖钰》