41指令級并行的概念課件

4.1 指令級并行的概念當(dāng)指令之間不存在相關(guān)時，它們在流水線中是可以重疊起來并行執(zhí)行的。這種指令序列中存在的潛在并行性稱為指令級并行。（Instruction-LevelParallelism，簡記為ILP）本章研究：如何通過各種可能的技術(shù)，獲得更多的指令級并行性。

（硬件技術(shù)和軟件技術(shù)）必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖掘出程序中存在的指令級并行。第四章指令級并行4.1 指令級并行的概念當(dāng)指令之間不存在相關(guān)時，它們在流水線1.流水線處理器的實際CPICPI流水線=CPI理想+各類停頓周期數(shù)的總和流水線的理想CPI是流水線的最大流量。各類停頓包括：結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一個功能部件而導(dǎo)致的停頓?？刂葡嚓P(guān)停頓：是由于指令流的改變（如分支指令）而導(dǎo)致的停頓。RAW、WAR和WAW停頓：由數(shù)據(jù)相關(guān)造成的。減少其中的任何一種停頓，都可以有效地減少CPI，從而提高流水線的性能。4.1指令級并行的概念1.流水線處理器的實際CPICPI流水線=CPI理想+2.本章要研究的技術(shù)以及它們所克服的停頓技術(shù)主要克服的停頓章節(jié)基本流水線調(diào)度數(shù)據(jù)先寫后讀相關(guān)停頓4.1循環(huán)展開控制相關(guān)停頓4.1寄存器換名數(shù)據(jù)寫后寫相關(guān)和先讀后寫相關(guān)停頓4.1指令動態(tài)調(diào)度（記分牌和Tomasulo算法）各種數(shù)據(jù)相關(guān)停頓 4.2動態(tài)分支預(yù)測控制相關(guān)停頓4.3前瞻（Speculation）所有數(shù)據(jù)/控制相關(guān)停頓4.3多指令流出（超標量和超長指令字）提高理想CPI4.44.1指令級并行的概念2.本章要研究的技術(shù)以及它們所克服的停頓技術(shù)主要克服的停頓3.幾個概念基本程序塊一段除了入口和出口以外不包含其它分支的線性代碼段。程序平均每6～7條指令就會有一個分支。循環(huán)體中指令之間的并行性稱為循環(huán)級并行性。開發(fā)循環(huán)體中存在的并行性。

最常見、最基本是指令級并行研究的重點之一。4.1指令級并行的概念3.幾個概念基本程序塊4.1指令級并行的概念最基本的開發(fā)循環(huán)級并行的技術(shù)指令調(diào)度（scheduling）技術(shù)循環(huán)展開（loopunrolling）技術(shù)換名（renaming）技術(shù)4.1指令級并行的概念最基本的開發(fā)循環(huán)級并行的技術(shù)4.1指令級并行的概念4.1.1 循環(huán)展開調(diào)度的基本方法1.指令調(diào)度通過改變指令在程序中的位置，將相關(guān)指令之間的距離加大到不小于指令執(zhí)行延遲，將相關(guān)指令轉(zhuǎn)化為無關(guān)指令。

指令調(diào)度是循環(huán)展開的技術(shù)基礎(chǔ)。2.編譯器在完成這種指令調(diào)度時，受限于以下兩個特性：程序固有的指令級并行性流水線功能部件的執(zhí)行延遲4.1指令級并行的概念4.1.1 循環(huán)展開調(diào)度的基本方法1.指令調(diào)度程序固有的3.本章使用的浮點流水線的延遲產(chǎn)生結(jié)果指令使用結(jié)果指令延遲時鐘周期數(shù)浮點計算另外的浮點計算3浮點計算浮點數(shù)據(jù)存操作（SD）2浮點數(shù)據(jù)取操作（LD）浮點計算1浮點數(shù)據(jù)取操作（LD）浮點數(shù)據(jù)存操作（SD）04.1指令級并行的概念3.本章使用的浮點流水線的延遲產(chǎn)生結(jié)果指令使用結(jié)果指令延遲例4.1

對于下面的源代碼，轉(zhuǎn)換成DLX匯編語言，在不進行指令調(diào)度和進行指令調(diào)度兩種情況下，分析代碼一次循環(huán)的執(zhí)行時間。for(i=1;i<=1000;i++) x[i]=x[i]+s;4.1指令級并行的概念例4.14.1指令級并行的概念解：(1)

變量分配寄存器整數(shù)寄存器R1：循環(huán)計數(shù)器，初值為向量中最高端地址元素的地址。浮點寄存器F2：保存常數(shù)S。假定最低端元素的地址為8。(2)

DLX匯編語言后的程序Loop: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop 4.1指令級并行的概念解：(1)變量分配寄存器4.1指令級并行的概念(3)程序執(zhí)行的實際時鐘根據(jù)表4-2中給出的的延遲，實際時鐘如下：

指令流出時鐘Loop:LD F0,0(R1) 1 （空轉(zhuǎn)） 2 ADDDF4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD 0(R1),F4 6 SUBI R1,R1,#8 7 （空轉(zhuǎn)） 8 BNEZR1,Loop 9 （空轉(zhuǎn)） 10每個元素的操作需要10個時鐘周期，其中5個是空轉(zhuǎn)周期。4.1指令級并行的概念(3)程序執(zhí)行的實際時鐘根據(jù)表4-2中給出的的延遲，實際時(4)指令調(diào)度以后，程序的執(zhí)行情況SD放在分支指令的分支延遲槽中對存儲器地址偏移量進行調(diào)整

指令流出時鐘Loop:LDF0,0(R1) 1 SUBIR1,R1,#8 2 ADDDF4,F0,F2 3 （空轉(zhuǎn)） 4 BNEZR1,Loop 5 SD 8(R1),F4 6一個元素的操作時間從10個時鐘周期減少到6個5個周期是有指令執(zhí)行的，1個空轉(zhuǎn)周期。4.1指令級并行的概念(4)指令調(diào)度以后，程序的執(zhí)行情況SD放在分支指令的分支延(5)例子中的問題及解決方案只有LD、ADDD和SD這3條指令是有效操作.占用3個時鐘周期而SUBI、空轉(zhuǎn)和BENZ這3個時鐘周期都是附加的循環(huán)控制開銷。循環(huán)展開技術(shù)多次復(fù)制循環(huán)體并相應(yīng)調(diào)整展開后的指令和循環(huán)結(jié)束條件，增加有效操作時間與控制操作時間的比率。也給編譯器進行指令調(diào)度帶來了更大的空間。4.1指令級并行的概念(5)例子中的問題及解決方案只有LD、ADDD和SD這3條例4.2體現(xiàn)循環(huán)展開技術(shù)的特點將例4.1中的循環(huán)展開成3次得到4個循環(huán)體，再對展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。假定R1的初值為32的倍數(shù)，即循環(huán)次數(shù)為4的倍數(shù)。4.1指令級并行的概念例4.2體現(xiàn)循環(huán)展開技術(shù)的特點將例4.1中的解：補償代碼問題寄存器分配展開后的循環(huán)體內(nèi)不重復(fù)使用寄存器。F0、F4：用于展開后的第1個循環(huán)體F2：保存常數(shù)F6和F8：用于展開后的第2個循環(huán)體F10和F12：用于第3個循環(huán)體F14和F16：用于第4個循環(huán)體4.1指令級并行的概念解：補償代碼問題4.1指令級并行的概念(1)展開后沒有調(diào)度的代碼

流出時鐘Loop: LD F0,0(R1) 1 （空轉(zhuǎn)） 2 ADDD F4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD 0(R1),F4 6 LD F6,-8(R1) 7 （空轉(zhuǎn)） 8 ADDD F8,F6,F2 9 （空轉(zhuǎn)） 10 （空轉(zhuǎn)） 11 SD -8(R1),F8 12 LD F10,-16(R1)13 （空轉(zhuǎn)） 14

