指令调度:修订间差异
修正链接 |
内容扩充(Phase Order - 执行次序) |
||
第15行: | 第15行: | ||
对于这三种冒险,指令 '''I<sub>1</sub>''' 都必须执行于 '''I<sub>2</sub>''' 被执行前,否则其运算结果是不被定义的(具体结果视该机器的硬件实现而定)。对于冒险1,这是因为 '''I<sub>2</sub>''' 依赖着 '''I<sub>1</sub>''' 的数据;对于冒险2,则是因为 '''I<sub>1</sub>''' 依赖着即将被 '''I<sub>2</sub>''' 所覆盖的数据;对于冒险3,则是因为在 '''I<sub>1</sub>''' 和 '''I<sub>2</sub>''' 之间所运行的指令可能会使用到 '''I<sub>1</sub>''' 的输出结果。为了确保这些数据依赖所需的运行顺序得到保证,编译器首先需要建立一幅依赖图,即一幅[[顶点_(图论)|顶点]]是指令,而[[边_(图论)|边]]是依赖性的有向图。最终,这幅图的任何一种[[拓扑排序]]都可以是有效的指令调度表。 |
对于这三种冒险,指令 '''I<sub>1</sub>''' 都必须执行于 '''I<sub>2</sub>''' 被执行前,否则其运算结果是不被定义的(具体结果视该机器的硬件实现而定)。对于冒险1,这是因为 '''I<sub>2</sub>''' 依赖着 '''I<sub>1</sub>''' 的数据;对于冒险2,则是因为 '''I<sub>1</sub>''' 依赖着即将被 '''I<sub>2</sub>''' 所覆盖的数据;对于冒险3,则是因为在 '''I<sub>1</sub>''' 和 '''I<sub>2</sub>''' 之间所运行的指令可能会使用到 '''I<sub>1</sub>''' 的输出结果。为了确保这些数据依赖所需的运行顺序得到保证,编译器首先需要建立一幅依赖图,即一幅[[顶点_(图论)|顶点]]是指令,而[[边_(图论)|边]]是依赖性的有向图。最终,这幅图的任何一种[[拓扑排序]]都可以是有效的指令调度表。 |
||
==执行次序== |
|||
指令调度可以在[[寄存器配置]]之前或之后进行,也可以在寄存器配置之前和之后进行。在寄存器配置前执行指令调度的好处是可以最大化程序的并行性,然而这种做法会有一定的代价,即代码的[[寄存器]]需求量可能会有所增加,而当这个需求量大于处理器所拥有的寄存器时,[[寄存器配置#溢出|寄存器溢出]]便会随之产生,造成性能影响。 |
|||
如果该处理器架构不允许某些特定的指令序列组合(一般由于缺乏跨指令互锁),则指令调度须在寄存器配置发生后才能执行。这种配置法同时也有助于寄存器溢出问题。 |
|||
如果指令调度在寄存器配置后发生,指令排序可能因寄存器配置器产生的假依赖性而受到一定限制。 |
|||
==类型== |
==类型== |
2020年5月2日 (六) 11:16的版本
此條目可参照英語維基百科相應條目来扩充。 (2020年4月24日) |
此條目没有列出任何参考或来源。 (2020年4月24日) |
指令调度(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 的输出结果。为了确保这些数据依赖所需的运行顺序得到保证,编译器首先需要建立一幅依赖图,即一幅顶点是指令,而边是依赖性的有向图。最终,这幅图的任何一种拓扑排序都可以是有效的指令调度表。
执行次序
指令调度可以在寄存器配置之前或之后进行,也可以在寄存器配置之前和之后进行。在寄存器配置前执行指令调度的好处是可以最大化程序的并行性,然而这种做法会有一定的代价,即代码的寄存器需求量可能会有所增加,而当这个需求量大于处理器所拥有的寄存器时,寄存器溢出便会随之产生,造成性能影响。
如果该处理器架构不允许某些特定的指令序列组合(一般由于缺乏跨指令互锁),则指令调度须在寄存器配置发生后才能执行。这种配置法同时也有助于寄存器溢出问题。
如果指令调度在寄存器配置后发生,指令排序可能因寄存器配置器产生的假依赖性而受到一定限制。
类型
指令调度有几种类型,其中包括了:
- 本地(基础块)调度:指令仅能在其所在基础块内移动。
- 全局调度:指令能在各基础块内移动。
- 模算调度:属于一种软件流水线的生成算法,通过交叉运行不同的循环达到指令层级并行的效果。
- 跟踪调度:第一种真正实用的全局调度方法,编译器尽力优化最常被运行的代码控制流路。
- 超块(superblock)调度: 跟踪调度的简化版。