指令級(jí)并行-指令級(jí)并行的概念

1、4.1指令級(jí)并行的概念,當(dāng)指令之間不存在相關(guān)時(shí)，它們?cè)诹魉€中是可以重疊起來并行執(zhí)行的。這種指令序列中存在的潛在并行性稱為指令級(jí)并行。 （Instruction-Level Parallelism，簡(jiǎn)記為ILP） 本章研究：如何通過各種可能的技術(shù)，獲得更多的指令級(jí)并行性。 （硬件技術(shù)和軟件技術(shù)） 必須要硬件技術(shù)和軟件技術(shù)互相配合，才能夠最大限度地挖掘出程序中存在的指令級(jí)并行,第四章 指令級(jí)并行,虛擬存儲(chǔ)器的特點(diǎn),1.流水線處理器的實(shí)際CPI,CPI流水線 = CPI理想 + 各類停頓周期數(shù)的總和 流水線的理想CPI是流水線的最大流量。 各類停頓包括： 結(jié)構(gòu)相關(guān)停頓：是由于兩條指令使用同一個(gè)功能

2、部件而導(dǎo)致的停頓。 控制相關(guān)停頓：是由于指令流的改變（如分支指令）而導(dǎo)致的停頓。 RAW、WAR和WAW停頓：由數(shù)據(jù)相關(guān)造成的。 減少其中的任何一種停頓，都可以有效地減少CPI，從而提高流水線的性能,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),2. 本章要研究的技術(shù)以及它們所克服的停頓,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),3.幾個(gè)概念,基本程序塊 一段除了入口和出口以外不包含其它分支的線性代碼段。 程序平均每67條指令就會(huì)有一個(gè)分支。 循環(huán)體中指令之間的并行性稱為循環(huán)級(jí)并行性。 開發(fā)循環(huán)體中存在的并行性。 最常見、最基本 是指令級(jí)并行研究的重點(diǎn)之一,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器

3、的特點(diǎn),最基本的開發(fā)循環(huán)級(jí)并行的技術(shù) 指令調(diào)度（scheduling）技術(shù) 循環(huán)展開（loop unrolling）技術(shù) 換名（renaming）技術(shù),4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),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)度時(shí)，受限于以下兩 個(gè)特性,程序固有的指令級(jí)并行性 流水線功能部件的執(zhí)行延遲,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),3. 本章使用的浮點(diǎn)流水線的延遲,4.1 指令級(jí)并行的概念,虛擬存

4、儲(chǔ)器的特點(diǎn),例4.1 對(duì)于下面的源代碼，轉(zhuǎn)換成DLX匯編語言，在不進(jìn)行指令調(diào)度和進(jìn)行指令調(diào)度兩種情況下，分析代碼一次循環(huán)的執(zhí)行時(shí)間。 for (i=1; i=1000; i+) xi = xi + s,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),解：(1) 變量分配寄存器 整數(shù)寄存器R1：循環(huán)計(jì)數(shù)器，初值為向量 中最高端地址元素的地址。 浮點(diǎn)寄存器F2：保存常數(shù)S。 假定最低端元素的地址為8。 (2) DLX匯編語言后的程序 Loop:LDF0,0(R1) ADDDF4,F0,F2 SD0(R1),F4 SUBIR1,R1,#8 BNEZR1,Loop,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特

5、點(diǎn),3) 程序執(zhí)行的實(shí)際時(shí)鐘,根據(jù)表4-2中給出的的延遲，實(shí)際時(shí)鐘如下： 指令流出時(shí)鐘 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 SUBI R1 , R1 , #8 7 （空轉(zhuǎn)） 8 BNEZ R1 , Loop 9 （空轉(zhuǎn)） 10 每個(gè)元素的操作需要10個(gè)時(shí)鐘周期，其中5個(gè)是空轉(zhuǎn)周期,4.1 指令級(jí)并行的概念,4) 指令調(diào)度以后，程序的執(zhí)行情況,SD放在分支指令的分支延遲槽中 對(duì)存儲(chǔ)器地址偏移量進(jìn)行調(diào)整 指令流出時(shí)鐘 Loop: LD F0 , 0(R1) 1 SUBI R1

6、, R1 , #8 2 ADDD F4 , F0 , F2 3 （空轉(zhuǎn)） 4 BNEZ R1 , Loop 5 SD 8(R1) , F4 6 一個(gè)元素的操作時(shí)間從10個(gè)時(shí)鐘周期減少到6個(gè) 5個(gè)周期是有指令執(zhí)行的，1個(gè)空轉(zhuǎn)周期,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),5) 例子中的問題及解決方案,只有LD、ADDD和SD這3條指令是有效操作. 占用3個(gè)時(shí)鐘周期 而SUBI、空轉(zhuǎn)和BENZ這3個(gè)時(shí)鐘周期都是附加的循環(huán)控制開銷。 循環(huán)展開技術(shù) 多次復(fù)制循環(huán)體并相應(yīng)調(diào)整展開后的指令和循環(huán)結(jié)束條件，增加有效操作時(shí)間與控制操作時(shí)間的比率。 也給編譯器進(jìn)行指令調(diào)度帶來了更大的空間,4.1 指令級(jí)并行的

