编译过程中的并行性优化（二）：基本块与全局代码调度算法

我的GIS/CS学习笔记：https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 >

上一篇：编译过程中的并行性优化（一）：概要

（浙江大学编译原理课程的课程报告）

基本块调度算法

基本块是连续三地址状态的最大序列，其中控制流只能在块的第一个语句中输入，并在最后一个语句中停留，而不会停止或分支。

对于一个由机器指令组成的基本块中的指令进行调度以获取最优解，这个时间复杂度是NP完全的。但在实践中，由于基本块之间的高度约束的运算较少，因此用简单的调度算法是可行的。这里介绍一个列表调度的算法。

数据依赖图

数据依赖图是调度算法中用到的一个重要工具。我们可以把每个由机器指令组成的基本块标识成为一个数据依赖图（data-dependence graph), G = (N,E)，其中节点集合N表示基本块中机器指令的运算，而有向边集合E表示运算之间的数据依赖约束。G的节点集合和边及可以按照如下方式构造：

1. 在N中的每个运算n为一个节点，有个资源预约表RTn，其值就是n的运算类型所对应的资源预约表；
2. E中的每条边e有一个表示延时的标号de，表明目标节点必须在源节点发出后至少de个时钟周期之后发出。

数据依赖图的实例如下：

列表调度算法

从数据依赖图和资源预约表就能清晰地看到指令之间的依赖关系，因此，我们可以采用简单的方法，即使用带优先级的拓扑排序访问数据依赖图的各个节点，就能得到基本块调度的顺序。换句话说，算法根据数据依赖图中每个节点和之前已调度的节点之间的数据依赖约束，计算出能执行该节点的最早时间位置。

• 输入：一个机器资源向量 R = [ r1, r2 ... ], 其中ri是第i种资源的可用单元数目；以及一个数据依赖图 G = (N,E)
• 输出：一个调度方案S, 将N中的每个运算映射到时间位置中。

算法伪代码：

列表调度算法不进行回溯，对每个节点只进行一次指令调度，并使用一个启发式的优先级函数函数从已就绪的节点中选择下一个调度的节点。它具有如下性质：

• 在不考虑资源约束的情况下，最短的调度方案根据关键路径给出；
• 如果运算都是独立的，调度方案的长度受到可用资源的约束；
• 可以使用源代码中的顺序决定运算之间难分先后的情况；

全局代码调度

为了更好地利用机器资源，我们还可以考虑将一些指令从一个基本块移动到另一个基本块的代码调度，这种策略就称为全局调度。为了正确地进行全局调度，除了数据依赖关系以外，我们也要考虑控制依赖关系。

我们需要保证以下两点才能进行调度：

1. 所有在源程序中执行的指令都会在优化后的程序中运行；
2. 额外投机执行的指令不能产生任何副作用；

基本代码移动

局部与全局代码调动的例子：

就像上述调度，在全局代码移动过程中，我们可以沿着一个执行路径上下移动指令。可以根据基本块之间的支配关系考虑指令移动的方式：

• 如果每个从控制流图入口处到达基本块B1的路径都经过一个基本块B2，那么就认为B2支配B1；
• 如果从基本块B1到达控制流图出口处的路径都经过B2，那么就认为B2反向支配B1；
• 如果B1支配B2且B2反向支配B1，则二者控制等价。

在一条路径上的一堆基本块之间可能支配关系和反向支配关系都不具有。

对于可能的全局代码移动方式，可以总结如下：

• 在控制等价的基本块之间移动指令最简单且性价比最高；
• 在沿着控制流路径向上（向下）的代码移动中，如果源基本块不反向支配（支配）目标基本块，可能需要执行额外的运算；
• 在沿着控制流路径向上（向下）的代码移动中，如果目标基本块不支配（反向支配）源基本块，就可能需要补偿一些相应的代码；
• 如果在沿着控制流路径向上（向下）的代码移动中，源和目的基本块之中既不支配，也不反向支配，那么可能既需要需要执行额外的运算又需要补偿一些相应的代码。

同时，代码移动可能也会改变运算之间的数据依赖关系，因此每次代码移动之后都必须更新它。

全局调动算法

• 基于区域的调度算法： 区域是一个控制流图的子集，它只能ton过一个入口基本块到达。对于一个简单的全局调度器，可以采用基于区域的调度算法，它支持吧运算向上移动到控制等价的基本块，或把运算向上移动一个分支，到一个支配前驱中：
  • 输入：一个控制流图和一个机器资源描述
  • 输出：一个调度方案S
  • 伪代码：

• 循环展开： 在代码调度前少量地展开循环可以增加代码移动的可能性，进而增加并行性，如下所示：

• 相邻压缩： 在基于区域的调度后可以再跟一个简单的代码处理过程，在这个过程中检查各对相邻的连续执行的基本块是否有运算可以在他们之间上移或下移，以改进它们的执行时间。

动态调度

如果编程语言支持动态调度器，即可以根据运行时刻的情况产生新的调度方案，而不需要在运行之前对于所有的可能调度进行编码，就能获得更好的优化方案。

知识点总结：

• 基本块的数据依赖图
• 带优先级的拓扑排序
• 列表调度
• 基本块之间的代码移动

参考资料

• 《编译原理》第二版，第十章、第十一章

我的GIS/CS学习笔记：https://github.com/yunwei37/myClassNotes <一个浙大GIS/CS小白的课程学习笔记 >