計算機體系結構：第5章 指令級并行及其開發(fā)——硬件方法

1、第5章 指令級并行及其開發(fā)硬件方法5.1指令級并行的概念5.2相關與指令級并行5.3指令的動態(tài)調(diào)度5.4動態(tài)分支預測技術5.5多指令流出技術指令級并行：指指令之間存在的一種并行性，利用它，計算機可以并行執(zhí)行兩條或兩條以上的指令。 （ILP：Instruction-Level Parallelism）開發(fā)ILP的途徑有兩種 資源重復，重復設置多個處理部件，讓它們同時執(zhí)行相鄰或相近的多條指令； 采用流水線技術，使指令重疊并行執(zhí)行。 本章研究：如何利用各種技術來開發(fā)更多的指令級并行 （硬件的方法） 開發(fā)ILP的方法可以分為兩大類主要基于硬件的動態(tài)開發(fā)方法基于軟件的靜態(tài)開發(fā)方法流水線處理機的實際CPI

2、理想流水線的CPI加上各類停頓的時鐘周期數(shù)： CPI流水線 = CPI理想 + 停頓結構沖突 + 停頓數(shù)據(jù)沖突 + 停頓控制沖突理想CPI是衡量流水線最高性能的一個指標。IPC：Instructions Per Cycle （每個時鐘周期完成的指令條數(shù)）5.1 指令級并行的概念5.1 指令級并行的概念基本程序塊基本程序塊：一串連續(xù)的代碼除了入口和出口以外，沒有其他的分支指令和轉(zhuǎn)入點 。程序平均每47條指令就會有一個分支。循環(huán)級并行：使一個循環(huán)中的不同循環(huán)體并行執(zhí)行。開發(fā)循環(huán)的不同疊代之間存在的并行性 最常見、最基本是指令級并行研究的重點之一5.1 指令級并行的概念例如，考慮下述語句： for

3、（i=1； i2）分支預測的性能差不多。兩位分支預測的狀態(tài)轉(zhuǎn)換如下所示： 5.4 動態(tài)分支預測技術兩位分支預測中的操作有兩個步驟：分支預測；當分支指令到達譯碼段（ID）時，根據(jù)從BHT讀出的信息進行分支預測 。若預測正確，就繼續(xù)處理后續(xù)的指令，流水線沒有斷流。否則，就要作廢已經(jīng)預取和分析的指令，恢復現(xiàn)場，并從另一條分支路徑重新取指令。 狀態(tài)修改。 BHT方法只在以下情況下才有用：判定分支是否成功所需的時間大于確定分支目標地址所需的時間。 5.4 動態(tài)分支預測技術前述5段經(jīng)典流水線：由于判定分支是否成功和計算分支目標地址都是在ID段完成，所以BHT方法不會給該流水線帶來好處。研究結果表明：對于S

4、PEC89測試程序來說，具有大小為4KB的BHT的預測準確率為82%99%。 一般來說，采用4KB的BHT就可以了。 BHT可以跟分支指令一起存放在指令Cache中，也可以用一塊專門的硬件來實現(xiàn)。 5.4 動態(tài)分支預測技術目標：將分支的開銷降為 0方法：分支目標緩沖將分支成功的分支指令的地址和它的分支目標地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令的地址作為標識。這個緩沖區(qū)就是分支目標緩沖器（Branch-Target Buffer，簡記為BTB，或者分支目標Cache （ranch-Target Cache）。 5.4.2 采用分支目標緩沖器BTB5.4 動態(tài)分支預測技術BTB的結構 5

5、.4 動態(tài)分支預測技術看成是用專門的硬件實現(xiàn)的一張表格。 表格中的每一項至少有兩個字段： 執(zhí)行過的成功分支指令的地址；（作為該表的匹配標識 ）預測的分支目標地址。采用BTB后，在流水線各個階段所進行的相關操作： 5.4 動態(tài)分支預測技術采用BTB后，各種可能情況下的延遲 ：指令在BTB中？ 預測 實際情況 延遲周期 是 成功 成功 0 是 成功 不成功 2 不是 成功 2 不是 不成功 0 5.4 動態(tài)分支預測技術BTB的另一種形式在分支目標緩沖器中增設一個至少是兩位的“分支歷史表”字段 5.4 動態(tài)分支預測技術更進一步，在表中對于每條分支指令都存放若干條分支目標處的指令，就形成了分支目標指令