流出時鐘 ADDD F12,F10,F2 15 （空轉(zhuǎn)） 16 （空轉(zhuǎn)） 17 SD -16(R1),F12 18 LD F14,-24(R1)19 （空轉(zhuǎn)） 20 ADDD F16,F14,F2 21 （空轉(zhuǎn)） 22 （空轉(zhuǎn)） 23 SD -24(R1),F1624 SUBI R1,R1,#32 25 （空轉(zhuǎn)） 26 BNEZ R1,Loop 27 （空轉(zhuǎn)） 284.1指令級并行的概念(1)展開后沒有調(diào)度的代碼 流出時鐘 流出時鐘4.結(jié)果分析:這個循環(huán)每遍共使用了28個時鐘周期有4個循環(huán)體，完成4個元素的操作平均每個元素使用28/4=7個時鐘周期原始循環(huán)的每個元素需要10個時鐘周期節(jié)省的時間:從減少循環(huán)控制的開銷中獲得的在整個展開后的循環(huán)中，實際指令只有14條，其它13個周期都是空轉(zhuǎn)。效率并不高4.1指令級并行的概念結(jié)果分析:這個循環(huán)每遍共使用了28個時鐘周期4.1指令級并(2)對指令序列進行優(yōu)化調(diào)度

指令流出時鐘Loop: LD F0,0(R1) 1 LD F6,-8(R1) 2 LD F10,-16(R1) 3 LD F14,-24(R1) 4 ADDD F4,F0,F2 5 ADDD F8,F6,F2 6 ADDD F12,F10,F2 7 ADDD F16,F14,F2 8 SD 0(R1),F4 9 SD -8(R1),F8 10 SUBI R1,R1,#32 12 SD 16(R1),F12 11 BNEZ R1,Loop 13 SD 8(R1),F16 144.1指令級并行的概念(2)對指令序列進行優(yōu)化調(diào)度 指令流出時鐘4.1指結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待整個循環(huán)僅僅使用了14個時鐘周期平均每個元素的操作使用14/4=3.5個時鐘周期循環(huán)展開和指令調(diào)度可以有效地提高循環(huán)級并行性。這種循環(huán)級并行性的提高實際是通過實現(xiàn)指令級并行來達到的?？梢允褂镁幾g器來完成，也可以通過硬件來完成。4.1指令級并行的概念結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待4.1指令級并行的概念4.循環(huán)展開和指令調(diào)度時要注意的問題(1)保證正確性(2)注意有效性(3)使用不同的寄存器(4)盡可能減少循環(huán)控制中的測試指令和分支指令(5)注意對存儲器數(shù)據(jù)的相關(guān)性分析(6)注意新的相關(guān)性5.實現(xiàn)循環(huán)展開的關(guān)鍵

分析清楚代碼中指令的相關(guān)性，然后通過指令調(diào)度來消除相關(guān).4.1指令級并行的概念4.循環(huán)展開和指令調(diào)度時要注意的問題(1)保證正確性5.4.1.2相關(guān)性開發(fā)指令級并行的關(guān)鍵存在相關(guān)的兩條指令，不能改變它們的順序。相關(guān)是否導(dǎo)致流水線的空轉(zhuǎn)，還與流水線的組織與結(jié)構(gòu)有關(guān)。程序中的相關(guān)主要有以下三種

數(shù)據(jù)相關(guān)

名相關(guān)

控制相關(guān)4.1指令級并行的概念4.1.2相關(guān)性開發(fā)指令級并行的關(guān)鍵數(shù)據(jù)相關(guān)4.1指令1.數(shù)據(jù)相關(guān)（datadependence）對于指令i和指令j，如果(1)指令j使用指令i產(chǎn)生的結(jié)果，或者(2)指令j與指令k數(shù)據(jù)相關(guān)，指令k與指令i數(shù)據(jù)相關(guān)，則指令j與指令i數(shù)據(jù)相關(guān)。

