指令调度
指令调度（instruction scheduling）是一种代码优化手段，常见于优化编译器，其主要功能在于通过加强指令层级的并行运行，使得程序在拥有指令流水线的中央处理器上能够高效运行。换句话说，此手段力求以不改变程序运算结果的方式，完成以下任务：
其中流水线停顿主要由结构型冒险（受处理器的资源所限）、数据型冒险以及控制流型冒险导致。
数据型冒险
[编辑]指令调度一般在某基础块（basic block）上执行。为了确保指令的运行顺序在重组后，其运算结果依旧不变，编译器的开发者们必须要认识到数据依赖这种概念。数据型冒险总共有三种，其性质恰恰与数据型冒险相符，这三种数据冒险分别是：
- 写入后读取（RAW, Read After Write） - I1 的输出值之后会被 I2 使用。
- 读取后写入（WAR, Write After Read） - I1 的输入位置之后会被 I2 使用并覆盖。
- 写入后写入（WAW, Write After Write） - I1 以及 I2 皆将结果写入同一个位置上。
其中 I1 以及 I2 是两个在不同时间点上执行的指令。
对于这三种冒险，指令 I1 都必须执行于 I2 被执行前，否则其运算结果是不被定义的（具体结果视该机器的硬件实现而定）。对于冒险1，这是因为 I2 依赖着 I1 的数据；对于冒险2，则是因为 I1 依赖着即将被 I2 所覆盖的数据；对于冒险3，则是因为在 I1 和 I2 之间所运行的指令可能会使用到 I1 的输出结果。为了确保这些数据依赖所需的运行顺序得到保证，编译器首先需要建立一幅依赖图，即一幅顶点是指令，而边是依赖性的有向图。最终，这幅图的任何一种拓扑排序都可以是有效的指令调度表。
算法
[编辑]寻找拓扑排序最简单且常见的算法是列表调度法，其基本概念是不断将依赖图的某个源抽出，并将其添加到现有指令调度表上。在此过程中变成源的其他顶点，也会如前面所言被抽出并进行调度。当这幅依赖图为空时，算法便会结束。
在这种算法里，为了优化指令调度表的有效性，以减少流水线停顿等现象的发生频率，该算法所选择用于调度的下一条指令尤为重要。为此常用的启发式有：
- 将已调度指令所占用的处理器资源记录下来，若候选指令同样会占用这些资源，则降低其优先度。
- 若前指令的延迟（latency）高于前指令与候选指令的距离（即二者的周期差），则降其优先度。
- 当某候选指令坐落在依赖图中的某关键路径时，则提高其优先度。这使得这个算法拥有部分向前探查的功能，而不再寻找局部最优解。
- 如果候选指令能创造大量新源，则提高其优先度。这项启发式一般能提供调度器更多的调度自由。
执行次序
[编辑]指令调度可以在寄存器配置之前或之后进行，也可以在寄存器配置之前和之后进行。在寄存器配置前执行指令调度的好处是可以最大化程序的并行性，然而这种做法会有一定的代价，即代码的寄存器需求量可能会有所增加，而当这个需求量大于处理器所拥有的寄存器时，寄存器溢出便会随之产生，造成性能影响。
如果该处理器架构不允许某些特定的指令序列组合（一般由于缺乏跨指令互锁），则指令调度须在寄存器配置发生后才能执行。这种配置法同时也有助于寄存器溢出问题。
如果指令调度在寄存器配置后发生，指令排序可能因寄存器配置器产生的假依赖性而受到一定限制。
类型
[编辑]指令调度有几种类型，其中包括了：
- 本地（基本块）调度：指令仅能在其所在基础块内移动。
- 全局调度：指令能在各基础块内移动。
- 模算调度：属于一种软件流水线的生成算法，通过交叉运行不同的循环达到指令层级并行的效果。
- 跟踪调度：第一种真正实用的全局调度方法，编译器尽力优化最常被运行的代码控制流路。[1]
- 超块（superblock）调度： 跟踪调度的简化版。
参考
[编辑]- ^ Joseph A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Transactions on Computers. 1981-07, C–30 (7): 478–490. doi:10.1109/TC.1981.1675827.