6、緩沖器。5.4 動態(tài)分支預測技術前瞻執(zhí)行（speculation）的基本思想： 對分支指令的結果進行猜測，并假設這個猜測總是對的，然后按這個猜測結果繼續(xù)取、流出和執(zhí)行后續(xù)的指令。只是執(zhí)行指令的結果不是寫回到寄存器或存儲器，而是寫入一個稱為再定序緩沖器ROB（ReOrder Buffer）中 。等到相應的指令得到“確認”（commit）（即確實是應該執(zhí)行的）之后，才將結果寫入寄存器或存儲器。 5.4.3 基于硬件的前瞻執(zhí)行5.4 動態(tài)分支預測技術基于硬件的前瞻執(zhí)行結合了3種思想：動態(tài)分支預測。用來選擇后續(xù)執(zhí)行的指令。在控制相關的結果尚未出來之前，前瞻地執(zhí)行后續(xù)指令。用動態(tài)調(diào)度對基本塊的各種組合進

7、行跨基本塊的調(diào)度。對Tomasulo算法加以擴充，就可以支持前瞻執(zhí)行。 把Tomasulo算法的寫結果和指令完成加以區(qū)分，分成兩個不同的段： 寫結果，指令確認 5.4 動態(tài)分支預測技術寫結果段把前瞻執(zhí)行的結果寫到ROB中；通過CDB在指令之間傳送結果，供需要用到這些結果的指令使用。指令確認段 在分支指令的結果出來后，對相應指令的前瞻執(zhí)行給予確認。如果前面所做的猜測是對的，把在ROB中的結果寫到寄存器或存儲器。如果發(fā)現(xiàn)前面對分支結果的猜測是錯誤的，那就不予以確認，并從那條分支指令的另一條路徑開始重新執(zhí)行。 5.4 動態(tài)分支預測技術實現(xiàn)前瞻的關鍵思想： 允許指令亂序執(zhí)行，但必須順序確認。在指令被確

8、認之前，不允許它進行不可恢復的操作。 支持前瞻執(zhí)行的浮點部件的結構 5.4 動態(tài)分支預測技術ROB中的每一項由以下4個字段組成：指令類型 指出該指令是分支指令、store指令或寄存器操作指令。目標地址 給出指令執(zhí)行結果應寫入的目標寄存器號（如果是 load和ALU指令）或存儲器單元的地址（如果是store指 令）。數(shù)據(jù)值字段 用來保存指令前瞻執(zhí)行的結果，直到指令得到確認。就緒字段 指出指令是否已經(jīng)完成執(zhí)行并且數(shù)據(jù)已就緒。5.4 動態(tài)分支預測技術Tomasulo算法中保留站的換名功能是由ROB來完成的。 采用前瞻執(zhí)行機制后，指令的執(zhí)行步驟：（在Tomasulo算法的基礎上改造的 ）流出 從浮點指

9、令隊列的頭部取一條指令。如果有空閑的保留站（設為r）且有空閑的ROB項（設為b），就流出該指令，并把相應的信息放入保留站r和ROB項b。如果保留站或ROB全滿，便停止流出指令，直到它們都有空閑的項。 5.4 動態(tài)分支預測技術執(zhí)行 如果有操作數(shù)尚未就緒，就等待，并不斷地監(jiān)測CDB。 (檢測RAW沖突)當兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指令的操作。寫結果 當結果產(chǎn)生后，將該結果連同本指令在流出段所分配到的ROB項的編號放到CDB上，經(jīng)CDB寫到ROB以及所有等待該結果的保留站。釋放產(chǎn)生該結果的保留站。 store指令在本階段完成，其操作為: 5.4 動態(tài)分支預測技術如果要寫入存儲器的數(shù)

10、據(jù)已經(jīng)就緒，就把該數(shù)據(jù)寫入分配給該store指令的ROB項。否則，就監(jiān)測CDB，直到那個數(shù)據(jù)在CDB上播送出來，才將之寫入分配給該store指令的ROB項。確認 對分支指令、store指令以及其它指令的處理不同：其它指令（除分支指令和store指令） 當該指令到達ROB隊列的頭部而且其結果已經(jīng)就緒時，就把該結果寫入該指令的目的寄存器，并從ROB中刪除該指令。 5.4 動態(tài)分支預測技術store指令 處理與上面的類似，只是它把結果寫入存儲器。分支指令 當預測錯誤的分支指令到達ROB隊列的頭部時，清空ROB，并從分支指令的另一個分支重新開始執(zhí)行。 （錯誤的前瞻執(zhí)行）當預測正確的分支指令到達ROB隊

11、列的頭部時，該指令執(zhí)行完畢。 5.4 動態(tài)分支預測技術 例5.4 假設浮點功能部件的延遲時間為：加法2個時鐘周期，乘法10個時鐘周期，除法40個時鐘周期。對于下面的代碼段，給出當指令MUL.D即將確認時的狀態(tài)表內(nèi)容。 L.D F6,34（R2） L.D F2,45（R3） MUL.DF0,F2,F4 SUB.DF8,F6,F2 DIV.DF10,F0,F6 ADD.DF6,F8,F2名稱 保留站 Busy Op Vj Vk Qj Qk Dest A Load1noLoad2noAdd1 no Add2 no Add3 no Mult1 no MUL.DMem45+ RegsR2 RegsF4

12、#3 Mult2 yes DIV.D Mem34+RegsR2 #3 #5 前瞻執(zhí)行中MUL.D確認前，保留站和ROB的狀態(tài) 項號 ROB Busy 指令 狀態(tài) 目的 Value 1 no L.D F6, 34（R2） 確認 F6 Mem34+RegsR2 2no L.D F2, 45（R3） 確認 F2 Mem45+RegsR3 3yes MUL.D F0, F2, F4 寫結果 F0 #2RegsF4 4yes SUB.D F8, F6, F2 寫結果 F8 #1#2 5yes DIV.D F10, F0, F6 執(zhí)行 F10 6yes ADD.D F6,F8,F2 寫結果 F6 #4#2

13、 字段 浮點寄存器狀態(tài) F0 F2 F4 F6 F8 F10 F30 ROB項編號 3645Busy yes no no yes yes yes no5.4 動態(tài)分支預測技術前瞻執(zhí)行通過ROB實現(xiàn)了指令的順序完成。能夠?qū)崿F(xiàn)精確異常。很容易地推廣到整數(shù)寄存器和整數(shù)功能單元上。 主要缺點：所需的硬件太復雜。 在每個時鐘周期內(nèi)流出多條指令， CPI1。單流出和多流出處理機執(zhí)行指令的時空圖對比 5.5 多指令流出技術單流出和多流出處理機執(zhí)行指令的時空圖 5.5 多指令流出技術5.5 多指令流出技術多流出處理機有兩種基本風格：超標量（Superscalar）在每個時鐘周期流出的指令條數(shù)不固定，依代碼的具

14、體情況而定。（有個上限）設這個上限為n，就稱該處理機為n-流出。可以通過編譯器進行靜態(tài)調(diào)度，也可以基于Tomasulo算法進行動態(tài)調(diào)度。 超長指令字VLIW（Very Long Instruction Word）在每個時鐘周期流出的指令條數(shù)是固定的，這些指令構成一條長指令或者一個指令包。指令包中，指令之間的并行性是通過指令顯式地表示出來的。指令調(diào)度是由編譯器靜態(tài)完成的。 5.5 多指令流出技術超標量處理機與VLIW處理機相比有兩個優(yōu)點：超標量結構對程序員是透明的，處理機能自己檢測下一條指令能否流出，不需要由編譯器或?qū)ｉT的變換程序?qū)Τ绦蛑械闹噶钸M行重新排列；即使是沒有經(jīng)過編譯器針對超標量結構進行

15、調(diào)度優(yōu)化的代碼或是舊的編譯器生成的代碼也可以運行，當然運行的效果不會很好。要想達到很好的效果，方法之一： 使用動態(tài)超標量調(diào)度技術。下表列出了一些基本的多流出技術、這些技術的特點以及采用這些技術的處理機實例。技 術 流出結構 沖突檢測 調(diào) 度 主要特點 處理機實例 超標量（靜態(tài)） 動態(tài) 硬件 靜態(tài)按序執(zhí)行 Sun UltraSPARC/ 超標量（動態(tài)） 動態(tài) 硬件 動態(tài)部分亂序執(zhí)行 IBM Power2 超標量（猜測） 動態(tài) 硬件 帶有前瞻的動態(tài)調(diào)度 帶有前瞻的亂序執(zhí)行 Pentium /4，MIPS R10K，Alpha 21264， HP PA 8500，IBM RS64 VLIW/LIW

16、靜態(tài) 軟件 靜態(tài)流出包之間沒有沖突 Trimedia，i860 EPIC 主要是靜態(tài) 主要是軟件 主要是靜態(tài)相關性被編譯器顯式地標記出來 Itanium 5.5 多指令流出技術在典型的超標量處理器中，每個時鐘周期可流出1到8條指令。指令按序流出，在流出時進行沖突檢測。 由硬件檢測當前流出的指令之間是否存在沖突以及當前流出的指令與正在執(zhí)行的指令是否有沖突。 舉例：一個4-流出的靜態(tài)調(diào)度超標量處理機 在取指令階段，流水線將從取指令部件收到14條指令（稱為流出包）。在一個時鐘周期內(nèi)，這些指令有可能是全部都能流出，也可能是只有一部分能流出。5.5.1 基于靜態(tài)調(diào)度的多流出技術5.5 多指令流出技術流出