數(shù)據(jù)相關(guān)具有傳遞性。數(shù)據(jù)相關(guān)是兩條指令之間存在一個先寫后讀相關(guān)鏈。相關(guān)鏈貫穿整個程序，是程序的內(nèi)在特征。這種相關(guān)鏈是導(dǎo)致流水線停頓的原因之一。4.1指令級并行的概念1.數(shù)據(jù)相關(guān)（datadependence）對于指令i和指令的相關(guān)距離（distance）兩條指令之間的指令條數(shù)。分析數(shù)據(jù)相關(guān)的主要工作:(1)確定指令的相關(guān)性，找到所有可能產(chǎn)生停頓的地方。(2)確定必須嚴格遵守的數(shù)據(jù)的計算順序。(3)確定指令的最大相關(guān)距離，確定程序中可

能的最大并行性。4.1指令級并行的概念指令的相關(guān)距離（distance）4.1指令級并行的概念2.名相關(guān)（namedependence）指令使用的寄存器或存儲器稱為名。如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流，則稱之為名相關(guān)。指令j與指令i之間名相關(guān)有以下兩種：(1)反相關(guān)（anti-dependence）(2)輸出相關(guān)（outputdependence）4.1指令級并行的概念2.名相關(guān)（namedependence）指令使用的寄存消除名相關(guān)名相關(guān)的指令之間沒有數(shù)據(jù)交換。如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。通過改變指令中操作數(shù)的名來消除名相關(guān)，這就是換名（renaming）技術(shù)。對于寄存器操作數(shù)進行換名稱為寄存器換名。

（registerrenaming）可以用編譯器靜態(tài)完成或硬件動態(tài)完成。4.1指令級并行的概念消除名相關(guān)名相關(guān)的指令之間沒有數(shù)據(jù)交換。4.1指令級并行例：我們對例4.2編譯過程進行分析，來仔細考察

換名的過程。

(1)首先，僅僅去除4遍循環(huán)體中的分支指令，

得到以下由17條指令構(gòu)成的指令序列：4.1指令級并行的概念例：我們對例4.2編譯過程進行分析，來仔細考察

換名Loop:LDF0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,R1,#8 LD F0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,R1,#8 LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop4.1指令級并行的概念 LD F0,0(R1)4.1指令級并行的概念(2)編譯器可以通過對相關(guān)鏈上存儲器訪問偏移量的直接調(diào)整，將前3條SUBI指令消除掉，從而得到下面一個14條指令構(gòu)成的指令序列：

4.1指令級并行的概念(2)編譯器可以通過對相關(guān)鏈上存儲器訪問偏移量的直接Loop: LD F0,0(R1) ADDDF4,F0,F2

SD 0(R1),F4 LD F0,-8(R1) ADDDF4,F0,F2 SD -8(R1),F4 LD F0,-16(R1) ADDDF4,F0,F2

SD -16(R1),F4 LD F0,-24(R1) ADDD F4,F0,F2 SD -24(R1),F4 SUBIR1,R1,#32 BNEZR1,Loop4.1指令級并行的概念Loop: LD F0,0(R1)4(3)通過寄存器換名，消除名相關(guān)。得到右邊的指令序列：Loop: LD F0,0(R1) ADDD F4,F0,F2

SD 0(R1),F4 LD F6,-8(R1) ADDD F8,F6,F2 SD -8(R1),F8 LD F10,-16(R1) ADDD F12,F10,F2

SD -16(R1),F12 LD F14,-24(R1) ADDD F16,F14,F2 SD -24(R1),F16 SUBI R1,R1,#32 BNEZ R1,Loop換名操作需要較大的寄存器開銷。4.1指令級并行的概念(3)通過寄存器換名，消除名相關(guān)。Loop: LD F03．控制相關(guān)（controldependence）

控制相關(guān)是指由分支指令引起的相關(guān)。典型的程序結(jié)構(gòu)是“if-then”結(jié)構(gòu)?？聪旅嬉粋€示例：

