《計算機(jī)系統(tǒng)結(jié)構(gòu)》系統(tǒng)結(jié)構(gòu)4

1、小節(jié)章節(jié)名主要內(nèi)容4.1指令級并行的概念指令級并行4.2指令的動態(tài)調(diào)度動態(tài)調(diào)度思想，Tomasulo算法4.3動態(tài)分支預(yù)測技術(shù)什么是動態(tài)分支預(yù)測，分支歷史表，分支目標(biāo)緩沖器，基于硬件的前瞻技術(shù)4.4多指令流出技術(shù)自學(xué)4.5循環(huán)展開和指令調(diào)度自學(xué)幾乎所有的處理機(jī)都利用流水線來使指令重疊并行執(zhí)行，以達(dá)到提高性能的目的。這種指令之間存在的潛在并行性稱為指令級并行。 （ILP：Instruction-Level Parallelism）開發(fā)指令級并行的方法：靜態(tài)方法軟件動態(tài)方法硬件4.1 指令級并行4.1.1 指令級并行的概念4.1 指令級并行目標(biāo) 降低流水線處理機(jī)的實際CPI理想流水線的CPI加上各

2、類停頓的時鐘周期數(shù)： CPI流水線 = CPI理想 + 停頓結(jié)構(gòu)沖突 + 停頓數(shù)據(jù)沖突 + 停頓控制沖突理想CPI是衡量流水線最高性能的一個指標(biāo)。概念 - 基本程序塊基本程序塊：一段除了入口和出口以外不包含其他分支的線性代碼段。程序平均每57條指令就會有一個分支?？缁緣K開發(fā)指令級并行4.1 指令級并行方法1 從循環(huán)入手：使一個循環(huán)中的不同循環(huán)體并行執(zhí)行。開發(fā)循環(huán)體中存在的并行性是指令級并行研究的重點之一例如，考慮下述語句： for （i=1； i2）分支預(yù)測的性能差不多。兩位分支預(yù)測的狀態(tài)轉(zhuǎn)換如下所示： 4.3 動態(tài)分支預(yù)測技術(shù)兩位分支預(yù)測中的操作有兩個步驟：分支預(yù)測。當(dāng)分支指令到達(dá)譯碼段（

3、ID）時，根據(jù)從BHT讀出的信息進(jìn)行分支預(yù)測 。若預(yù)測正確，就繼續(xù)處理后續(xù)的指令，流水線沒有斷流。否則，就要作廢已經(jīng)預(yù)取和分析的指令，恢復(fù)現(xiàn)場，并從另一條分支路徑重新取指令。 狀態(tài)修改。 4.3 動態(tài)分支預(yù)測技術(shù)BHT方法只在以下情況下才有用：判定分支是否成功所需的時間大于確定分支目標(biāo)地址所需的時間。 前述5段經(jīng)典流水線：由于判定分支是否成功和計算分支目標(biāo)地址都是在ID段完成，所以BHT方法不會給該流水線帶來好處。研究結(jié)果表明：對于SPEC89測試程序來說，具有大小為4K的BHT的預(yù)測準(zhǔn)確率為82%99%。 一般來說，采用4K的BHT就可以了。 BHT可以跟分支指令一起存放在指令Cache中，

4、也可以用一個專門的硬件來實現(xiàn)。 4.3 動態(tài)分支預(yù)測技術(shù)目標(biāo)：將分支的開銷降為 0方法：分支目標(biāo)緩沖將分支成功的分支指令的地址和它的分支目標(biāo)地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令的地址作為標(biāo)識。這個緩沖區(qū)就是分支目標(biāo)緩沖器（Branch-Target Buffer，簡記為BTB，或者Branch-Target Cache）。 4.3.2 采用分支目標(biāo)緩沖器BTB4.3 動態(tài)分支預(yù)測技術(shù)BTB的結(jié)構(gòu) 采用BTB后，在流水線各個階段所進(jìn)行的相關(guān)操作： 4.3 動態(tài)分支預(yù)測技術(shù)采用BTB后，各種可能情況下的延遲 ：指令在BTB中？ 預(yù)測 實際情況 延遲周期 是 成功 成功 0 是 成功 不

