計算機體系結(jié)構(gòu)第四章-2

1、n4.3 動態(tài)分支預(yù)測技術(shù)4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)n動態(tài)分支預(yù)測動態(tài)分支預(yù)測 在程序運行時，根據(jù)分支指令過去的表現(xiàn)來預(yù)測其將來的行為。如果分支行為發(fā)生了變化，預(yù)測結(jié)果也跟著改變。有更好的預(yù)測準確度和適應(yīng)性。n需要解決的關(guān)鍵問題需要解決的關(guān)鍵問題 如何記錄分支的歷史信息； 如何根據(jù)這些信息來預(yù)測分支的去向（甚至取到指令）。4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)一一. .采用分支歷史表采用分支歷史表 BHTBHT（Branch History TableBranch History Table）n又稱為分支預(yù)測緩沖器（Branch Prediciton Buffe

2、r）n最簡單的動態(tài)分支預(yù)測方法。 n用BHTBHT來記錄分支指令最近一次或幾次的執(zhí)行情況（成功或不成功），并據(jù)此進行預(yù)測。 1. 1. 只有只有1 1個預(yù)測位的分支預(yù)測緩沖個預(yù)測位的分支預(yù)測緩沖 記錄分支指令最近一次的歷史，BHTBHT中只需要1 1位二進制位。（最簡單）2.2.采用兩位二進制位來記錄歷史采用兩位二進制位來記錄歷史n提高預(yù)測的準確度n研究結(jié)果表明：研究結(jié)果表明：兩位分支預(yù)測的性能與n位（n2）分支預(yù)測的性能差不多。1）兩位分支預(yù)測的狀態(tài)轉(zhuǎn)換如下所示：）兩位分支預(yù)測的狀態(tài)轉(zhuǎn)換如下所示： 分支預(yù)測：分支預(yù)測： 不成功不成功 分支預(yù)測：分支預(yù)測： 成功成功 11 10 分支不成功分支

3、不成功 分支成功分支成功 分支不成功分支不成功 分支成功分支成功 01 00 分支不成功分支不成功 分支成功分支成功 分支不成功分支不成功 分支成功分支成功 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)2）操作步驟：（）操作步驟：（2步）步）n分支預(yù)測分支預(yù)測n當分支指令到達譯碼段（IDID）時，根據(jù)從BHTBHT讀出的信息進行分支預(yù)測 。n若預(yù)測正確，就繼續(xù)處理后續(xù)的指令，流水線沒有斷流。否則，就要作廢已經(jīng)預(yù)取和分析的指令，恢復(fù)現(xiàn)場，并從另一條分支路徑重新取指令。 n狀態(tài)修改狀態(tài)修改4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)3. BHT方法只在以下情況下才有用：方法只在以下情況下才有用：n適用情況

4、：適用情況：判定分支是否成功所需的時間大于確定分支目標地址所需的時間。 n前述5段經(jīng)典流水線：由于判定分支是否成功和計算分支目標地址都是在ID段完成，所以BHT方法不會給該流水線帶來好處。4. 4. 研究結(jié)果表明：研究結(jié)果表明：對于SPEC89測試程序來說，具有大小為4K的BHT的預(yù)測準確率為預(yù)測準確率為82%82%99%99%。 一般來說，采用一般來說，采用4K4K的的BHTBHT就可以了。就可以了。 5. BHTBHT可以跟分支指令一起存放在指令可以跟分支指令一起存放在指令CacheCache中，也可以用一個專中，也可以用一個專門的硬件來實現(xiàn)。門的硬件來實現(xiàn)。 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)