ifp1{ S1;};S;ifp2{ S2;};4.1指令級并行的概念3．控制相關(guān)（controldependence）

控制處理控制相關(guān)的兩個原則：(1)與控制相關(guān)的指令不能移到分支指令之前，即控制有關(guān)的指令不能調(diào)度到分支指令控制范圍以外；(2)與控制無關(guān)的指令不能移到分支指令之后，即控制無關(guān)的指令不能調(diào)度到分支指令控制范圍以內(nèi)。4.1指令級并行的概念處理控制相關(guān)的兩個原則：4.1指令級并行的概念再考察例4.2：假設(shè)循環(huán)展開時，循環(huán)控制分支指令沒有去除，則指令序列如下：4.1指令級并行的概念再考察例4.2：4.1指令級并行的概念Loop:LD F0,0(R1) ADDD F4,F0,F2

SD 0(R1),F4 SUBI R1,R1,#8 BEQZ R1,Exit LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4

SUBI R1,R1,#8 BEQZ R1,ExitLD F0,0(R1) ADDD F4,F0,F2

SD 0(R1),F4 SUBI R1,R1,#8 BEQZ R1,Exit LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4

SUBI R1,R1,#8 BNEZ R1,LoopExit:

4.1指令級并行的概念Loop:LD F0,0(R1)L4.1 指令級并行的概念當(dāng)指令之間不存在相關(guān)時，它們在流水線中是可以重疊起來并行執(zhí)行的。這種指令序列中存在的潛在并行性稱為指令級并行。（Instruction-LevelParallelism，簡記為ILP）本章研究：如何通過各種可能的技術(shù)，獲得更多的指令級并行性。

（硬件技術(shù)和軟件技術(shù)）必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖掘出程序中存在的指令級并行。第四章指令級并行4.1 指令級并行的概念當(dāng)指令之間不存在相關(guān)時，它們在流水線1.流水線處理器的實際CPICPI流水線=CPI理想+各類停頓周期數(shù)的總和流水線的理想CPI是流水線的最大流量。各類停頓包括：結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一個功能部件而導(dǎo)致的停頓?？刂葡嚓P(guān)停頓：是由于指令流的改變（如分支指令）而導(dǎo)致的停頓。RAW、WAR和WAW停頓：由數(shù)據(jù)相關(guān)造成的。減少其中的任何一種停頓，都可以有效地減少CPI，從而提高流水線的性能。4.1指令級并行的概念1.流水線處理器的實際CPICPI流水線=CPI理想+2.本章要研究的技術(shù)以及它們所克服的停頓技術(shù)主要克服的停頓章節(jié)基本流水線調(diào)度數(shù)據(jù)先寫后讀相關(guān)停頓4.1循環(huán)展開控制相關(guān)停頓4.1寄存器換名數(shù)據(jù)寫后寫相關(guān)和先讀后寫相關(guān)停頓4.1指令動態(tài)調(diào)度（記分牌和Tomasulo算法）各種數(shù)據(jù)相關(guān)停頓 4.2動態(tài)分支預(yù)測控制相關(guān)停頓4.3前瞻（Speculation）所有數(shù)據(jù)/控制相關(guān)停頓4.3多指令流出（超標量和超長指令字）提高理想CPI4.44.1指令級并行的概念2.本章要研究的技術(shù)以及它們所克服的停頓技術(shù)主要克服的停頓3.幾個概念基本程序塊一段除了入口和出口以外不包含其它分支的線性代碼段。程序平均每6～7條指令就會有一個分支。循環(huán)體中指令之間的并行性稱為循環(huán)級并行性。開發(fā)循環(huán)體中存在的并行性。