5、成功 2 不是 成功 2 不是 不成功 0 更新 1；重取 1.4.3 動態(tài)分支預(yù)測技術(shù)BTB的另一種形式 在分支目標(biāo)緩沖器中存放一條或者多條分支目標(biāo)處的指令。有三個潛在的好處：更快地獲得分支目標(biāo)處的指令；可以一次提供分支目標(biāo)處的多條指令，這對于多流出處理器是很有必要的；使我們可以進(jìn)行稱為分支折疊（branch folding）的優(yōu)化。 實現(xiàn)零延遲無條件分支，甚至有時還可以做到零延遲條件分支。4.3 動態(tài)分支預(yù)測技術(shù)前瞻執(zhí)行（speculation）的基本思想： 對分支指令的結(jié)果進(jìn)行猜測，并假設(shè)這個猜測總是對的，然后按這個猜測結(jié)果繼續(xù)取、流出和執(zhí)行后續(xù)的指令。只是執(zhí)行指令的結(jié)果不是寫回到寄存器

6、或存儲器，而是放到一個稱為ROB（ReOrder Buffer）的緩沖器中。等到相應(yīng)的指令得到“確認(rèn)”（commit）（即確實是應(yīng)該執(zhí)行的）之后，才將結(jié)果寫入寄存器或存儲器。 4.3.3 基于硬件的前瞻執(zhí)行4.3 動態(tài)分支預(yù)測技術(shù)基于硬件的前瞻執(zhí)行結(jié)合了三種思想：動態(tài)分支預(yù)測。用來選擇后續(xù)執(zhí)行的指令。在控制相關(guān)的結(jié)果尚未出來之前，前瞻地執(zhí)行后續(xù)指令。用動態(tài)調(diào)度對基本塊的各種組合進(jìn)行跨基本塊的調(diào)度。對Tomasulo算法加以擴(kuò)充，就可以支持前瞻執(zhí)行。 把Tomasulo算法的寫結(jié)果和指令完成加以區(qū)分，分成兩個不同的段： 寫結(jié)果，指令確認(rèn) 4.3 動態(tài)分支預(yù)測技術(shù)寫結(jié)果段把前瞻執(zhí)行的結(jié)果寫到ROB

7、中；通過CDB在指令之間傳送結(jié)果，供需要用到這些結(jié)果的指令使用。指令確認(rèn)段 在分支指令的結(jié)果出來后，對相應(yīng)指令的前瞻執(zhí)行給予確認(rèn)。如果前面所做的猜測是對的，把在ROB中的結(jié)果寫到寄存器或存儲器。如果發(fā)現(xiàn)前面對分支結(jié)果的猜測是錯誤的，那就不予以確認(rèn)（清空ROB），并從那條分支指令的另一條路徑開始重新執(zhí)行。 4.3 動態(tài)分支預(yù)測技術(shù)實現(xiàn)前瞻的關(guān)鍵思想： 允許指令亂序執(zhí)行，但必須順序確認(rèn)。支持前瞻執(zhí)行的浮點部件的結(jié)構(gòu) 4.3 動態(tài)分支預(yù)測技術(shù)ROB中的每一項由以下4個字段組成：指令類型 指出該指令是分支指令、store指令或寄存器操作指令。目標(biāo)地址 給出指令執(zhí)行結(jié)果應(yīng)寫入的目標(biāo)寄存器號（如果是 lo

8、ad和ALU指令）或存儲器單元的地址（如果是store指 令）。數(shù)據(jù)值字段 用來保存指令前瞻執(zhí)行的結(jié)果，直到指令得到確認(rèn)。就緒字段 指出指令是否已經(jīng)完成執(zhí)行并且數(shù)據(jù)已就緒。4.3 動態(tài)分支預(yù)測技術(shù)Tomasulo算法中保留站的換名功能是由ROB來完成的。 采用前瞻執(zhí)行機(jī)制后，指令的執(zhí)行步驟：（在Tomasulo算法的基礎(chǔ)上改造的 ）流出 從浮點指令隊列的頭部取一條指令。如果有空閑的保留站（設(shè)為r）且有空閑的ROB項（設(shè)為b），就流出該指令，并把相應(yīng)的信息放入保留站r和ROB項b。如果保留站或ROB全滿，便停止流出指令，直到它們都有空閑的項。 4.3 動態(tài)分支預(yù)測技術(shù)執(zhí)行 如果有操作數(shù)尚未就緒，

9、就等待，并不斷地監(jiān)測CDB。 (檢測RAW沖突)當(dāng)兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指令的操作。寫結(jié)果 當(dāng)結(jié)果產(chǎn)生后，將該結(jié)果連同本指令在流出段所分配到的ROB項的編號放到CDB上，經(jīng)CDB寫到ROB以及所有等待該結(jié)果的保留站。釋放產(chǎn)生該結(jié)果的保留站。 store指令在本階段完成，其操作為: 4.3 動態(tài)分支預(yù)測技術(shù)如果要寫入存儲器的數(shù)據(jù)已經(jīng)就緒，就把該數(shù)據(jù)寫入分配給該store指令的ROB項。否則，就監(jiān)測CDB，直到那個數(shù)據(jù)在CDB上播送出來，這時才將之寫入分配給該store指令的ROB項。確認(rèn) 對分支指令、store指令以及其他指令的處理不同：其他指令（除分支指令和store指令

10、） 當(dāng)該指令到達(dá)ROB隊列的頭部而且其結(jié)果已經(jīng)就緒時，就把該結(jié)果寫入該指令的目標(biāo)寄存器，并從ROB中刪除該指令。 4.3 動態(tài)分支預(yù)測技術(shù)store指令 處理與上面類似，只是它把結(jié)果寫入存儲器。分支指令 當(dāng)預(yù)測錯誤的分支指令到達(dá)ROB隊列的頭部時，清空ROB，并從分支指令的另一個分支重新開始執(zhí)行。 （錯誤的前瞻執(zhí)行）當(dāng)預(yù)測正確的分支指令到達(dá)ROB隊列的頭部時，該指令執(zhí)行完畢。 4.3 動態(tài)分支預(yù)測技術(shù) 例4.3 假設(shè)浮點功能部件的延遲時間為：加法2個時鐘周期，乘法10個時鐘周期，除法40個時鐘周期。對于下面的代碼段，給出當(dāng)指令MUL.D即將確認(rèn)時的狀態(tài)表內(nèi)容。 L.DF6,34（R2） L.D

11、F2,45（R3） MUL.D F0,F2,F4 SUB.D F8,F6,F2 DIV.D F10,F0,F6 ADD.D F6,F8,F24.3 動態(tài)分支預(yù)測技術(shù)名稱 保留站 Busy Op Vj Vk Qj Qk Dest A Add1 no Add2 no Add3 no Mult1 no MUL Mem45+ RegsR2 RegsF4 #3 Mult2 yes DIV Mem34+RegsR2 #3 #5 前瞻執(zhí)行中MUL.D確認(rèn)前，保留站和ROB的狀態(tài) 項號 ROB Busy 指令 狀態(tài) 目的 Value 1 no L.D F6, 34（R2） 確認(rèn) F6 Mem34+RegsR2

12、 2no L.D F2, 45（R3） 確認(rèn) F2 Mem45+RegsR3 3yes MUL.D F0, F2, F4 寫結(jié)果 F0 #2RegsF4 4yes SUB.D F8, F6, F2 寫結(jié)果 F8 #1#2 5yes DIV.D F10, F0, F6 執(zhí)行 F10 6yes ADD.D F6,F8,F2 寫結(jié)果 F6 #4#2 字段 浮點寄存器狀態(tài) F0 F2 F4 F6 F8 F10 F30 ROB項編號 3645Busy yes no no yes yes yes no4.3 動態(tài)分支預(yù)測技術(shù)前瞻執(zhí)行通過ROB實現(xiàn)了指令的順序完成。能夠?qū)崿F(xiàn)精確異常。很容易地推廣到整數(shù)寄存器

13、和整數(shù)功能單元上。 主要缺點：所需的硬件太復(fù)雜。 一個時鐘周期內(nèi)流出多條指令， CPI1。單流出和多流出處理機(jī)執(zhí)行指令的時空圖對比 4.4 多指令流出技術(shù)單流出和多流出處理機(jī)執(zhí)行指令的時空圖 4.4 多指令流出技術(shù)4.4 多指令流出技術(shù)多流出處理機(jī)有兩種基本風(fēng)格：超標(biāo)量（Superscalar）在每個時鐘周期流出的指令條數(shù)不固定，依代碼的具體情況而定。（有上限）設(shè)這個上限為n，就稱該處理機(jī)為n流出?？梢酝ㄟ^編譯器進(jìn)行靜態(tài)調(diào)度，也可以基于Tomasulo算法進(jìn)行動態(tài)調(diào)度。 超長指令字VLIW（Very Long Instruction Word）在每個時鐘周期流出的指令條數(shù)是固定的，這些指令構(gòu)成

14、一條長指令或者一個指令包。指令包中，指令之間的并行性是通過指令顯式地表示出來的。指令調(diào)度是由編譯器靜態(tài)完成的。 4.4 多指令流出技術(shù)超標(biāo)量處理機(jī)與VLIW處理機(jī)相比有兩個優(yōu)點：超標(biāo)量結(jié)構(gòu)對程序員是透明的，因為處理機(jī)能自己檢測下一條指令能否流出，從而不需要重新排列指令來滿足指令的流出。即使是沒有經(jīng)過編譯器針對超標(biāo)量結(jié)構(gòu)進(jìn)行調(diào)度優(yōu)化的代碼或是舊的編譯器生成的代碼也可以運行，當(dāng)然運行的效果不會很好。要想達(dá)到很好的效果，方法之一： 使用動態(tài)超標(biāo)量調(diào)度技術(shù)。下表列出了一些基本的多流出技術(shù)、這些技術(shù)的特點以及采用這些技術(shù)的處理機(jī)例子。技 術(shù) 流出結(jié)構(gòu) 沖突檢測 調(diào) 度 主要特點 處理機(jī)實例 超標(biāo)量（靜態(tài)

15、） 動態(tài) 硬件 靜態(tài)順序執(zhí)行 Sun UltraSPARC/ 超標(biāo)量（動態(tài)） 動態(tài) 硬件 動態(tài)部分亂序執(zhí)行 IBM Power2 超標(biāo)量（猜測） 動態(tài) 硬件 帶有猜測的動態(tài)執(zhí)行 帶有猜測的亂序執(zhí)行 Pentium /4，MIPS R10K，Alpha 21264， HP PA 8500，IBM RS64 VLIW/LIW 靜態(tài) 軟件 靜態(tài)流出包之間沒有沖突 Trimedia，i860 EPIC 主要是靜態(tài) 主要是軟件 主要是靜態(tài)相關(guān)性被編譯器顯式地標(biāo)記出來 Itanium 4.4 多指令流出技術(shù)在典型的超標(biāo)量處理器中，每個時鐘周期可流出1到8條指令。指令按序流出，在流出時進(jìn)行沖突檢測。 在當(dāng)前

16、流出的指令序列中，不存在數(shù)據(jù)沖突或者相關(guān)沖突。舉例：一個4流出的靜態(tài)調(diào)度超標(biāo)量處理機(jī) 在取指令階段，流水線將從取指令部件收到14條指令（稱為流出包）。在一個時鐘周期內(nèi)，這些指令有可能是全部都能流出，也可能是只有一部分能流出。4.4.1 基于靜態(tài)調(diào)度的多流出技術(shù)4.4 多指令流出技術(shù)流出部件檢測結(jié)構(gòu)沖突或者數(shù)據(jù)沖突。一般分兩階段實現(xiàn)：第一階段：進(jìn)行流出包內(nèi)的沖突檢測，選出初步判定可以流出的指令。第二階段：檢測所選出的指令與正在執(zhí)行的指令是否有沖突。 MIPS處理機(jī)是怎樣實現(xiàn)超標(biāo)量的呢？假設(shè)：每個時鐘周期流出兩條指令： 1條整數(shù)型指令1條浮點操作指令其中，把load指令、store指令、分支指令歸

17、類為整數(shù)型指令。 4.4 多指令流出技術(shù)要求：同時取兩條指令（64位），譯碼兩條指令（64位）。對指令的處理包括以下步驟：從Cache中取兩條指令。確定那幾條指令可以流出（02條指令）。把它們發(fā)送到相應(yīng)的功能部件。 雙流出超標(biāo)量流水線中指令的執(zhí)行過程 假設(shè)：所有的浮點指令都是加法指令，其執(zhí)行時間為兩個時鐘周期。為簡單起見，下圖中總是把整數(shù)指令放在浮點指令的前面。 4.4 多指令流出技術(shù)指令類型 流水線工作情況 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF

18、 ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEM4.4 多指令流出技術(shù)采用“1條整數(shù)型指令1條浮點指令”并行流出的方式，需要增加的硬件很少。浮點load或浮點store指令將使用整數(shù)部件，會增加對浮點寄存器的訪問沖突。 增設(shè)一個浮點寄存器的讀/寫端口。由于流水線中的指令多了一倍，定向路徑也要增加。 4.4 多指令流出技術(shù)限制超標(biāo)量流水線的性能發(fā)揮的障礙。 load指令 load后續(xù)3條指令都不能使用其結(jié)果，否則就會引起停頓。 分支延遲 如果分支指令是流出包中的第一條指令，則其延遲是3個時鐘周

19、期；否則就是流出包中的第二條指令，其延遲就是兩個時鐘周期。 4.4 多指令流出技術(shù)擴(kuò)展Tomasulo算法：支持兩路超標(biāo)量每個時鐘周期流出兩條指令；一條是整數(shù)指令，另一條是浮點指令。采用一種比較簡單的方法：指令按順序流向保留站，否則會破壞程序語義。 將整數(shù)所用的表結(jié)構(gòu)與浮點用的表結(jié)構(gòu)分離開，分別進(jìn)行處理，這樣就可以同時地流出一條浮點指令和一條整數(shù)指令到各自的保留站。 4.4.2 基于動態(tài)調(diào)度的多流出技術(shù)4.4 多指令流出技術(shù)有兩種不同的方法可以實現(xiàn)多流出。 關(guān)鍵在于：對保留站的分配和對流水線控制表格的修改。在半個時鐘周期里完成流出步驟，這樣一個時鐘周期就能處理兩條指令。設(shè)置一次能同時處理兩條指

20、令的邏輯電路。 現(xiàn)代的流出4條或4條以上指令的超標(biāo)量處理機(jī)經(jīng)常是兩種方法都采用。 4.4 多指令流出技術(shù) 例4.4 對于采用了Tomasulo算法和多流出技術(shù)的MIPS流水線，考慮以下簡單循環(huán)的執(zhí)行。該程序把F2中的標(biāo)量加到一個向量的每個元素上。 Loop: L.D F0, 0（R1） / 取一個數(shù)組元素放入F0 ADD.D F4, F0, F2 / 加上在F2中的標(biāo)量 S.D F4, 0（R1） / 存結(jié)果 DADDIU R1,R1，#-8 / 將指針減少8（每個數(shù)據(jù)占8個字節(jié)） BNE R1,R2,Loop / 若R1不等于R2，表示尚未結(jié)束，轉(zhuǎn)移到Loop繼續(xù) 4.4 多指令流出技術(shù)現(xiàn)做

21、以下假設(shè)：每個時鐘周期能流出一條整數(shù)指令和一條浮點指令，即使它們相關(guān)也是如此。有一個整數(shù)部件，用于整數(shù)ALU運算和地址計算；并且對于每一種浮點操作類型都有一個獨立的流水化了的浮點功能部件。指令流出和寫結(jié)果各占用一個時鐘周期。具有動態(tài)分支預(yù)測部件和一個獨立的計算分支條件的功能部件。分支指令單獨流出，沒有采用延遲分支，但分支預(yù)測是完美的。分支指令完成前，其后續(xù)指令只能被取出和流出，但不能執(zhí)行。4.4 多指令流出技術(shù)因為寫結(jié)果占用一個時鐘周期，所以產(chǎn)生結(jié)果的延遲為：整數(shù)運算一個周期，load兩個周期，浮點加法運算3個周期。 列出該程序前面3遍循環(huán)中各條指令的流出、開始執(zhí)行和將結(jié)果寫到CDB上的時間。

22、 解 執(zhí)行時，該循環(huán)將動態(tài)展開，并且只要可能就流出兩條指令。 為了便于分析，表中列出了訪存發(fā)生的時刻。運行結(jié)果如下圖所示。 遍數(shù) 指 令 流出 執(zhí)行 訪存 寫CDB 說明 1L.D F0,0（R1） 1234流出第一條指令 1ADD.D F4,F0,F2 158等待L.D的結(jié)果 1S.D F4,0（R1） 239等待ADD.D的結(jié)果 1DADDIU R1,R1,#-8 245等待ALU1BNE R1,R2,Loop 36等待DADDIU的結(jié)果 2L.D F0,0（R1） 4789等待BNE完成 2ADD.D F4,F0,F2 41013等待L.D的結(jié)果 2S.D F4,0（R1） 5814等待

23、ADD.D的結(jié)果 2DADDIU R1,R1,#-8 5910等待ALU 2BNE R1,R2,Loop611等待DADDIU的結(jié)果 3L.D F0,0（R1） 7121314等待BNE完成 3ADD.D F4,F0,F2 71518等待L.D的結(jié)果 3S.D F4,0（R1） 81319等待ADD.D的結(jié)果 3DADDIU R1,R1,#-8 81415等待ALU 3BNE R1,R2,Loop916等待DADDIU的結(jié)果 4.4 多指令流出技術(shù)從圖中可以看出：程序基本可以達(dá)到3拍流出5條指令 IPC5/31.67 條/拍雖然指令的流出率比較高，但是執(zhí)行效率并不是很高。16拍共執(zhí)行15條指令

24、，平均指令執(zhí)行速度為15/160.94 條/拍。原因是浮點運算少，ALU部件成了瓶頸。 解決方法：增加一個加法器，把ALU功能和地址運算功能分開。 4.4 多指令流出技術(shù)上述雙流出動態(tài)調(diào)度流水線的性能受限于以下3個因素：整數(shù)部件和浮點部件的工作負(fù)載不平衡，沒有充分發(fā)揮出浮點部件的作用。 應(yīng)該設(shè)法減少循環(huán)中整數(shù)型指令的數(shù)量。每個循環(huán)迭代中的控制開銷太大。5條指令中有兩條指令是輔助指令。應(yīng)該設(shè)法減少或消除這些指令?？刂葡嚓P(guān)使得處理機(jī)必須等到分支指令的結(jié)果出來后才能開始下一條L.D指令的執(zhí)行。 4.4 多指令流出技術(shù)把能并行執(zhí)行的多條指令組裝成一條很長的指令。（100多位到幾百位）設(shè)置多個功能部件。

25、指令字被分割成一些字段，每個字段稱為一個操作槽，直接獨立地控制一個功能部件。在VLIW處理機(jī)中，所有的處理和指令安排都是由編譯器完成的。 4.4.3 超長指令字技術(shù)（VLIW） 例4.5 假設(shè)VLIW處理機(jī)每個時鐘周期可同時流出5條指令：兩條訪存指令、兩條浮點操作指令和一條整數(shù)指令或分支指令。對于例4.4中的循環(huán)展開后的代碼，給出它在該VLIW中的代碼序列。不考慮分支指令的延遲槽。 解 代碼序列如下圖所示。運行時間為8個時鐘周期。每遍循環(huán)平均1.6個時鐘周期。8個時鐘周期內(nèi)流出了17條指令，每個時鐘周期2.1條。8個時鐘周期共有操作槽85=40個，有效槽的比例為42.5%。 4.4 多指令流出

26、技術(shù)4.4 多指令流出技術(shù)訪存指令1 訪存指令2 浮點指令1 浮點指令2 整數(shù)/轉(zhuǎn)移指令 L.D F0,0(R1)L.D F6,-8(R1)L.D F10,-16(R1)L.D F14,-24(R1)L.D F18,-32(R1)ADD.D F4,F0,F2ADD.DF8,F6,F2ADD.DF12,F10,F2ADD.DF16,F14,F2ADD.DF20,F18,F2S.D F4,0(R1)S.D F8,-8(R1)S.D F12,-16(R1)S.D F16,24(R1)DADDIUR1,R1,#-40S.D F20,8(R1)BNE R1,R2,Loop4.4 多指令流出技術(shù)VLIW存

27、在的一些問題 程序代碼長度增加了提高并行性而進(jìn)行的大量的循環(huán)展開。指令字中的操作槽并非總能填滿。 解決：采用指令共享立即數(shù)字段的方法，或者采用指 令壓縮存儲、調(diào)入Cache或譯碼時展開的方法。采用了鎖步機(jī)制 任何一個操作部件出現(xiàn)停頓時，整個處理機(jī)都要停頓。機(jī)器代碼的不兼容性4.4 多指令流出技術(shù)指令多流出處理器受哪些因素的限制呢？ 主要受以下三個方面的影響：程序所固有的指令級并行性。硬件實現(xiàn)上的困難。超標(biāo)量和超長指令字處理器固有的技術(shù)限制。4.4.4 多流出處理器受到的限制4.4 多指令流出技術(shù)將每個流水段進(jìn)一步細(xì)分，這樣在一個時鐘周期內(nèi)能夠分時流出多條指令。這種處理機(jī)稱為超流水線處理機(jī)。對于

28、一臺每個時鐘周期能流出n條指令的超流水線計算機(jī)來說，這n條指令不是同時流出的，而是每隔1/n個時鐘周期流出一條指令。實際上該超流水線計算機(jī)的流水線周期為1/n個時鐘周期。 一臺每個時鐘周期分時流出兩條指令的超流水線計算機(jī)的時空圖。 4.4.5 超流水線處理機(jī)4.4 多指令流出技術(shù)4.4 多指令流出技術(shù)在有的資料上，把指令流水線級數(shù)為8或8以上的流水線處理機(jī)稱為超流水線處理機(jī)。典型的超流水線處理器：SGI公司的MIPS系列R4000R4000微處理器芯片內(nèi)有2個Cache：指令Cache和數(shù)據(jù)Cache容量都是8 KB每個Cache的數(shù)據(jù)寬度為64 b R4000的核心處理部件：整數(shù)部件 一個3

29、232位的通用寄存器組一個算術(shù)邏輯部件（ALU）一個專用的乘法/除法部件 4.4 多指令流出技術(shù)浮點部件一個執(zhí)行部件浮點乘法部件浮點除法部件浮點加法/轉(zhuǎn)換/求平方根部件 （它們可以并行工作）一個1664位的浮點通用寄存器組。浮點通用寄存器組也可以設(shè)置成32個32位的浮點寄存器。R4000的指令流水線有8級4.4 多指令流出技術(shù)4.4 多指令流出技術(shù)各級的功能IF：取指令的前半步，根據(jù)PC值去啟動對指令Cache的訪問。IS：取指令的后半步，在這一級完成對指令Cache的訪問。RF：指令譯碼，訪問寄存器組讀取操作數(shù)，沖突檢測，并判斷指令Cache是否命中。EX：指令執(zhí)行。包括有效地址計算，ALU