7、概念,虛擬存儲(chǔ)器的特點(diǎn),例4.2 體現(xiàn)循環(huán)展開技術(shù)的特點(diǎn),將例4.1中的循環(huán)展開成3次得到4個(gè)循環(huán)體，再對(duì)展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。 假定R1的初值為32的倍數(shù)，即循環(huán) 次數(shù)為4的倍數(shù),4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),解,補(bǔ)償代碼問題 寄存器分配 展開后的循環(huán)體內(nèi)不重復(fù)使用寄存器。 F0、F4：用于展開后的第1個(gè)循環(huán)體 F2：保存常數(shù) F6和F8：用于展開后的第2個(gè)循環(huán)體 F10和F12：用于第3個(gè)循環(huán)體 F14和F16：用于第4個(gè)循環(huán)體,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),1) 展開后沒有調(diào)度的代碼,流出時(shí)鐘 Loop:LDF0,0(R1)

8、 1 （空轉(zhuǎn)） 2 ADDDF4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 SD0(R1),F4 6 LDF6,-8(R1) 7 （空轉(zhuǎn)） 8 ADDDF8,F6,F2 9 （空轉(zhuǎn)） 10 （空轉(zhuǎn)） 11 SD-8(R1),F8 12 LDF10,-16(R1) 13 （空轉(zhuǎn)） 14,流出時(shí)鐘 ADDDF12,F10,F2 15 （空轉(zhuǎn)） 16 （空轉(zhuǎn)） 17 SD-16(R1),F12 18 LDF14,-24(R1) 19 （空轉(zhuǎn)） 20 ADDDF16,F14,F2 21 （空轉(zhuǎn)） 22 （空轉(zhuǎn)） 23 SD-24(R1),F16 24 SUBIR1,R1,#32 25 （空轉(zhuǎn)） 26

9、 BNEZR1,Loop 27 （空轉(zhuǎn)） 28,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),結(jié)果分析,這個(gè)循環(huán)每遍共使用了28個(gè)時(shí)鐘周期 有4個(gè)循環(huán)體，完成4個(gè)元素的操作 平均每個(gè)元素使用28/4=7個(gè)時(shí)鐘周期 原始循環(huán)的每個(gè)元素需要10個(gè)時(shí)鐘周期 節(jié)省的時(shí)間:從減少循環(huán)控制的開銷中獲得的 在整個(gè)展開后的循環(huán)中，實(shí)際指令只有14條，其它13個(gè)周期都是空轉(zhuǎn)。 效率并不高,4.1 指令級(jí)并行的概念,虛擬存儲(chǔ)器的特點(diǎn),2) 對(duì)指令序列進(jìn)行優(yōu)化調(diào)度,指令流出時(shí)鐘 Loop:LDF0,0(R1)1 LDF6,-8(R1)2 LDF10,-16(R1)3 LDF14,-24(R1)4 ADDDF4,F0,

10、F25 ADDDF8,F6,F26 ADDDF12,F10,F27 ADDDF16,F14,F28 SD0(R1),F49 SD-8(R1),F810 SUBIR1,R1,#3212 SD16(R1),F1211 BNEZR1,Loop13 SD8(R1),F1614,4.1 指令級(jí)并行的概念,結(jié)果分析,沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待 整個(gè)循環(huán)僅僅使用了14個(gè)時(shí)鐘周期 平均每個(gè)元素的操作使用14/4=3.5個(gè)時(shí)鐘周期 循環(huán)展開和指令調(diào)度可以有效地提高循環(huán)級(jí)并行性。 這種循環(huán)級(jí)并行性的提高實(shí)際是通過實(shí)現(xiàn)指令級(jí)并行來達(dá)到的。 可以使用編譯器來完成，也可以通過硬件來完成,4.1 指令級(jí)并行的概念,4.