最常見、最基本是指令級并行研究的重點之一。4.1指令級并行的概念3.幾個概念基本程序塊4.1指令級并行的概念最基本的開發(fā)循環(huán)級并行的技術(shù)指令調(diào)度（scheduling）技術(shù)循環(huán)展開（loopunrolling）技術(shù)換名（renaming）技術(shù)4.1指令級并行的概念最基本的開發(fā)循環(huán)級并行的技術(shù)4.1指令級并行的概念4.1.1 循環(huán)展開調(diào)度的基本方法1.指令調(diào)度通過改變指令在程序中的位置，將相關(guān)指令之間的距離加大到不小于指令執(zhí)行延遲，將相關(guān)指令轉(zhuǎn)化為無關(guān)指令。

指令調(diào)度是循環(huán)展開的技術(shù)基礎(chǔ)。2.編譯器在完成這種指令調(diào)度時，受限于以下兩個特性：程序固有的指令級并行性流水線功能部件的執(zhí)行延遲4.1指令級并行的概念4.1.1 循環(huán)展開調(diào)度的基本方法1.指令調(diào)度程序固有的3.本章使用的浮點流水線的延遲產(chǎn)生結(jié)果指令使用結(jié)果指令延遲時鐘周期數(shù)浮點計算另外的浮點計算3浮點計算浮點數(shù)據(jù)存操作（SD）2浮點數(shù)據(jù)取操作（LD）浮點計算1浮點數(shù)據(jù)取操作（LD）浮點數(shù)據(jù)存操作（SD）04.1指令級并行的概念3.本章使用的浮點流水線的延遲產(chǎn)生結(jié)果指令使用結(jié)果指令延遲例4.1

對于下面的源代碼，轉(zhuǎn)換成DLX匯編語言，在不進行指令調(diào)度和進行指令調(diào)度兩種情況下，分析代碼一次循環(huán)的執(zhí)行時間。for(i=1;i<=1000;i++) x[i]=x[i]+s;4.1指令級并行的概念例4.14.1指令級并行的概念解：(1)

變量分配寄存器整數(shù)寄存器R1：循環(huán)計數(shù)器，初值為向量中最高端地址元素的地址。浮點寄存器F2：保存常數(shù)S。假定最低端元素的地址為8。(2)

DLX匯編語言后的程序Loop: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop 4.1指令級并行的概念解：(1)變量分配寄存器4.1指令級并行的概念(3)程序執(zhí)行的實際時鐘根據(jù)表4-2中給出的的延遲，實際時鐘如下：

指令流出時鐘Loop:LD F0,0(R1) 1 （空轉(zhuǎn)） 2 ADDDF4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD 0(R1),F4 6 SUBI R1,R1,#8 7 （空轉(zhuǎn)） 8 BNEZR1,Loop 9 （空轉(zhuǎn)） 10每個元素的操作需要10個時鐘周期，其中5個是空轉(zhuǎn)周期。4.1指令級并行的概念(3)程序執(zhí)行的實際時鐘根據(jù)表4-2中給出的的延遲，實際時(4)指令調(diào)度以后，程序的執(zhí)行情況SD放在分支指令的分支延遲槽中對存儲器地址偏移量進行調(diào)整

指令流出時鐘Loop:LDF0,0(R1) 1 SUBIR1,R1,#8 2 ADDDF4,F0,F2 3 （空轉(zhuǎn)） 4 BNEZR1,Loop 5 SD 8(R1),F4 6一個元素的操作時間從10個時鐘周期減少到6個5個周期是有指令執(zhí)行的，1個空轉(zhuǎn)周期。4.1指令級并行的概念(4)指令調(diào)度以后，程序的執(zhí)行情況SD放在分支指令的分支延(5)例子中的問題及解決方案只有LD、ADDD和SD這3條指令是有效操作.占用3個時鐘周期而SUBI、空轉(zhuǎn)和BENZ這3個時鐘周期都是附加的循環(huán)控制開銷。循環(huán)展開技術(shù)多次復(fù)制循環(huán)體并相應(yīng)調(diào)整展開后的指令和循環(huán)結(jié)束條件，增加有效操作時間與控制操作時間的比率。也給編譯器進行指令調(diào)度帶來了更大的空間。4.1指令級并行的概念(5)例子中的問題及解決方案只有LD、ADDD和SD這3條例4.2體現(xiàn)循環(huán)展開技術(shù)的特點將例4.1中的循環(huán)展開成3次得到4個循環(huán)體，再對展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。假定R1的初值為32的倍數(shù)，即循環(huán)次數(shù)為4的倍數(shù)。4.1指令級并行的概念例4.2體現(xiàn)循環(huán)展開技術(shù)的特點將例4.1中的解：補償代碼問題寄存器分配展開后的循環(huán)體內(nèi)不重復(fù)使用寄存器。F0、F4：用于展開后的第1個循環(huán)體F2：保存常數(shù)F6和F8：用于展開后的第2個循環(huán)體F10和F12：用于第3個循環(huán)體F14和F16：用于第4個循環(huán)體4.1指令級并行的概念解：補償代碼問題4.1指令級并行的概念(1)展開后沒有調(diào)度的代碼