5、分支預(yù)測技術(shù)二二. .采用分支目標緩沖器采用分支目標緩沖器BTB (Branch Target Buffer)BTB (Branch Target Buffer)n目的：目的：將分支的開銷減少為將分支的開銷減少為 0 0n方法：方法：分支目標緩沖器分支目標緩沖器 BTBn將分支成功的分支指令的地址和它的分支目標地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令的地地址作為標識址作為標識。n這個緩沖區(qū)就是分支目標緩沖器分支目標緩沖器（Branch-Target Buffer，簡記為BTB，或者Branch-Target Cache）。 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)1.1.BTB的結(jié)構(gòu)的

6、結(jié)構(gòu) N = =？ 當前取指令的地址當前取指令的地址 地址標識地址標識 預(yù)測的分支目標地址預(yù)測的分支目標地址 查找查找 認為本指令不是分支指令，認為本指令不是分支指令， 按普通指令正常執(zhí)行。按普通指令正常執(zhí)行。 Y 認為該指令是成功的分支指令，用預(yù)測的認為該指令是成功的分支指令，用預(yù)測的 分支目標地址作為下一條指令的分支目標地址作為下一條指令的 PCPC 值。值。 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)BTB是用專門的硬是用專門的硬件實現(xiàn)的一張表格。件實現(xiàn)的一張表格。 表格中的每一項表格中的每一項至少有兩個字段：至少有兩個字段： 執(zhí)行過的成功分執(zhí)行過的成功分支指令的地址；支指令的地址；（作為

7、該表的匹配作為該表的匹配標識標識 ）預(yù)測的分支目標預(yù)測的分支目標地址。地址。 2. 2.采用采用BTBBTB后，在流水線各個階段所進行的相關(guān)操作：后，在流水線各個階段所進行的相關(guān)操作： 當當前前P PC C 值值 B BT TB B 中中存存在在匹匹配配的的項項？ 成成功功分分支支指指令令？ 當當前前分分支支成成功功？ 以以B BT TB B 的的第第二二字字段段作作為為 否否 否否 正正常常執(zhí)執(zhí)行行指指令令 是是 是是 否否 分分支支預(yù)預(yù)測測正正確確， 繼繼續(xù)續(xù)執(zhí)執(zhí)行行后后繼繼指指令令， 指令無 不不會會出出現(xiàn)現(xiàn)停停頓頓。 分分支支預(yù)預(yù)測測錯錯誤誤，清清除除 已已取取的的指指令令，并并從從另

8、另 一一個個分分支支（即即失失敗敗處處） 取取指指令令。從從B BT TB B 中中刪刪 除除相相應(yīng)應(yīng)的的項項。 將將其其P PC C 值值和和分分支支 目目標標地地址址寫寫入入B BT TB B 中中，作作為為一一個個新新項項。 I IF F 段段 I ID D 段段 E EX X 段段 送送存存儲儲器器和和B BT TB B 分分支支目目標標地地址址送送給給P PC C 是是 預(yù)測分支成功預(yù)測分支成功實際分支實際分支不成功不成功BTB的建立的建立延遲延遲2個時鐘周期個時鐘周期之前不成功的分支之前不成功的分支未未執(zhí)行過的分支執(zhí)行過的分支普通指令普通指令三三. .基于硬件的前瞻執(zhí)行基于硬件的前

9、瞻執(zhí)行1.1. 前瞻執(zhí)行（前瞻執(zhí)行（SpeculationSpeculation）的基本思想）的基本思想 對分支指令的結(jié)果進行猜測，并假設(shè)這個猜測總是對的，然后按這個猜測結(jié)果繼續(xù)取、流出和執(zhí)行后續(xù)的指令。只是執(zhí)行指令的結(jié)果不是寫回到寄存器或存儲器，而是放到一個稱為ROB（ReOrder Buffer）的緩沖器中。等到相應(yīng)的指令得到“確認確認” （commit）（即確實是應(yīng)該執(zhí)行的）之后，才將結(jié)果寫入寄存器或存儲器。4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)2.2.基于硬件的前瞻執(zhí)行結(jié)合了三種思想：基于硬件的前瞻執(zhí)行結(jié)合了三種思想：1）動態(tài)分支預(yù)測。用來選擇后續(xù)執(zhí)行的指令。2）在控制相關(guān)的結(jié)果尚未

10、出來之前，前瞻地執(zhí)行后續(xù)指令。3）用動態(tài)調(diào)度對基本塊的各種組合進行跨基本塊的調(diào)度。3.3.對對TomasuloTomasulo算法加以擴充，就可以支持前瞻執(zhí)行。算法加以擴充，就可以支持前瞻執(zhí)行。 把Tomasulo算法的寫結(jié)果和指令完成加以區(qū)分，分成兩個不同的段：n寫結(jié)果寫結(jié)果n指令確認指令確認 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)n寫結(jié)果段寫結(jié)果段把前瞻執(zhí)行的結(jié)果寫到ROB中；通過CDB在指令之間傳送結(jié)果，供需要用到這些結(jié)果的指令使用。n指令確認段指令確認段 在分支指令的結(jié)果出來后，對相應(yīng)指令的前瞻執(zhí)行給予確認。如果前面所做的猜測是對的，把在ROB中的結(jié)果寫到寄存器或存儲器。如果發(fā)現(xiàn)前面

11、對分支結(jié)果的猜測是錯誤的，那就不予以確認，并從那條分支指令的另一條路徑開始重新執(zhí)行。 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)支持前瞻執(zhí)行的浮點部件的結(jié)構(gòu) 從從指指令令部部件件來來 浮浮點點寄寄存存器器 FP 地地址址部部件件 load/store 操操作作 浮浮點點操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 store 數(shù)數(shù)據(jù)據(jù) 1 1 存存儲儲部部件件 浮浮點點加加法法器器 浮浮點點乘乘法法器器 指指令令隊隊列列 地地址址 2 3 2 3 4 5 6 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 ROB 數(shù)數(shù)據(jù)據(jù) 寄寄存存器器號號 緩緩沖沖器器 load store 地地

12、址址 保保留留站站 load 數(shù)數(shù)據(jù)據(jù) 介于保留站和寄介于保留站和寄存器組之間存器組之間支持前瞻執(zhí)行的浮點部件的結(jié)構(gòu) 從從指指令令部部件件來來 浮浮點點寄寄存存器器 FP 地地址址部部件件 load/store 操操作作 浮浮點點操操作作 操操作作數(shù)數(shù)總總線線 操操作作總總線線 store 數(shù)數(shù)據(jù)據(jù) 1 1 存存儲儲部部件件 浮浮點點加加法法器器 浮浮點點乘乘法法器器 指指令令隊隊列列 地地址址 2 3 2 3 4 5 6 公公共共數(shù)數(shù)據(jù)據(jù)總總線線（CDB） 1 2 保保留留站站 ROB 數(shù)數(shù)據(jù)據(jù) 寄寄存存器器號號 緩緩沖沖器器 load store 地地址址 保保留留站站 load 數(shù)數(shù)據(jù)據(jù)

13、 換名功能是由換名功能是由ROB來完成的。來完成的。 實現(xiàn)前瞻的關(guān)鍵思想：實現(xiàn)前瞻的關(guān)鍵思想： 允許指令亂序執(zhí)行，但必須允許指令亂序執(zhí)行，但必須順序確認。順序確認。4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)n采用前瞻執(zhí)行機制后，指令的執(zhí)行步驟：采用前瞻執(zhí)行機制后，指令的執(zhí)行步驟： 書書P132（在（在TomasuloTomasulo算法的基礎(chǔ)上改造的算法的基礎(chǔ)上改造的 ）1. 流出流出 n從浮點指令隊列的頭部取一條指令。從浮點指令隊列的頭部取一條指令。n如果有空閑的保留站（設(shè)為如果有空閑的保留站（設(shè)為r r）且有空閑的）且有空閑的ROBROB項（設(shè)為項（設(shè)為b b），），就流出該指令，并

14、把就流出該指令，并把相應(yīng)的信息相應(yīng)的信息放入保留站放入保留站r r和和ROBROB項項b b。n如果保留站或如果保留站或ROBROB全滿，便停止流出指令，直到它們都有空全滿，便停止流出指令，直到它們都有空閑的項。閑的項。 4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)2. 執(zhí)行執(zhí)行 n如果有操作數(shù)尚未就緒，就等待，并不斷地監(jiān)測如果有操作數(shù)尚未就緒，就等待，并不斷地監(jiān)測CDBCDB。 ( (檢測檢測RAWRAW沖突沖突) )n當兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指令的當兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指令的操作。操作。3. 寫結(jié)果寫結(jié)果 n當結(jié)果產(chǎn)生后，將該結(jié)果連同本指令

15、在流出段所分配到的當結(jié)果產(chǎn)生后，將該結(jié)果連同本指令在流出段所分配到的ROBROB項的編號放到項的編號放到CDBCDB上，經(jīng)上，經(jīng)CDBCDB寫到寫到ROBROB以及所有等待該結(jié)果的保以及所有等待該結(jié)果的保留站。留站。n釋放產(chǎn)生該結(jié)果的保留站。釋放產(chǎn)生該結(jié)果的保留站。n storestore指令指令在本階段完成，其操作為在本階段完成，其操作為: : 4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分支預(yù)測技術(shù)n如果要寫入存儲器的數(shù)據(jù)已經(jīng)就緒，就把該數(shù)據(jù)寫入分如果要寫入存儲器的數(shù)據(jù)已經(jīng)就緒，就把該數(shù)據(jù)寫入分配給該配給該storestore指令的指令的ROBROB項。項。n否則，就監(jiān)測否則，就監(jiān)測CDBCDB，

16、直到那個數(shù)據(jù)在，直到那個數(shù)據(jù)在CDBCDB上播送出來，這上播送出來，這時才將之寫入分配給該時才將之寫入分配給該storestore指令的指令的ROBROB項項。4. 確認確認 對對分支指令、分支指令、store指令指令以及以及其他指令其他指令的處理不同：的處理不同：n其他指令其他指令（除分支指令和除分支指令和storestore指令）指令） 當該指令到達當該指令到達ROBROB隊列的頭部而且其結(jié)果已經(jīng)隊列的頭部而且其結(jié)果已經(jīng)就緒時，就把該結(jié)果寫入該指令的目標寄存器，并從就緒時，就把該結(jié)果寫入該指令的目標寄存器，并從ROBROB中刪除該指令。中刪除該指令。 4.3 4.3 動態(tài)分支預(yù)測技術(shù)動態(tài)分

17、支預(yù)測技術(shù)nstorestore指令指令 處理與上面類似，只是它把結(jié)果寫入存儲器。處理與上面類似，只是它把結(jié)果寫入存儲器。n分支指令分支指令 n當預(yù)測錯誤的分支指令到達當預(yù)測錯誤的分支指令到達ROBROB隊列的頭部時，清空隊列的頭部時，清空ROBROB，并從分支指令的另一個分支重新開始執(zhí)行。并從分支指令的另一個分支重新開始執(zhí)行。 （錯誤的前瞻執(zhí)行）（錯誤的前瞻執(zhí)行）n當預(yù)測正確的分支指令到達當預(yù)測正確的分支指令到達ROBROB隊列的頭部時，該指令執(zhí)隊列的頭部時，該指令執(zhí)行完畢。行完畢。 n4.4 多指令流出技術(shù)4.4 4.4 多指令流出技術(shù)多指令流出技術(shù)一一. .單流出（單發(fā)射）處理機和多流出

18、（多發(fā)射）處理機單流出（單發(fā)射）處理機和多流出（多發(fā)射）處理機 1. 單流出處理機單流出處理機每個周期只取一條指令、只譯碼一條指令，只執(zhí)行一條指令，只寫回一個運算結(jié)果。（理想的CPI=1） 設(shè)計目標：設(shè)計目標：每個時鐘周期平均執(zhí)行一條指令，即指令并行度ILPILP期望值為期望值為1 1. IF 1 2 3 4 5 6 7 時鐘周期時鐘周期 指令指令 I1 I2 I3 ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB 單流出時空圖單流出時空圖 4.4 多指令流出技術(shù)多指令流出技術(shù)2. 多流出處理機多流出處理機( (多發(fā)射多發(fā)射) )n每個周期同時取多條指令

19、、同時譯碼多條指令，同時執(zhí)行多條指令，同時寫回多個運算結(jié)果。n需要多套（m）指令部件（取指部件和譯碼部件）和多個寫結(jié)果部件。設(shè)置多個指令執(zhí)行部件，有些指令部件采用流水線結(jié)構(gòu)。n設(shè)計目標：設(shè)計目標：一個時鐘周期內(nèi)流出多條指令， 指令并行度ILP1（CPI1）。 同時發(fā)射兩條指令的同時發(fā)射兩條指令的多發(fā)射處理機流水線：多發(fā)射處理機流水線： 1 2 3 4 5 6 7 時鐘周期時鐘周期 指令指令 I1 I2 I3 IF ID EX MEM WB IF IF ID ID EX EX MEM MEM WB WB IF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB

20、IF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB同時發(fā)射三條指令的多發(fā)射處理機的指令執(zhí)行時空圖同時發(fā)射三條指令的多發(fā)射處理機的指令執(zhí)行時空圖 4.4 多指令流出技術(shù)多指令流出技術(shù)二二. 多流出處理機有兩種基本結(jié)構(gòu)多流出處理機有兩種基本結(jié)構(gòu)1. 1. 超標量超標量處理機（空間并行）：處理機（空間并行）：n一個時鐘周期內(nèi)能夠同時同時發(fā)射多條指令的處理機稱為超標量處理機。 n最基本的要求是有兩套或兩套以上完整的指令執(zhí)行部件。n為了能夠在一個時鐘周期內(nèi)同時發(fā)射多條指令，超標量處理機必須有兩條或兩條以上能夠同時工作的指令流水線。4.4 多指令流出技術(shù)多指令流出技

21、術(shù)n目前的指令調(diào)度技術(shù)，每個周期發(fā)射2-4條指令比較合理。n例如：Intel公司的i860、i960、Pentium，IBM公司的Power 6000每個周期發(fā)射2條指令；Pentium 每個周期發(fā)射3條指令。n超標量處理機在每個時鐘周期流出的指令條數(shù)不固定，依代碼的具體情況而定。有上限，設(shè)這個上限為m，就稱該處理機為m-流出（發(fā)射m條指令）。n實際指令級并行度實際指令級并行度1 1ILPILPm mn可以通過編譯器進行靜態(tài)調(diào)度，也可以基于Tomasulo算法進行動態(tài)調(diào)度。 4.4 多指令流出技術(shù)多指令流出技術(shù)2. 2. 超長指令字超長指令字VLIWVLIW（Very Long Instruc

22、tion WordVery Long Instruction Word） 基本思路：基本思路：由編譯器在編譯時找出指令間潛在的并行性，進行適當調(diào)度安排，把多個能并行執(zhí)行的操作組合在一起，成為一條具有多個操作段的超長指令（100多位到幾百位），并設(shè)置多個功能部件。超長指令字被分割成一些操作段，每個字段稱為一個操作槽，直接獨立地控制一個功能部件。 VLIW處理機是一種單指令多操作碼多數(shù)據(jù)的系統(tǒng)結(jié)構(gòu)。處理機是一種單指令多操作碼多數(shù)據(jù)的系統(tǒng)結(jié)構(gòu)。第第k條指令條指令第第k + 1條指令條指令第第k + 2條指令條指令4.4 多指令流出技術(shù)多指令流出技術(shù)每拍啟動一條長每拍啟動一條長指令，執(zhí)行指令，執(zhí)行3個

23、個操作，相當于操作，相當于3條指令并行。條指令并行。n在每個時鐘周期流出的指令條數(shù)是固定的固定的，這些指令構(gòu)成一條長指令或者一個混合指令包。n指令包中，指令之間的并行性是通過指令顯式地表示出來的。n指令調(diào)度是由編譯器靜態(tài)完成的。4.4 多指令流出技術(shù)多指令流出技術(shù)三三. . 多流出流水線的調(diào)度問題多流出流水線的調(diào)度問題n順序發(fā)射與亂序發(fā)射：順序發(fā)射與亂序發(fā)射：指令發(fā)射順序是按照程序中指令排列順序進行的稱為順序發(fā)射(in-order issue)，否則，稱為亂序發(fā)射(out-order issue)。n順序完成與亂序完成：順序完成與亂序完成：指令完成順序是按照程序中指令排列順序進行的稱為順序完成

24、。否則，稱為亂序完成。n多流水的調(diào)度主要有三種方法：n順序發(fā)射順序完成順序發(fā)射順序完成n順序發(fā)射亂序完成順序發(fā)射亂序完成n亂序發(fā)射亂序完成亂序發(fā)射亂序完成4.4 多指令流出技術(shù)多指令流出技術(shù)n以如下指令為例，說明三種調(diào)度方法：以如下指令為例，說明三種調(diào)度方法：n 同時發(fā)射兩條指令的同時發(fā)射兩條指令的多發(fā)射處理機流水線：多發(fā)射處理機流水線：真數(shù)據(jù)相關(guān)真數(shù)據(jù)相關(guān)真數(shù)據(jù)相關(guān)真數(shù)據(jù)相關(guān)輸出相關(guān)輸出相關(guān)反相關(guān)反相關(guān)流水線流水線1流水線流水線2功能功能部件部件沖突沖突（1 1）順序發(fā)射順序完成）順序發(fā)射順序完成p 6 6條指令共用了條指令共用了1010個時鐘周期才完成。個時鐘周期才完成。p 有有8 8個空

25、閑的時鐘周期。個空閑的時鐘周期。指令流水線時空圖指令流水線時空圖(假設(shè)采用假設(shè)采用“定向技術(shù)定向技術(shù)”)：插入插入5個個空閑的時空閑的時鐘周期，鐘周期，為了維持為了維持順序完成。順序完成。（2 2）順序發(fā)射亂序完成）順序發(fā)射亂序完成p共需共需9 9個周期。僅有個周期。僅有3 3個個空閑周期?？臻e周期。p總執(zhí)行時間縮短了；總執(zhí)行時間縮短了；p功能部件利用率提高了。功能部件利用率提高了。FA3順序發(fā)射亂序完成的指令完成次序：順序發(fā)射亂序完成的指令完成次序：指令流水線時空圖：指令流水線時空圖：（3 3）亂序發(fā)射亂序完成）亂序發(fā)射亂序完成先行指令窗口：先行指令窗口： 能夠從指令能夠從指令Cache中預(yù)

26、取多條指令。多數(shù)超標量處理機的指令窗口大中預(yù)取多條指令。多數(shù)超標量處理機的指令窗口大小為小為2-8條指令。條指令。 能夠通過硬件對窗口內(nèi)的指令進行數(shù)據(jù)相關(guān)性分析和功能部件沖突的能夠通過硬件對窗口內(nèi)的指令進行數(shù)據(jù)相關(guān)性分析和功能部件沖突的檢測。可以把沒有功能部件沖突、沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令超越檢測?？梢园褯]有功能部件沖突、沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令超越它前面的指令先發(fā)射到操作部件中去。它前面的指令先發(fā)射到操作部件中去。（3 3）亂序發(fā)射亂序完成）亂序發(fā)射亂序完成p共需共需8 8個周期。無空個周期。無空閑周期。閑周期。p總執(zhí)行時間最短；總執(zhí)行時間最短；p功能部件利用率最高。功能部件利用率最

27、高。指令在流水線中的發(fā)射次序：指令在流水線中的發(fā)射次序：指令在流水線中的完成次序：指令在流水線中的完成次序：指令流水線時空圖：指令流水線時空圖：4.4 多指令流出技術(shù)多指令流出技術(shù)四、超流水線處理機四、超流水線處理機n兩種定義：在一個時鐘周期內(nèi)能夠分時分時發(fā)射多條指令的處理機稱為超超流水線處理機。流水線處理機。指令流水線的段數(shù)大于等于8的流水線處理機。n提高處理機性能的兩種方法：n通過增加硬件資源來提高處理機性能-超標量處理機n通過各部分硬件的重疊工作來提高處理機性能-超流水線處理機。n 對于一臺每個時鐘周期能流出n n條條指令的超流水線來說，這n條指令不是同時流出的，而是每隔1/n1/n個時

28、鐘周期流出一條指令。n 即處理機的流水線周期流水線周期為1/n1/n個時鐘周期。 IF IF IF IF WBMEM ID EX IF 1 2 3 4 5 6 7 時時鐘鐘周周期期 指指令令 I1 I2 I3 ID EX MEM WBI6 I5 I4 I7 ID EX MEM WBIF ID EX MEM WBID EX MEM WBIF ID EX MEM WBID EX MEM WB每個時鐘周期分時發(fā)射每個時鐘周期分時發(fā)射2條指令的超流水線處理機的指令執(zhí)行時空圖條指令的超流水線處理機的指令執(zhí)行時空圖4.4 多指令流出技術(shù)多指令流出技術(shù)1典型結(jié)構(gòu)典型結(jié)構(gòu)MIPS R4000采用8級超流水線結(jié)

29、構(gòu)n每個時鐘周期包含兩個流水段；n是一種很標準的超流水線處理機結(jié)構(gòu)；n指令流水線有8個流水段；n指令Cache和數(shù)據(jù)Cache的容量各8KB；n每個時鐘周期可以訪問Cache兩次；n在一個時鐘周期內(nèi)可以從指令Cache中讀出兩條指令，從數(shù)據(jù)Cache中讀出或?qū)懭雰蓚€數(shù)據(jù)。n主要運算部件有整數(shù)部件和浮點部件。4.4 多指令流出技術(shù)多指令流出技術(shù)nMIPS R4000的的8級流水線結(jié)構(gòu)圖級流水線結(jié)構(gòu)圖一個時鐘周期一個時鐘周期一個時鐘周期一個時鐘周期4.4 多指令流出技術(shù)多指令流出技術(shù)4.4 多指令流出技術(shù)多指令流出技術(shù)n每個時鐘周期分時發(fā)射2條指令的超流水線處理機的指令執(zhí)行時空圖如下： WB WB

30、 時鐘周期時鐘周期 IF IS RF EX DF DS TC IF IS RF EX DF DS WB IF IS RF EX DF TC WB IF IS RF EX DS TC WB IF IS RF DF DS TC WB IF IS EX DF DS TC IF RF EX DF DS TC WB IS RF EX DF DS TC 周期周期 流水流水 線線 當前當前 CPU 周期周期 WB TC DS DF EX RF IS IF 2 2、與超標量機提高處理機性能的途徑不同、與超標量機提高處理機性能的途徑不同n超標量處理機超標量處理機通過重復(fù)設(shè)置多個“取指令”部件，多個“譯碼”、“執(zhí)