30、操作，分支目標(biāo)地址計算，條件碼測試。DF：取數(shù)據(jù)的前半步，啟動對數(shù)據(jù)Cache的訪問。DS：取數(shù)據(jù)的后半步，在這一級完成對數(shù)據(jù)Cache的訪問。TC：標(biāo)識比較，判斷對數(shù)據(jù)Cache的訪問是否命中。WB：load指令或運算型指令把結(jié)果寫回寄存器組。 4.4 多指令流出技術(shù)MIPS R4000指令流水線時空圖 載入延遲為兩個時鐘周期充分開發(fā)指令之間存在的并行性，找出不相關(guān)的指令序列，讓它們在流水線上重疊并行執(zhí)行。 增加指令間并行性最簡單和最常用的方法開發(fā)循環(huán)級并行性循環(huán)的不同迭代之間存在的并行性。在把循環(huán)展開后，通過重命名和指令調(diào)度來開發(fā)更多的并行性。 4.5 循環(huán)展開和指令調(diào)度4.5.1 循環(huán)展

31、開和指令調(diào)度的基本方法4.5 循環(huán)展開和指令調(diào)度編譯器完成這種指令調(diào)度的能力受限于兩個特性：程序固有的指令級并行性；流水線功能部件的執(zhí)行延遲。本節(jié)中，我們使用的浮點流水線延遲為： 產(chǎn)生結(jié)果的指令 使用結(jié)果的指令 延遲（時鐘周期數(shù)） 浮點計算 另一個浮點計算 3 浮點計算 浮點store（S.D） 2 浮點load（L.D） 浮點計算 1 浮點load（L.D） 浮點store（S.D） 0 4.5 循環(huán)展開和指令調(diào)度假設(shè)采用第3章的5段整數(shù)流水線：分支的延遲：1個時鐘周期。整數(shù)load指令的延遲：1個時鐘周期。整數(shù)運算部件是全流水或者重復(fù)設(shè)置了足夠的份數(shù)。 4.5 循環(huán)展開和指令調(diào)度 例4.6

32、 對于下面的源代碼，轉(zhuǎn)換成MIPS匯編語言，在不進(jìn)行指令調(diào)度和進(jìn)行指令調(diào)度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時間。 for (i=1； i=1000； i+) xi = xi + s；解 把該程序翻譯成MIPS匯編語言代碼：假設(shè)R1的初值是指向第一個元素，8（R2）指向最后一個元素。4.5 循環(huán)展開和指令調(diào)度Loop：L.D F0,0（R1） ADD.D F4,F0,F2 S.D F4, 0（R1） DADDIU R1,R1，#-8 BNE R1,R2,Loop其中：整數(shù)寄存器R1：指向向量中的當(dāng)前元素。 （初值為向量中最高端元素的地址）浮點寄存器F2：用于保存常數(shù)s。 4.5 循環(huán)展開

33、和指令調(diào)度不進(jìn)行指令調(diào)度的情況下，程序的實際執(zhí)行情況： 指令流出時鐘 Loop: L.D F0,0（R1） 1 （空轉(zhuǎn)） 2 ADD.D F4,F0,F2 3 （空轉(zhuǎn)） 4 （空轉(zhuǎn)） 5 S.D F4, 0（R1） 6 DADDIU R1,R1，# -8 7 （空轉(zhuǎn)） 8 BNE R1,R2,Loop 9 （空轉(zhuǎn)） 10 每個元素的操作需要10個時鐘周期，其中5個是空轉(zhuǎn)周期。4.5 循環(huán)展開和指令調(diào)度指令調(diào)度以后，程序的執(zhí)行情況如下：把DADDIU指令調(diào)度到了L.D指令和ADD.D指令之間的“空轉(zhuǎn)”拍。把S.D指令放到了分支指令的延遲槽中。對存儲器地址偏移量進(jìn)行調(diào)整。 4.5 循環(huán)展開和指令調(diào)

34、度 Loop: L.D F0,0（R1） （空轉(zhuǎn)） ADD.D F4,F0,F2 （空轉(zhuǎn)） （空轉(zhuǎn)） S.D F4, 0（R1） DADDIU R1,R1,#-8 （空轉(zhuǎn)） BNE R1,R2,Loop （空轉(zhuǎn)）Loop: L.D F0, 0(R1) DADDIU R1,R1,#-8 ADD.D F4, F0, F2 （空轉(zhuǎn)） BNE R1,R2,Loop S.D F4，8(R1) 4.5 循環(huán)展開和指令調(diào)度 指令流出時鐘Loop: L.D F0, 0(R1) 1 DADDIU R1, R1, #-8 2 ADD.D F4, F0, F2 3 （空轉(zhuǎn)） 4 BNE R1, Loop 5 S.D