流出時鐘Loop: LD F0,0(R1) 1 （空轉(zhuǎn)） 2 ADDD F4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD 0(R1),F4 6 LD F6,-8(R1) 7 （空轉(zhuǎn)） 8 ADDD F8,F6,F2 9 （空轉(zhuǎn)） 10 （空轉(zhuǎn)） 11 SD -8(R1),F8 12 LD F10,-16(R1)13 （空轉(zhuǎn)） 14

流出時鐘 ADDD F12,F10,F2 15 （空轉(zhuǎn)） 16 （空轉(zhuǎn)） 17 SD -16(R1),F12 18 LD F14,-24(R1)19 （空轉(zhuǎn)） 20 ADDD F16,F14,F2 21 （空轉(zhuǎn)） 22 （空轉(zhuǎn)） 23 SD -24(R1),F1624 SUBI R1,R1,#32 25 （空轉(zhuǎn)） 26 BNEZ R1,Loop 27 （空轉(zhuǎn)） 284.1指令級并行的概念(1)展開后沒有調(diào)度的代碼 流出時鐘 流出時鐘4.結(jié)果分析:這個循環(huán)每遍共使用了28個時鐘周期有4個循環(huán)體，完成4個元素的操作平均每個元素使用28/4=7個時鐘周期原始循環(huán)的每個元素需要10個時鐘周期節(jié)省的時間:從減少循環(huán)控制的開銷中獲得的在整個展開后的循環(huán)中，實際指令只有14條，其它13個周期都是空轉(zhuǎn)。效率并不高4.1指令級并行的概念結(jié)果分析:這個循環(huán)每遍共使用了28個時鐘周期4.1指令級并(2)對指令序列進行優(yōu)化調(diào)度

指令流出時鐘Loop: LD F0,0(R1) 1 LD F6,-8(R1) 2 LD F10,-16(R1) 3 LD F14,-24(R1) 4 ADDD F4,F0,F2 5 ADDD F8,F6,F2 6 ADDD F12,F10,F2 7 ADDD F16,F14,F2 8 SD 0(R1),F4 9 SD -8(R1),F8 10 SUBI R1,R1,#32 12 SD 16(R1),F12 11 BNEZ R1,Loop 13 SD 8(R1),F16 144.1指令級并行的概念(2)對指令序列進行優(yōu)化調(diào)度 指令流出時鐘4.1指結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待整個循環(huán)僅僅使用了14個時鐘周期平均每個元素的操作使用14/4=3.5個時鐘周期循環(huán)展開和指令調(diào)度可以有效地提高循環(huán)級并行性。這種循環(huán)級并行性的提高實際是通過實現(xiàn)指令級并行來達到的?？梢允褂镁幾g器來完成，也可以通過硬件來完成。4.1指令級并行的概念結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待4.1指令級并行的概念4.循環(huán)展開和指令調(diào)度時要注意的問題(1)保證正確性(2)注意有效性(3)使用不同的寄存器(4)盡可能減少循環(huán)控制中的測試指令和分支指令(5)注意對存儲器數(shù)據(jù)的相關(guān)性分析(6)注意新的相關(guān)性5.實現(xiàn)循環(huán)展開的關(guān)鍵