17、部件檢測結構沖突或者數(shù)據(jù)沖突。一般分兩階段實現(xiàn)：第一段：進行流出包內(nèi)的沖突檢測，選出初步判定可以流出的指令；第二段：檢測所選出的指令與正在執(zhí)行的指令是否有沖突。 MIPS處理機是怎樣實現(xiàn)超標量的呢？假設：每個時鐘周期流出兩條指令： 1條整數(shù)型指令1條浮點操作指令其中：把load指令、store指令、分支指令歸類為整數(shù)型指令。 5.5 多指令流出技術要求：同時取兩條指令（64位），譯碼兩條指令（64位）。對指令的處理包括以下步驟：從Cache中取兩條指令；確定那幾條指令可以流出（02條指令）；把它們發(fā)送到相應的功能部件。 雙流出超標量流水線中指令執(zhí)行的時空圖 假設：所有的浮點指令都是加法指令，其

18、執(zhí)行時間為兩個時鐘周期。為簡單起見，圖中總是把整數(shù)指令放在浮點指令的前面。 5.5 多指令流出技術指令類型 流水線工作情況 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEMWB 整數(shù)指令 IF ID EX MEM WB 浮點指令 IF ID EX EXMEM5.5 多指令流出技術采用“1條整數(shù)型指令1條浮點指令”并行流出的方式，需要增加的硬件很少。浮點load或浮點store指令將使用整數(shù)部件

19、，會增加對浮點寄存器的訪問沖突。 增設一個浮點寄存器的讀/寫端口。由于流水線中的指令多了一倍，定向路徑也要增加。 5.5 多指令流出技術限制超標量流水線的性能發(fā)揮的障礙 load指令 load后續(xù)3條指令都不能使用其結果，否則就會引起停頓。 分支延遲 如果分支指令是流出包中的第一條指令，則其延遲是3個時鐘周期；否則就是流出包中的第二條指令，其延遲就是兩個時鐘周期。 5.5 多指令流出技術擴展Tomasulo算法：支持雙流出超標量流水線 每個時鐘周期流出兩條指令；一條是整數(shù)指令，另一條是浮點指令。采用一種比較簡單的方法：指令按順序流向保留站，否則會破壞程序語義。 將整數(shù)所用的表結構與浮點用的表結

20、構分離開，分別進行處理，這樣就可以同時地流出一條浮點指令和一條整數(shù)指令到各自的保留站。 5.5.2 基于動態(tài)調(diào)度的多流出技術5.5 多指令流出技術有兩種不同的方法可以實現(xiàn)多流出 關鍵在于：對保留站的分配和對流水線控制表格的修改。在半個時鐘周期里完成流出步驟，這樣一個時鐘周期就能處理兩條指令。設置一次能同時處理兩條指令的邏輯電路。 現(xiàn)代的流出4條或4條以上指令的超標量處理機經(jīng)常是兩種方法都采用。 5.5 多指令流出技術 例5.5 對于采用了Tomasulo算法和多流出技術的MIPS流水線，考慮以下簡單循環(huán)的執(zhí)行。該程序把F2中的標量加到一個向量的每個元素上。 Loop: L.D F0, 0（R1

21、） / 取一個數(shù)組元素放入F0 ADD.D F4, F0, F2 / 加上在F2中的標量 S.D F4, 0（R1） / 存結果 DADDIU R1,R1，#-8 / 將指針減少8（每個數(shù)據(jù)占8個字節(jié)） BNE R1,R2,Loop / 若R1不等于R2，表示尚未結束，轉(zhuǎn)移到Loop繼續(xù)。 5.5 多指令流出技術現(xiàn)做以下假設：每個時鐘周期能流出一條整數(shù)指令和一條浮點指令，即使它們相關也是如此。有一個整數(shù)部件，用于整數(shù)ALU運算和地址計算；并且對于每一種浮點操作類型都有一個獨立的流水化了的浮點功能部件。指令流出和寫結果各占用一個時鐘周期。具有動態(tài)分支預測部件和一個獨立的計算分支條件的功能部件。跟