35、 F4，8(R1) 6 一個元素的操作時間從10個時鐘周期減少到6個,其中5個周期是有指令執(zhí)行的，1個為空轉(zhuǎn)周期。4.5 循環(huán)展開和指令調(diào)度例子中的問題及解決方案只有L.D、ADD.D和S.D這3條指令是有效操作。 (取、加、存)占用3個時鐘周期。而DADDIU、空轉(zhuǎn)和BEN這3個時鐘周期都是附加的循環(huán)控制開銷。循環(huán)展開技術(shù)把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。這給編譯器進(jìn)行指令調(diào)度帶來了更大的空間。 4.5 循環(huán)展開和指令調(diào)度 例4.7 （體現(xiàn)循環(huán)展開技術(shù)的特點） 將上述例子中的循環(huán)展開3次得到4個循環(huán)體，然后對展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性

36、能。假定R1的初值為32的倍數(shù)，即循環(huán)次數(shù)為4的倍數(shù)。消除冗余的指令，并且不要重復(fù)使用寄存器。 解 無需在循環(huán)體后面增加補(bǔ)償代碼4.5 循環(huán)展開和指令調(diào)度F0、F4：用于展開后的第1個循環(huán)體F2：保存常數(shù)F6、F8：展開后的第2個循環(huán)體F10、F12：第3個循環(huán)體F14、F16：第4個循環(huán)體 分配寄存器（不重復(fù)使用寄存器 ）：展開后沒有調(diào)度的代碼如下： 指令流出時鐘Loop:L.DF0,0(R1)1（空轉(zhuǎn)）2ADD.DF4,F0,F23（空轉(zhuǎn)）4（空轉(zhuǎn)）5S.DF4, 0（R1）6L.DF6,-8(R1)7（空轉(zhuǎn)）8ADD.DF8,F6,F29（空轉(zhuǎn)）10（空轉(zhuǎn)）11S.DF8, -8（R1）

37、12L.DF10,-16(R1)13（空轉(zhuǎn)）14 指令流出時鐘ADD.DF12,F10,F215（空轉(zhuǎn)）16（空轉(zhuǎn)）17S.DF12,-16(R1)18L.DF14,-24(R1)19（空轉(zhuǎn)）20ADD.DF16,F14,F221（空轉(zhuǎn)）22（空轉(zhuǎn)）23S.DF16,-24(R1)24DADDIUR1,R1,#-3225（空轉(zhuǎn)）26BNER1,R2,Loop27（空轉(zhuǎn)）284.5 循環(huán)展開和指令調(diào)度結(jié)果分析:這個循環(huán)每遍共使用了28個時鐘周期。有4個循環(huán)體，完成4個元素的操作。 平均每個元素使用28/4=7個時鐘周期原始循環(huán)的每個元素需要10個時鐘周期。 節(jié)省的時間：從減少循環(huán)控制的開銷中獲得

38、的。在整個展開后的循環(huán)中，實際指令只有14條，其他14個周期都是空轉(zhuǎn)。 效率并不高對指令序列進(jìn)行優(yōu)化調(diào)度，以減少空轉(zhuǎn)周期： 指令流出時鐘Loop:L.DF0,0(R1) 1L.DF6,-8(R1) 2L.DF10,-16(R1) 3L.DF14,-24(R1) 4ADD.DF4,F0,F2 5ADD.DF8,F6,F2 6ADD.DF12,F10,F2 7ADD.DF16,F14,F2 8S.DF4,0(R1) 9S.DF8,-8(R1) 10DADDIUR1,R1,#-32 12S.DF12,16(R1) 11BNER1,R2,Loop 13S.DF16,8(R1) 144.5 循環(huán)展開和指令調(diào)度結(jié)果分析：沒有數(shù)據(jù)相關(guān)引起的空轉(zhuǎn)等待。 整個循環(huán)僅僅使用了14個時鐘周期。 平均每個元素的操作使用14/4=3.5個時鐘周期。通過循環(huán)展開、寄存器重命名和指令調(diào)度，可以有效地開發(fā)出指令級并行。 4.5 循環(huán)展開和指令調(diào)度循環(huán)展開和指令調(diào)度時要注意以下幾個方面：保證正確性。 在循環(huán)展開和調(diào)度過程中尤其要注意兩個地方的正確性：循環(huán)控制，操作數(shù)偏移量的修改。注意有效性。 只有能夠找到不同循環(huán)體之間的無關(guān)性，才能