11、循環(huán)展開和指令調(diào)度時(shí)要注意的問題,1) 保證正確性 (2) 注意有效性 (3) 使用不同的寄存器 (4) 盡可能減少循環(huán)控制中的測(cè)試指令和分支指令 (5) 注意對(duì)存儲(chǔ)器數(shù)據(jù)的相關(guān)性分析 (6) 注意新的相關(guān)性,5. 實(shí)現(xiàn)循環(huán)展開的關(guān)鍵 分析清楚代碼中指令的相關(guān)性，然后通過 指令調(diào)度來消除相關(guān),4.1 指令級(jí)并行的概念,4.1.2 相關(guān)性,開發(fā)指令級(jí)并行的關(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 指令級(jí)并行的概念,1. 數(shù)據(jù)相關(guān)（data dependence,對(duì)于指令i

12、和指令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)是兩條指令之間存在一個(gè)先寫后讀相關(guān)鏈。 相關(guān)鏈貫穿整個(gè)程序，是程序的內(nèi)在特征。 這種相關(guān)鏈?zhǔn)菍?dǎo)致流水線停頓的原因之一,4.1 指令級(jí)并行的概念,指令的相關(guān)距離（distance） 兩條指令之間的指令條數(shù)。 分析數(shù)據(jù)相關(guān)的主要工作: (1) 確定指令的相關(guān)性，找到所有可能產(chǎn)生停 頓的地方。 (2) 確定必須嚴(yán)格遵守的數(shù)據(jù)的計(jì)算順序。 (3) 確定指令的最大相關(guān)距離，確定程序中可 能的最大并行性,4.1 指令級(jí)并行的概念,2.

13、 名相關(guān)（name dependence,指令使用的寄存器或存儲(chǔ)器稱為名。 如果兩條指令使用相同的名，但是它們之間并沒有數(shù)據(jù)流，則稱之為名相關(guān)。 指令j與指令i之間名相關(guān)有以下兩種： (1) 反相關(guān)（anti-dependence） (2) 輸出相關(guān)（output dependence,4.1 指令級(jí)并行的概念,消除名相關(guān),名相關(guān)的指令之間沒有數(shù)據(jù)交換。 如果一條指令中的名改變了，并不影響另外一條指令的執(zhí)行。 通過改變指令中操作數(shù)的名來消除名相關(guān)，這就是換名（renaming）技術(shù)。 對(duì)于寄存器操作數(shù)進(jìn)行換名稱為寄存器換名。 （register renaming） 可以用編譯器靜態(tài)完成或硬件動(dòng)

14、態(tài)完成,4.1 指令級(jí)并行的概念,例：我們對(duì)例4.2編譯過程進(jìn)行分析，來仔細(xì)考察 換名的過程。 (1) 首先，僅僅去除4遍循環(huán)體中的分支指令， 得到以下由17條指令構(gòu)成的指令序列,4.1 指令級(jí)并行的概念,Loop: 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,LDF0 , 0(R1) ADDDF4 , F0 , F2 SD0(R1) , F4 SUBIR1 , R1 , #8 LDF

15、0 , 0(R1) ADDDF4 , F0 , F2 SD0(R1) , F4 SUBIR1 , R1 , #8 BNEZR1 , Loop,4.1 指令級(jí)并行的概念,2) 編譯器可以通過對(duì)相關(guān)鏈上存儲(chǔ)器訪問偏移 量的直接調(diào)整，將前3條SUBI指令消除掉，從而得到下面一個(gè)14條指令構(gòu)成的指令序列,4.1 指令級(jí)并行的概念,Loop: LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 LD F0 , -8(R1) ADDD F4 , F0 , F2 SD -8(R1) , F4 LD F0 , -16(R1) ADDD F4 , F0 , F2 SD -

16、16(R1) , F4 LD F0 , -24(R1) ADDD F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop,4.1 指令級(jí)并行的概念,3) 通過寄存器換名，消除名相關(guān)。 得到右邊的指令序列,Loop:LDF0 , 0(R1) ADDDF4 , F0 , F2 SD0(R1) , F4 LDF6 , -8(R1) ADDDF8 , F6 , F2 SD-8(R1) , F8 LDF10 , -16(R1) ADDDF12 , F10 , F2 SD-16(R1) , F12 LDF14 , -24(R1) ADD

17、DF16 , F14 , F2 SD-24(R1) , F16 SUBIR1 , R1 , #32 BNEZR1 , Loop,換名操作需要較大的寄存器開銷,4.1 指令級(jí)并行的概念,3控制相關(guān)（control dependence,控制相關(guān)是指由分支指令引起的相關(guān)。 典型的程序結(jié)構(gòu)是“if-then”結(jié)構(gòu)。 看下面一個(gè)示例： if p1 S1; ; S; if p2 S2;,4.1 指令級(jí)并行的概念,處理控制相關(guān)的兩個(gè)原則： (1) 與控制相關(guān)的指令不能移到分支指令之 前，即控制有關(guān)的指令不能調(diào)度到分支 指令控制范圍以外； (2) 與控制無關(guān)的指令不能移到分支指令之 后，即控制無關(guān)的指令不能調(diào)度到分支 指令控制范圍以內(nèi),4.1 指令級(jí)并行的概念,再考察例4.2： 假設(shè)循環(huán)展開時(shí)，循環(huán)控制分支指令沒有去除， 則指令序列如下,4.1 指令級(jí)并行的概念,Loop: LDF0 , 0(R1) ADDDF4 , F0 , F2 SD0(R1) ,