22、大多數(shù)動態(tài)調(diào)度處理器一樣，寫回段的存在意味著實際的指令延遲會比按序流動的簡單流水線多一個時鐘周期。 5.5 多指令流出技術所以，從產(chǎn)生結果數(shù)據(jù)的源指令到使用該結果數(shù)據(jù)的指令之間的延遲為：整數(shù)運算一個周期，load兩個周期，浮點加法運算3個周期。 1. 請列出該程序前面3遍循環(huán)中各條指令的流出、開始執(zhí)行和將結果寫到CDB上的時間。 2. 如果分支指令單流出，沒有采用延遲分支，但分支預測是完美的。請列出整數(shù)部件、浮點部件、數(shù)據(jù)Cache以及CDB的資源使用情況。 解 執(zhí)行時，該循環(huán)將動態(tài)展開，并且只要可能就流出兩條指令。表中列出了各指令執(zhí)行到幾個操作點的時間及資源的使用情況。 遍數(shù) 指 令 流出

23、執(zhí)行 訪存 寫CDB 說明 1L.D F0,0（R1） 1234流出第一條指令 1ADD.D F4,F0,F2 158等待L.D的結果 1S.D F4,0（R1） 239等待ADD.D的結果 1DADDIU R1,R1,#-8 245等待ALU1BNE R1,R2,Loop 36等待DADDIU的結果 2L.D F0,0（R1） 4789等待BNE完成 2ADD.D F4,F0,F2 41013等待L.D的結果 2S.D F4,0（R1） 5814等待ADD.D的結果 2DADDIU R1,R1,#-8 5910等待ALU 2BNE R1,R2,Loop611等待DADDIU的結果 3L.D

24、F0,0（R1） 7121314等待BNE完成 3ADD.D F4,F0,F2 71518等待L.D的結果 3S.D F4,0（R1） 81319等待ADD.D的結果 3DADDIU R1,R1,#-8 81415等待ALU 3BNE R1,R2,Loop916等待DADDIU的結果 時鐘周期 整型ALU 浮點ALU 數(shù)據(jù)Cache CDB21/L.D 31/S.D 1/L.D 41/DADDIU 1/L.D 51/ADD.D 1/DADDIU 672/L.D 82/S.D 2/L.D 1/ADD.D 92/DADDIU 1/S.D 2/L.D 102/ADD.D 2/DADDIU 11123

25、/L.D 5.5 多指令流出技術時鐘周期 整型ALU 浮點ALU 數(shù)據(jù)Cache CDB133/S.D 3/L.D2/ADD.D143/DADDIU2/S.D3/L.D15 3/ADD.D3/DADDIU16 17183/ADD.D193/S.D 20 5.5 多指令流出技術可以看出：每3個時鐘周期就執(zhí)行一個新循環(huán)，每個循環(huán)5條指令。 IPC5/31.67條/拍雖然指令的流出率比較高，但是執(zhí)行效率并不是很高。16拍共執(zhí)行15條指令，平均指令執(zhí)行速度為15/160.94條/拍。原因是浮點運算少，ALU部件成了瓶頸。 解決方法：增加一個加法器，把ALU功能和地址運算功能分開。 5.5 多指令流出技

26、術上述雙流出動態(tài)調(diào)度流水線的性能受限于以下3個因素：整數(shù)部件和浮點部件的工作負載不平衡，沒有充分發(fā)揮出浮點部件的作用。 應該設法減少循環(huán)中整數(shù)型指令的數(shù)量。每個循環(huán)疊代中的控制開銷太大。5條指令中有兩條指令是輔助指令；應該設法減少或消除這些指令?？刂葡嚓P使得處理機必須等到分支指令的結果出來后才能開始下一條L.D指令的執(zhí)行。 5.5 多指令流出技術把能并行執(zhí)行的多條指令組裝成一條很長的指令；（100多位到幾百位）設置多個功能部件；指令字被分割成一些字段，每個字段稱為一個操作槽，直接獨立地控制一個功能部件；在VLIW處理機中，在指令流出時不需要進行復雜的沖突檢測，而是依靠編譯器全部安排好了。 5.5.3 超長指令字技術5.5 多指令流出技術VLIW存在的一些問題 程序代碼長度增加了提高并行性而進行的大量的循環(huán)展開；指令字中的操作槽并非總能填滿。 解決：采用指令共享立即數(shù)字段的方法，或者采用指 令壓縮存儲、調(diào)入Cache或譯碼時展開的方法。采用了鎖步機制 任何一個操作部件出現(xiàn)停頓時，整個處理機都要停頓。機器代碼的不兼容性5.5 多指令流出技術指令多流出處理器受哪些因素的限制呢？ 主要受以下3個方