指令级并行

指令流水

现代处理器大都采用了流水线的设计思想，将指令操作划分为更多的阶段，例如一条指令的执行过程可以划分为取指阶段、译码阶段、执行阶段、访存阶段、写回阶段这五个阶段，每个阶段分别在对应的功能部件中完成，利用指令的重叠执行来加速处理速度。

处理器内部的流水线超过5至6级以上就可以称为超级流水线，又叫做深度流水线。超级流水线对提升处理器的主频有帮助，但流水线级数越多，同一时刻重叠执行的指令就越多，可能会导致存在相关性的指令间发生冲突，造成处理器的高频低能。指令间相关性会导致流水线停顿，如下：

结构相关性是指两条指令使用相同名字的寄存器或者储存单元，并且两条指令之间不存在数据的传递。输出相关性是指令A和指令B对同一寄存器或存储单元进行写操作。

结构相关性包括反相关性和输出相关性，反相关性是指指令A在程序中的位置位于指令B之前，指令B中操作数写入的寄存器或存储单元是指令A操作数读的寄存器或存储单元，如果将两个指令调整执行顺序将影响结果的正确性，例如以下指令片段：

反相关性：

mul  R1， R2， R3   #指令A

sub  R4， R5， R1   #指令B

输出相关性：

mul  R1， R2， R3   #指令A

sub  R4， R5， R3   #指令B

除数据相关性以及结构相关性之外，还存在某些指令的执行受控于其它指令的情况，即指令间的控制相关，以下面的指令段为例：

bne  R1， R2， Label      #指令1

add  R3， R4， R5         #指令2

mul  R5， R0， R6    #指令3

Label: sub R1， R6， R6    #指令4

指令2和指令3的执行情况受控于指令1的执行结果，当指令1中R1和R2相等时不跳转到Label，此时指令2和指令3会执行；而当指令1中R1和R2不相等时则直接跳转到Label，此时指令2和指令3不会执行。

控制相关使得指令的执行顺序不确定，因此会造成流水线的停顿。当指令流水线上出现控制相关时，有两种处理方法。等流水线上的指令执行结束后，根据分支指令的执行结果进行跳转，但会造成指令流水线的停顿。预测分支指令的结果，选择某一条分支的指令填入流水线以避免流水线的停顿，如果分支预测正确流水线即可顺利运行，若分支预测错误，则需要清空流水线丢弃已经执行的结果，并执行正确的分支重新填充流水线。核心代码内含有较多的分支语句，将严重影响程序性能。

主流的编译器中会尝试破除指令的控制相关，但是一般仅对最内层循环中的简单控制流结构，对程序中形式复杂的控制相关语句则无能为力，因此优化人员对代码的优化依然是提升程序性能的有效手段。

下方代码段存在控制相关，可以采用控制语句外提的方法优化改写。将循环不变量的判断条件控制语句外提到循环外，从而减少或消除循环内的控制相关。

if控制语句外提不仅减少了循环的工作量并发掘出更多指令级并行性，甚至对后续的数据级并行等其它循环优化都有利，但并不是所有的控制语句都能外提，只有当该语句的判断条件不随循环迭代而改变时外提才是合法的

if外提后：

另一种处理控制相关的方法是控制转换，即将控制相关转为数据相关，通常将这种转换方法称为if转换。

if转换是指将程序中的条件分支语句及相关语句变换为顺序执行的条件赋值语句，从而把控制依赖转换成数据依赖。

初始代码：

if转换后：

if转换后，可以对条件语句进行合并。If转换后去除了指令中的控制相关，不仅避免了流水线的停顿，利于指令级并行，同时有利于程序的向量化、并行化等其它程序变换。以下面代码为例说明转换后对条件语句进行合并的过程。

初始代码：

if转换后：

合并后: