指令級(jí)并行

指令流水

現(xiàn)代處理器大都采用了流水線的設(shè)計(jì)思想，將指令操作劃分為更多的階段，例如一條指令的執(zhí)行過程可以劃分為取指階段、譯碼階段、執(zhí)行階段、訪存階段、寫回階段這五個(gè)階段，每個(gè)階段分別在對(duì)應(yīng)的功能部件中完成，利用指令的重疊執(zhí)行來加速處理速度。

處理器內(nèi)部的流水線超過5至6級(jí)以上就可以稱為超級(jí)流水線，又叫做深度流水線。超級(jí)流水線對(duì)提升處理器的主頻有幫助，但流水線級(jí)數(shù)越多，同一時(shí)刻重疊執(zhí)行的指令就越多，可能會(huì)導(dǎo)致存在相關(guān)性的指令間發(fā)生沖突，造成處理器的高頻低能。指令間相關(guān)性會(huì)導(dǎo)致流水線停頓，如下：

結(jié)構(gòu)相關(guān)性是指兩條指令使用相同名字的寄存器或者儲(chǔ)存單元，并且兩條指令之間不存在數(shù)據(jù)的傳遞。輸出相關(guān)性是指令A(yù)和指令B對(duì)同一寄存器或存儲(chǔ)單元進(jìn)行寫操作。

結(jié)構(gòu)相關(guān)性包括反相關(guān)性和輸出相關(guān)性，反相關(guān)性是指指令A(yù)在程序中的位置位于指令B之前，指令B中操作數(shù)寫入的寄存器或存儲(chǔ)單元是指令A(yù)操作數(shù)讀的寄存器或存儲(chǔ)單元，如果將兩個(gè)指令調(diào)整執(zhí)行順序?qū)⒂绊懡Y(jié)果的正確性，例如以下指令片段：

反相關(guān)性：

mul? R1， R2， R3?? #指令A(yù)

sub? R4， R5， R1?? #指令B

輸出相關(guān)性：

mul? R1， R2， R3?? #指令A(yù)

sub? R4， R5， R3?? #指令B

除數(shù)據(jù)相關(guān)性以及結(jié)構(gòu)相關(guān)性之外，還存在某些指令的執(zhí)行受控于其它指令的情況，即指令間的控制相關(guān)，以下面的指令段為例：

bne? R1， R2， Label????? #指令1

add? R3， R4， R5??? ???? #指令2

mul? R5， R0， R6??? #指令3

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

指令2和指令3的執(zhí)行情況受控于指令1的執(zhí)行結(jié)果，當(dāng)指令1中R1和R2相等時(shí)不跳轉(zhuǎn)到Label，此時(shí)指令2和指令3會(huì)執(zhí)行；而當(dāng)指令1中R1和R2不相等時(shí)則直接跳轉(zhuǎn)到Label，此時(shí)指令2和指令3不會(huì)執(zhí)行。

控制相關(guān)使得指令的執(zhí)行順序不確定，因此會(huì)造成流水線的停頓。當(dāng)指令流水線上出現(xiàn)控制相關(guān)時(shí)，有兩種處理方法。等流水線上的指令執(zhí)行結(jié)束后，根據(jù)分支指令的執(zhí)行結(jié)果進(jìn)行跳轉(zhuǎn)，但會(huì)造成指令流水線的停頓。預(yù)測(cè)分支指令的結(jié)果，選擇某一條分支的指令填入流水線以避免流水線的停頓，如果分支預(yù)測(cè)正確流水線即可順利運(yùn)行，若分支預(yù)測(cè)錯(cuò)誤，則需要清空流水線丟棄已經(jīng)執(zhí)行的結(jié)果，并執(zhí)行正確的分支重新填充流水線。核心代碼內(nèi)含有較多的分支語句，將嚴(yán)重影響程序性能。

主流的編譯器中會(huì)嘗試破除指令的控制相關(guān)，但是一般僅對(duì)最內(nèi)層循環(huán)中的簡(jiǎn)單控制流結(jié)構(gòu)，對(duì)程序中形式復(fù)雜的控制相關(guān)語句則無能為力，因此優(yōu)化人員對(duì)代碼的優(yōu)化依然是提升程序性能的有效手段。

下方代碼段存在控制相關(guān)，可以采用控制語句外提的方法優(yōu)化改寫。將循環(huán)不變量的判斷條件控制語句外提到循環(huán)外，從而減少或消除循環(huán)內(nèi)的控制相關(guān)。

if控制語句外提不僅減少了循環(huán)的工作量并發(fā)掘出更多指令級(jí)并行性，甚至對(duì)后續(xù)的數(shù)據(jù)級(jí)并行等其它循環(huán)優(yōu)化都有利，但并不是所有的控制語句都能外提，只有當(dāng)該語句的判斷條件不隨循環(huán)迭代而改變時(shí)外提才是合法的

if外提后：

另一種處理控制相關(guān)的方法是控制轉(zhuǎn)換，即將控制相關(guān)轉(zhuǎn)為數(shù)據(jù)相關(guān)，通常將這種轉(zhuǎn)換方法稱為if轉(zhuǎn)換。

if轉(zhuǎn)換是指將程序中的條件分支語句及相關(guān)語句變換為順序執(zhí)行的條件賦值語句，從而把控制依賴轉(zhuǎn)換成數(shù)據(jù)依賴。

初始代碼：

if轉(zhuǎn)換后：

if轉(zhuǎn)換后，可以對(duì)條件語句進(jìn)行合并。If轉(zhuǎn)換后去除了指令中的控制相關(guān)，不僅避免了流水線的停頓，利于指令級(jí)并行，同時(shí)有利于程序的向量化、并行化等其它程序變換。以下面代碼為例說明轉(zhuǎn)換后對(duì)條件語句進(jìn)行合并的過程。

初始代碼：

if轉(zhuǎn)換后：

合并后: