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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、、同時(shí)譯碼多條指令，同時(shí)執(zhí)行多條指令，同時(shí)寫(xiě)回多個(gè)運(yùn)算結(jié)果。n需要多套（m）指令部件（取指部件和譯碼部件）和多個(gè)寫(xiě)結(jié)果部件。設(shè)置多個(gè)指令執(zhí)行部件，有些指令部件采用流水線(xiàn)結(jié)構(gòu)。n設(shè)計(jì)目標(biāo)：設(shè)計(jì)目標(biāo)：一個(gè)時(shí)鐘周期內(nèi)流出多條指令， 指令并行度ILP1（CPI1）。 同時(shí)發(fā)射兩條指令的同時(shí)發(fā)射兩條指令的多發(fā)射處理機(jī)流水線(xiàn)：多發(fā)射處理機(jī)流水線(xiàn)： 1 2 3 4 5 6 7 時(shí)鐘周期時(shí)鐘周期 指令指令 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同時(shí)發(fā)射三條指令的多發(fā)射處理機(jī)的指令執(zhí)行時(shí)空?qǐng)D同時(shí)發(fā)射三條指令的多發(fā)射處理機(jī)的指令執(zhí)行時(shí)空?qǐng)D 4.4 多指令流出技術(shù)多指令流出技術(shù)二二. 多流出處理機(jī)有兩種基本結(jié)構(gòu)多流出處理機(jī)有兩種基本結(jié)構(gòu)1. 1. 超標(biāo)量超標(biāo)量處理機(jī)（空間并行）：處理機(jī)（空間并行）：n一個(gè)時(shí)鐘周期內(nèi)能夠同時(shí)同時(shí)發(fā)射多條指令的處理機(jī)稱(chēng)為超標(biāo)量處理機(jī)。 n最基本的要求是有兩套或兩套以上完整的指令執(zhí)行部件。n為了能夠在一個(gè)時(shí)鐘周期內(nèi)同時(shí)發(fā)射多條指令，超標(biāo)量處理機(jī)必須有兩條或兩條以上能夠同時(shí)工作的指令流水線(xiàn)。4.4 多指令流出技術(shù)多指令流出技

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

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

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

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

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

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

27、高。指令在流水線(xiàn)中的發(fā)射次序：指令在流水線(xiàn)中的發(fā)射次序：指令在流水線(xiàn)中的完成次序：指令在流水線(xiàn)中的完成次序：指令流水線(xiàn)時(shí)空?qǐng)D：指令流水線(xiàn)時(shí)空?qǐng)D：4.4 多指令流出技術(shù)多指令流出技術(shù)四、超流水線(xiàn)處理機(jī)四、超流水線(xiàn)處理機(jī)n兩種定義：在一個(gè)時(shí)鐘周期內(nèi)能夠分時(shí)分時(shí)發(fā)射多條指令的處理機(jī)稱(chēng)為超超流水線(xiàn)處理機(jī)。流水線(xiàn)處理機(jī)。指令流水線(xiàn)的段數(shù)大于等于8的流水線(xiàn)處理機(jī)。n提高處理機(jī)性能的兩種方法：n通過(guò)增加硬件資源來(lái)提高處理機(jī)性能-超標(biāo)量處理機(jī)n通過(guò)各部分硬件的重疊工作來(lái)提高處理機(jī)性能-超流水線(xiàn)處理機(jī)。n 對(duì)于一臺(tái)每個(gè)時(shí)鐘周期能流出n n條條指令的超流水線(xiàn)來(lái)說(shuō)，這n條指令不是同時(shí)流出的，而是每隔1/n1/n個(gè)時(shí)

28、鐘周期流出一條指令。n 即處理機(jī)的流水線(xiàn)周期流水線(xiàn)周期為1/n1/n個(gè)時(shí)鐘周期。 IF IF IF IF WBMEM ID EX IF 1 2 3 4 5 6 7 時(shí)時(shí)鐘鐘周周期期 指指令令 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每個(gè)時(shí)鐘周期分時(shí)發(fā)射每個(gè)時(shí)鐘周期分時(shí)發(fā)射2條指令的超流水線(xiàn)處理機(jī)的指令執(zhí)行時(shí)空?qǐng)D條指令的超流水線(xiàn)處理機(jī)的指令執(zhí)行時(shí)空?qǐng)D4.4 多指令流出技術(shù)多指令流出技術(shù)1典型結(jié)構(gòu)典型結(jié)構(gòu)MIPS R4000采用8級(jí)超流水線(xiàn)結(jié)

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

30、 時(shí)鐘周期時(shí)鐘周期 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 周期周期 流水流水 線(xiàn)線(xiàn) 當(dāng)前當(dāng)前 CPU 周期周期 WB TC DS DF EX RF IS IF 2 2、與超標(biāo)量機(jī)提高處理機(jī)性能的途徑不同、與超標(biāo)量機(jī)提高處理機(jī)性能的途徑不同n超標(biāo)量處理機(jī)超標(biāo)量處理機(jī)通過(guò)重復(fù)設(shè)置多個(gè)“取指令”部件，多個(gè)“譯碼”、“執(zhí)

31、行”和“寫(xiě)回結(jié)果”部件，使其同時(shí)工作來(lái)提高指令的執(zhí)行速度，以增加硬件資源為代價(jià)來(lái)?yè)Q取處理機(jī)性能。n超流水線(xiàn)處理機(jī)超流水線(xiàn)處理機(jī)只需要增加少量硬件，是通過(guò)各部分硬件的充分重疊工作來(lái)提高處理機(jī)性能的。4.4 4.4 多指令流出技術(shù)多指令流出技術(shù) 從流水線(xiàn)的時(shí)從流水線(xiàn)的時(shí)空?qǐng)D上看，超空?qǐng)D上看，超標(biāo)量處理機(jī)采標(biāo)量處理機(jī)采用的是空間并用的是空間并行性，而超流行性，而超流水線(xiàn)處理機(jī)采水線(xiàn)處理機(jī)采用的是時(shí)間并用的是時(shí)間并行性。行性。機(jī)器類(lèi)型機(jī)器類(lèi)型k k段流水線(xiàn)基準(zhǔn)標(biāo)段流水線(xiàn)基準(zhǔn)標(biāo)量處理量處理m m度超標(biāo)量處理機(jī)度超標(biāo)量處理機(jī)n n度超流水線(xiàn)處理機(jī)度超流水線(xiàn)處理機(jī)機(jī)器流水線(xiàn)周期機(jī)器流水線(xiàn)周期1 1個(gè)時(shí)鐘周期

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

33、循環(huán)體，再對(duì)指令序列重新排序，以進(jìn)一步提高流水線(xiàn)的并行性。例：例：對(duì)于下面的源代碼，轉(zhuǎn)換成MIPS匯編語(yǔ)言， 在不進(jìn)行指令調(diào)度和進(jìn)行指令調(diào)度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時(shí)間。 for (i=1； i=1000； i+) xi = xi + s；解：把該程序翻譯成MIPS匯編語(yǔ)言代碼： 假設(shè)R1的初值是指向第一個(gè)元素，8（R2）指向最后一個(gè)元素；浮點(diǎn)寄存器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)展開(kāi)和指令調(diào)度循環(huán)展開(kāi)和指令調(diào)度 各操作時(shí)間不等,為保證流水線(xiàn)正常工作，插入等待周期。 指令流出時(shí)鐘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 每個(gè)元素的操作需要每個(gè)元素的操作需要10個(gè)個(gè)時(shí)鐘周時(shí)鐘周期，其中期，其中5個(gè)個(gè)是空轉(zhuǎn)周期。是空轉(zhuǎn)周期。 對(duì)該循環(huán)體進(jìn)行調(diào)度調(diào)度，執(zhí)行時(shí)間由10個(gè)周期縮減為6個(gè)周期。 指令

35、流出時(shí)鐘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)展開(kāi)和指令調(diào)度循環(huán)展開(kāi)和指令調(diào)度u只有只有L.D、ADD.D和和S.D這這3條指令條指令是有效操作。占用是有效操作。占用3個(gè)時(shí)鐘周期。個(gè)時(shí)鐘周期。u而而DADDIU、空轉(zhuǎn)和、空轉(zhuǎn)和BEN這這3個(gè)時(shí)鐘個(gè)時(shí)鐘周期都是附加的循環(huán)控制開(kāi)銷(xiāo)。周期都是附加的循環(huán)控制開(kāi)銷(xiāo)。n循環(huán)展開(kāi)技術(shù)：循環(huán)展開(kāi)技術(shù)：n把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。把循環(huán)體的代碼復(fù)制多次并按順序排列，然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。n這給編譯器進(jìn)行指令調(diào)度帶來(lái)了更大的空間。這