分析清楚代碼中指令的相關(guān)性，然后通過指令調(diào)度來消除相關(guān).4.1指令級并行的概念4.循環(huán)展開和指令調(diào)度時要注意的問題(1)保證正確性5.4.1.2相關(guān)性開發(fā)指令級并行的關(guān)鍵存在相關(guān)的兩條指令，不能改變它們的順序。相關(guān)是否導(dǎo)致流水線的空轉(zhuǎn)，還與流水線的組織與結(jié)構(gòu)有關(guān)。程序中的相關(guān)主要有以下三種

數(shù)據(jù)相關(guān)

名相關(guān)

控制相關(guān)4.1指令級并行的概念4.1.2相關(guān)性開發(fā)指令級并行的關(guān)鍵數(shù)據(jù)相關(guān)4.1指令1.數(shù)據(jù)相關(guān)（datadependence）對于指令i和指令j，如果(1)指令j使用指令i產(chǎn)生的結(jié)果，或者(2)指令j與指令k數(shù)據(jù)相關(guān)，指令k與指令i數(shù)據(jù)相關(guān)，則指令j與指令i數(shù)據(jù)相關(guān)。

數(shù)據(jù)相關(guān)具有傳遞性。數(shù)據(jù)相關(guān)是兩條指令之間存在一個先寫后讀相關(guān)鏈。相關(guān)鏈貫穿整個程序，是程序的內(nèi)在特征。這種相關(guān)鏈是導(dǎo)致流水線停頓的原因之一。4.1指令級并行的概念1.數(shù)據(jù)相關(guān)（datadependence）對于指令i和指令的相關(guān)距離（distance）兩條指令之間的指令條數(shù)。分析數(shù)據(jù)相關(guān)的主要工作:(1)確定指令的相關(guān)性，找到所有可能產(chǎn)生停頓的地方。(2)確定必須嚴格遵守的數(shù)據(jù)的計算順序。(3)確定指令的最大相關(guān)距離，確定程序中可

能的最大并行性。4.1指令級并行的概念指令的相關(guān)距離（distance）4.1指令級并行的概念2.名相關(guān)（namedependence）指令使用的寄存器或存儲器稱為名。如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流，則稱之為名相關(guān)。指令j與指令i之間名相關(guān)有以下兩種：(1)反相關(guān)（anti-dependence）(2)輸出相關(guān)（outputdependence）4.1指令級并行的概念2.名相關(guān)（namedependence）指令使用的寄存消除名相關(guān)名相關(guān)的指令之間沒有數(shù)據(jù)交換。如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。通過改變指令中操作數(shù)的名來消除名相關(guān)，這就是換名（renaming）技術(shù)。對于寄存器操作數(shù)進行換名稱為寄存器換名。

（registerrenaming）可以用編譯器靜態(tài)完成或硬件動態(tài)完成。4.1指令級并行的概念消除名相關(guān)名相關(guān)的指令之間沒有數(shù)據(jù)交換。4.1指令級并行例：我們對例4.2編譯過程進行分析，來仔細考察

換名的過程。

(1)首先，僅僅去除4遍循環(huán)體中的分支指令，

得到以下由17條指令構(gòu)成的指令序列：4.1指令級并行的概念例：我們對例4.2編譯過程進行分析，來仔細考察

換名Loop:LDF0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,R1,#8 LD F0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,R1,#8 LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop4.1指令級并行的概念 LD F0,0(R1)4.1指令級并行的概念(2)編譯器可以通過對相關(guān)鏈上存儲器訪問偏移量的直接調(diào)整，將前3條SUBI指令消除掉，從而得到下面一個14條指令構(gòu)成的指令序列：

4.1指令級并行的概念(2)編譯器可以通過對相關(guān)鏈上存儲器訪問偏移量的直接Loop: LD F0,0(R1) ADDDF4,F0,F2

SD 0(R1),F4 LD F0,-8(R1) ADDD