31、行”和“寫回結(jié)果”部件，使其同時工作來提高指令的執(zhí)行速度，以增加硬件資源為代價來換取處理機性能。n超流水線處理機超流水線處理機只需要增加少量硬件，是通過各部分硬件的充分重疊工作來提高處理機性能的。4.4 4.4 多指令流出技術(shù)多指令流出技術(shù) 從流水線的時從流水線的時空圖上看，超空圖上看，超標量處理機采標量處理機采用的是空間并用的是空間并行性，而超流行性，而超流水線處理機采水線處理機采用的是時間并用的是時間并行性。行性。機器類型機器類型k k段流水線基準標段流水線基準標量處理量處理m m度超標量處理機度超標量處理機n n度超流水線處理機度超流水線處理機機器流水線周期機器流水線周期1 1個時鐘周期

32、個時鐘周期1 1個時鐘周期個時鐘周期1/n1/n個時鐘周期個時鐘周期同時發(fā)射指令條數(shù)同時發(fā)射指令條數(shù)1 1m m1 1指令發(fā)射等待時間指令發(fā)射等待時間1 1個時鐘周期個時鐘周期1 1個時鐘周期個時鐘周期1/n1/n個時鐘周期個時鐘周期指令級并行度指令級并行度ILPILP （期望值）（期望值）1 1m mn n三種不同類型處理機的性能比較三種不同類型處理機的性能比較4.4 4.4 多指令流出技術(shù)多指令流出技術(shù)n4.5 循環(huán)展開和指令調(diào)度4.5 4.5 循環(huán)展開和指令調(diào)度循環(huán)展開和指令調(diào)度n 增加指令間并行性最簡單和最常用的方法：n開發(fā)循環(huán)級并行性循環(huán)的不同迭代之間存在的并行性。n在編譯時多次展開

33、循環(huán)體，再對指令序列重新排序，以進一步提高流水線的并行性。例：例：對于下面的源代碼，轉(zhuǎn)換成MIPS匯編語言， 在不進行指令調(diào)度和進行指令調(diào)度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時間。 for (i=1； i=1000； i+) xi = xi + s；解：把該程序翻譯成MIPS匯編語言代碼： 假設(shè)R1的初值是指向第一個元素，8（R2）指向最后一個元素；浮點寄存器F2保存常數(shù)s。 Loop：L.D F0F0, 0(R1)/取數(shù) ADD.D F4F4, F0F0, F2 /相加 S.D F4F4, 0(R1) /存數(shù) DADDIU R1R1, R1，#-8 /指針減8 BNE R1R1, R2

34、, Loop/ (R1) (R2),轉(zhuǎn)移到LOOP4.5 循環(huán)展開和指令調(diào)度循環(huán)展開和指令調(diào)度 各操作時間不等,為保證流水線正常工作，插入等待周期。 指令流出時鐘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)） 10n 每個元素的操作需要每個元素的操作需要10個個時鐘周時鐘周期，其中期，其中5個個是空轉(zhuǎn)周期。是空轉(zhuǎn)周期。 對該循環(huán)體進行調(diào)度調(diào)度，執(zhí)行時間由10個周期縮減為6個周期。 指令

35、流出時鐘Loop: L.D F0, 0(R1) 1 DADDIU R1, R1, #-82 ADD.D F4, F0, F23 （空轉(zhuǎn)）4 BNE R1, Loop 5 S.D F4，8(R1) 64.5 循環(huán)展開和指令調(diào)度循環(huán)展開和指令調(diào)度u只有只有L.D、ADD.D和和S.D這這3條指令條指令是有效操作。占用是有效操作。占用3個時鐘周期。個時鐘周期。u而而DADDIU、空轉(zhuǎn)和、空轉(zhuǎn)和BEN這這3個時鐘個時鐘周期都是附加的循環(huán)控制開銷。周期都是附加的循環(huán)控制開銷。n循環(huán)展開技術(shù)：循環(huán)展開技術(shù)：n把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。n這給編譯器進行指令調(diào)度帶來了更大的空間。這