第4章指令級并行

1、1 1/135/135第4章 指令級并行張晨曦張晨曦 劉依劉依www.A微信公眾號： arch3652 2/135/1354.1指令級并行的概念4.2指令的動態(tài)調度4.3動態(tài)分支預測技術4.4多指令流出技術4.5循環(huán)展開和指令調度3 3/135/135幾乎所有的處理機都利用流水線來使指令重疊并行執(zhí)行，以達到提高性能的目的。這種指令之間存在的潛在并行性稱為指令級并行。 （ILPILP：Instruction-Level ParallelismInstruction-Level Parallelism）本章研究：如何通過各種可能的技術，獲得更多的指令級并行性。 硬件軟件技術硬件軟件技術 必須要硬件

2、技術和軟件技術互相配合，才能夠最大必須要硬件技術和軟件技術互相配合，才能夠最大限度地挖掘出程序中存在的指令級并行。限度地挖掘出程序中存在的指令級并行。4.1 指令級并行4.1.1 指令級并行的概念4 4/135/1354.1 指令級并行1. 流水線處理機的實際CPI理想流水線的CPI加上各類停頓的時鐘周期數(shù)： CPICPI流水線流水線 = CPI= CPI理想理想 + + 停頓停頓結構沖突結構沖突 + + 停頓停頓數(shù)據(jù)沖突數(shù)據(jù)沖突 + + 停頓停頓控制沖突控制沖突理想CPI是衡量流水線最高性能的一個指標。IPC：Instructions Per Cycle （每個時鐘周期完成的指令條數(shù)）（每個

3、時鐘周期完成的指令條數(shù)）2. 基本程序塊基本程序塊：一段除了入口和出口以外不包含其他分支的線性代碼段。程序平均每57條指令就會有一個分支。5 5/135/1354.1 指令級并行3. 循環(huán)級并行：使一個循環(huán)中的不同循環(huán)體并行執(zhí)行。開發(fā)循環(huán)體中存在的并行性q最常見、最基本最常見、最基本指令級并行研究的重點之一 例如，考慮下述語句： for for （i=1i=1； i=500i2n2）分支預測的性能差不多。分支預測的性能差不多。兩位分支預測的狀態(tài)轉換如下所示： 分支預測：分支預測： 不成功不成功 分支預測：分支預測： 成功成功 11 10 分支不成功分支不成功 分支成功分支成功 分支不成功分支不

4、成功 分支成功分支成功 01 00 分支不成功分支不成功 分支成功分支成功 分支不成功分支不成功 分支成功分支成功 5858/135/1354.3 動態(tài)分支預測技術兩位分支預測中的操作有兩個步驟：q分支預測。分支預測。n當分支指令到達譯碼段當分支指令到達譯碼段（IDID）時，根據(jù)從時，根據(jù)從BHTBHT讀出讀出的信息進行分支預測的信息進行分支預測 。n若預測正確，就繼續(xù)處理后續(xù)的指令，流水線沒若預測正確，就繼續(xù)處理后續(xù)的指令，流水線沒有斷流。否則，就要作廢已經預取和分析的指令，有斷流。否則，就要作廢已經預取和分析的指令，恢復現(xiàn)場，并從另一條分支路徑重新取指令?；謴同F(xiàn)場，并從另一條分支路徑重新取

5、指令。 q狀態(tài)修改。狀態(tài)修改。 4. BHT方法只在以下情況下才有用：判定分支是否成功所需的時間大于確定分支目標地址所需的時間。 5959/135/1354.3 動態(tài)分支預測技術前述前述5 5段經典流水線段經典流水線：由于判定分支是否成功和計算：由于判定分支是否成功和計算分支目標地址都是在分支目標地址都是在IDID段完成，所以段完成，所以BHTBHT方法不會給方法不會給該流水線帶來好處。該流水線帶來好處。5. 研究結果表明：對于SPEC89測試程序來說，具有大小為4K的BHT的預測準確率為82%99%。 一般來說，采用一般來說，采用4K4K的的BHTBHT就可以了。就可以了。 6. BHT可以

6、跟分支指令一起存放在指令Cache中，也可以用一個專門的硬件來實現(xiàn)。 6060/135/1354.3 動態(tài)分支預測技術目標：將分支的開銷降為 0方法：分支目標緩沖將分支成功的分支指令的地址和它的分支目標地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令的地址作為標識。這個緩沖區(qū)就是分支目標緩沖器（Branch-Target Buffer，簡記為BTB，或者Branch-Target Cache）。 4.3.2 采用分支目標緩沖器BTB6161/135/1354.3 動態(tài)分支預測技術1. BTB的結構 N = =？ 當前取指令的地址當前取指令的地址 地址標識地址標識 分支目標地址分支目標地址 查找

7、查找 認為本指令不是分支指令，認為本指令不是分支指令， 按普通指令正常執(zhí)行。按普通指令正常執(zhí)行。 Y 認為該指令是成功的分支指令，用認為該指令是成功的分支指令，用 分支目標地址作為下一條指令的分支目標地址作為下一條指令的 PCPC值。值。 6262/135/1354.3 動態(tài)分支預測技術看成是用專門的硬件實現(xiàn)的一張表格。 表格中的每一項至少有兩個字段： q執(zhí)行過的成功分支指令的地址；執(zhí)行過的成功分支指令的地址；（作為該表的匹配標識（作為該表的匹配標識 ）q預測的分支目標地址。預測的分支目標地址。2. 采用BTB后，在流水線各個階段所進行的相關操作： 當當前前 P PC C 值值 B BT TB

8、 B 中中存存在在匹匹配配的的項項？ 成成功功分分支支指指令令？ 當當前前分分支支成成功功？ 以以 B BT TB B 的的第第二二字字段段作作為為 否否 否否 正正常常執(zhí)執(zhí)行行指指令令 是是 是是 否否 分分支支預預測測正正確確， 繼繼續(xù)續(xù)執(zhí)執(zhí)行行后后繼繼指指令令， 指令無 不不會會出出現(xiàn)現(xiàn)停停頓頓。 分分支支預預測測錯錯誤誤，清清除除 已已取取的的指指令令，并并從從另另 一一個個分分支支（即即失失敗敗處處） 取取指指令令。從從 B BT TB B 中中刪刪 除除相相應應的的項項。 將將其其 P PC C 值值和和分分支支 目目標標地地址址寫寫入入 B BT TB B 中中，作作為為一一個個

9、新新項項。 I IF F 段段 I ID D 段段 E EX X 段段 送送存存儲儲器器和和 B BT TB B 分分支支目目標標地地址址送送給給 P PC C 是是 6464/135/1354.3 動態(tài)分支預測技術3. 采用BTB后，各種可能情況下的延遲 ：指令在指令在BTBBTB中？中？ 預測預測 實際情況實際情況 延遲周期延遲周期 是是 成功成功 成功成功 0 0 是是 成功成功 不成功不成功 2 2 不是不是 成功成功 2 2 不是不是 不成功不成功 0 0 6565/135/1354.3 動態(tài)分支預測技術4. BTB的另一種形式 在分支目標緩沖器中存放一條或者多條分支目標處的指令。有

10、三個潛在的好處：q更快地獲得分支目標處的指令；更快地獲得分支目標處的指令；q可以一次提供分支目標處的多條指令，這對于多流出可以一次提供分支目標處的多條指令，這對于多流出處理器是很有必要的；處理器是很有必要的；q使我們可以進行稱為使我們可以進行稱為分支折疊分支折疊（branch foldingbranch folding）的優(yōu)化。的優(yōu)化。 實現(xiàn)零延遲無條件分支，甚至有時還可以做到實現(xiàn)零延遲無條件分支，甚至有時還可以做到零延遲條件分支。零延遲條件分支。6666/135/135 當當前前取取指指令令的的地地址址PC 相相聯(lián)聯(lián)查查找找 分分支支指指令令地地址址 A0 A1 Ak-1 分分支支目目標標處

11、處的的若若干干條條指指令令 I0,0，I0,1，I0,n-1 分分支支歷歷史史表表B BH HT T T0 T1 Tk-1 I1,0，I1,1，I1,n-1 Ik-1,0，Ik-1,1，Ik-1,n-1 6767/135/1354.3 動態(tài)分支預測技術前瞻執(zhí)行（speculation）的基本思想： 對分支指令的結果進行猜測，并假設這個猜測總是對的，然后按這個猜測結果繼續(xù)取、流出和執(zhí)行后續(xù)的指令。只是執(zhí)行指令的結果不是寫回到寄存器或存儲器，而是放到一個稱為ROB（ReOrder Buffer）的緩沖器中。等到相應的指令得到“確認”（commit）（即確實是應該執(zhí)行的）之后，才將結果寫入寄存器或存

12、儲器。 4.3.3 基于硬件的前瞻執(zhí)行6868/135/1354.3 動態(tài)分支預測技術1. 基于硬件的前瞻執(zhí)行結合了三種思想：動態(tài)分支預測。用來選擇后續(xù)執(zhí)行的指令。在控制相關的結果尚未出來之前，前瞻地執(zhí)行后續(xù)指令。用動態(tài)調度對基本塊的各種組合進行跨基本塊的調度。2. 對Tomasulo算法加以擴充，就可以支持前瞻執(zhí)行。 把Tomasulo算法的寫結果和指令完成加以區(qū)分，分成兩個不同的段： 寫結果寫結果，指令確認指令確認 6969/135/1354.3 動態(tài)分支預測技術寫結果段q把前瞻執(zhí)行的結果寫到把前瞻執(zhí)行的結果寫到ROBROB中；中；q通過通過CDBCDB在指令之間傳送結果，供需要用到這些結

13、果在指令之間傳送結果，供需要用到這些結果的指令使用。的指令使用。指令確認段 在分支指令的結果出來后，對相應指令的前瞻執(zhí)行在分支指令的結果出來后，對相應指令的前瞻執(zhí)行給予確認。給予確認。q如果前面所做的猜測是對的，把在如果前面所做的猜測是對的，把在ROBROB中的結果寫到中的結果寫到寄存器或存儲器。寄存器或存儲器。q如果發(fā)現(xiàn)前面對分支結果的猜測是錯誤的，那就不予如果發(fā)現(xiàn)前面對分支結果的猜測是錯誤的，那就不予以確認，并從那條分支指令的另一條路徑開始重新執(zhí)以確認，并從那條分支指令的另一條路徑開始重新執(zhí)行。行。 7070/135/1354.3 動態(tài)分支預測技術3. 實現(xiàn)前瞻的關鍵思想： 允許指令亂序執(zhí)

14、行，但必須順序確認。4. 支持前瞻執(zhí)行的浮點部件的結構 從指令部件來從指令部件來 浮點寄存器浮點寄存器 FP 地址部件地址部件 load/store 操作操作 浮點操作浮點操作 操作數(shù)總線操作數(shù)總線 操作總線操作總線 store數(shù)據(jù)數(shù)據(jù) 1 1 存儲部件存儲部件 浮點加法器浮點加法器 浮點乘法器浮點乘法器 指令隊列指令隊列 地址地址 2 3 2 3 4 5 6 公共數(shù)據(jù)總線（公共數(shù)據(jù)總線（CDB） 1 2 保留站保留站 ROB 數(shù)據(jù)數(shù)據(jù) 寄存器號寄存器號 緩沖器緩沖器 load store地址地址 保留站保留站 load 數(shù)據(jù)數(shù)據(jù) 7272/135/1354.3 動態(tài)分支預測技術ROB中的每一

15、項由以下4個字段組成：q指令類型指令類型 指出該指令是分支指令、指出該指令是分支指令、storestore指令或寄存器操作指令。指令或寄存器操作指令。q目標地址目標地址 給出指令執(zhí)行結果應寫入的目標寄存器號（如果是給出指令執(zhí)行結果應寫入的目標寄存器號（如果是 loadload和和ALUALU指令）或存儲器單元的地址（如果是指令）或存儲器單元的地址（如果是storestore指指 令）。令）。q數(shù)據(jù)值字段數(shù)據(jù)值字段 用來保存指令前瞻執(zhí)行的結果，直到指令得到確認。用來保存指令前瞻執(zhí)行的結果，直到指令得到確認。q就緒字段就緒字段 指出指令是否已經完成執(zhí)行并且數(shù)據(jù)已就緒。指出指令是否已經完成執(zhí)行并且數(shù)

16、據(jù)已就緒。7373/135/1354.3 動態(tài)分支預測技術Tomasulo算法中保留站的換名功能是由ROB來完成的。 5. 采用前瞻執(zhí)行機制后，指令的執(zhí)行步驟：（在（在TomasuloTomasulo算法的基礎上改造的算法的基礎上改造的 ）流出 q從浮點指令隊列的頭部取一條指令。從浮點指令隊列的頭部取一條指令。q如果有空閑的保留站（設為如果有空閑的保留站（設為r r）且有空閑的）且有空閑的ROBROB項（設項（設為為b b），就流出該指令，并把相應的信息放入保留站），就流出該指令，并把相應的信息放入保留站r r和和ROBROB項項b b。q如果保留站或如果保留站或ROBROB全滿，便停止流出指

17、令，直到它們全滿，便停止流出指令，直到它們都有空閑的項。都有空閑的項。 7474/135/1354.3 動態(tài)分支預測技術執(zhí)行 q如果有操作數(shù)尚未就緒，就等待，并不斷地監(jiān)測如果有操作數(shù)尚未就緒，就等待，并不斷地監(jiān)測CDBCDB。 ( (檢測檢測RAWRAW沖突沖突) )q當兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指當兩個操作數(shù)都已在保留站中就緒后，就可以執(zhí)行該指令的操作。令的操作。寫結果 q當結果產生后，將該結果連同本指令在流出段所分配到當結果產生后，將該結果連同本指令在流出段所分配到的的ROBROB項的編號放到項的編號放到CDBCDB上，經上，經CDBCDB寫到寫到ROBROB以及所有等待

18、以及所有等待該結果的保留站。該結果的保留站。q釋放產生該結果的保留站。釋放產生該結果的保留站。q storestore指令指令在本階段完成，其操作為在本階段完成，其操作為: : 7575/135/1354.3 動態(tài)分支預測技術n如果要寫入存儲器的數(shù)據(jù)已經就緒，就把該數(shù)如果要寫入存儲器的數(shù)據(jù)已經就緒，就把該數(shù)據(jù)寫入分配給該據(jù)寫入分配給該storestore指令的指令的ROBROB項。項。n否則，就監(jiān)測否則，就監(jiān)測CDBCDB，直到那個數(shù)據(jù)在，直到那個數(shù)據(jù)在CDBCDB上播送上播送出來，這時才將之寫入分配給該出來，這時才將之寫入分配給該storestore指令的指令的ROBROB項項。確認 對分支

19、指令、storestore指令以及其他指令的處理不同：q其他指令其他指令（除分支指令和除分支指令和storestore指令）指令） 當該指令到達當該指令到達ROBROB隊列的頭部而且其結果已經隊列的頭部而且其結果已經就緒時，就把該結果寫入該指令的目標寄存器，并從就緒時，就把該結果寫入該指令的目標寄存器，并從ROBROB中刪除該指令。中刪除該指令。 7676/135/1354.3 動態(tài)分支預測技術qstorestore指令指令 處理與上面類似，只是它把結果寫入存儲器。處理與上面類似，只是它把結果寫入存儲器。q分支指令分支指令 n當預測錯誤的分支指令到達當預測錯誤的分支指令到達ROBROB隊列的頭

20、部時，隊列的頭部時，清空清空ROBROB，并從分支指令的另一個分支重新開始，并從分支指令的另一個分支重新開始執(zhí)行。執(zhí)行。 （錯誤的前瞻執(zhí)行）（錯誤的前瞻執(zhí)行）n當預測正確的分支指令到達當預測正確的分支指令到達ROBROB隊列的頭部時，隊列的頭部時，該指令執(zhí)行完畢。該指令執(zhí)行完畢。 7777/135/1354.3 動態(tài)分支預測技術 例例4.34.3 假設浮點功能部件的延遲時間為：加法假設浮點功能部件的延遲時間為：加法2 2個時鐘周期，個時鐘周期，乘法乘法1010個時鐘周期，除法個時鐘周期，除法4040個時鐘周期。對于下面的代碼段，個時鐘周期。對于下面的代碼段，給出當指令給出當指令MUL.DMUL

21、.D即將確認時的狀態(tài)表內容。即將確認時的狀態(tài)表內容。 L.D L.D F6,34F6,34（R2R2） L.D L.D F2,45F2,45（R3R3） MUL.D F0,F2,F4 MUL.D F0,F2,F4 SUB.D F8,F6,F2 SUB.D F8,F6,F2 DIV.D F10,F0,F6 DIV.D F10,F0,F6 ADD.D F6,F8,F2 ADD.D F6,F8,F27878/135/1354.3 動態(tài)分支預測技術名稱名稱 保留站保留站 Busy Op Vj Vk Qj Qk Dest A Add1 no Add2 no Add3 no Mult1 no MUL Me

22、m45+ RegsR2 RegsF4 #3 Mult2 yes DIV Mem34+RegsR2 #3 #5 前瞻執(zhí)行中MUL.D確認前，保留站和ROB的狀態(tài) 項號項號 ROB Busy 指令指令 狀態(tài)狀態(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í)行執(zhí)

23、行 F10 6yes ADD.D F6,F8,F2 寫結果寫結果 F6 #4#2 字段字段 浮點寄存器狀態(tài)浮點寄存器狀態(tài) F0 F2 F4 F6 F8 F10 F30 ROB項編號 3645Busy yes no no yes yes yes no8080/135/1354.3 動態(tài)分支預測技術6. 前瞻執(zhí)行通過ROB實現(xiàn)了指令的順序完成。能夠實現(xiàn)精確異常。很容易地推廣到整數(shù)寄存器和整數(shù)功能單元上。 主要缺點：所需的硬件太復雜。 8181/135/135一個時鐘周期內流出多條指令， CPI1。單流出和多流出處理機執(zhí)行指令的時空圖對比 4.4 多指令流出技術8282/135/135 IF 1 2

24、 3 4 5 6 7 時鐘周期時鐘周期 指令指令 I1 I2 I3 ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB1 2 3 4 5 6 7 時鐘周期時鐘周期 指令指令 I1 I2 I3 IF ID EX MEM WBIF IF ID ID EX EX MEM MEM WBWBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WBIF ID EX MEM WB單流出時空圖單流出時空圖 多流出時空圖多流出時空圖 單流出和多流出處理機執(zhí)行指令的時空圖單流出和多流出處

25、理機執(zhí)行指令的時空圖 4.4 多指令流出技術8383/135/1354.4 多指令流出技術1. 多流出處理機有兩種基本風格超標量（Superscalar）q在每個時鐘周期流出的指令條數(shù)在每個時鐘周期流出的指令條數(shù)不固定不固定，依代碼的具，依代碼的具體情況而定。（有上限）體情況而定。（有上限）q設這個上限為設這個上限為n n，就稱該處理機為，就稱該處理機為n n流出。流出。q可以通過編譯器進行靜態(tài)調度，也可以基于可以通過編譯器進行靜態(tài)調度，也可以基于TomasuloTomasulo算法進行動態(tài)調度。算法進行動態(tài)調度。 超長指令字VLIW（Very Long Instruction Word）q在

26、每個時鐘周期流出的指令條數(shù)是在每個時鐘周期流出的指令條數(shù)是固定的固定的，這些指令，這些指令構成一條長指令或者一個指令包。構成一條長指令或者一個指令包。q指令包中，指令之間的并行性是通過指令顯式地表示指令包中，指令之間的并行性是通過指令顯式地表示出來的。出來的。q指令調度是由編譯器靜態(tài)完成的。指令調度是由編譯器靜態(tài)完成的。 8484/135/1354.4 多指令流出技術2. 超標量處理機與VLIW處理機相比有兩個優(yōu)點：超標量結構對程序員是透明的，因為處理機能自己檢測下一條指令能否流出，從而不需要重新排列指令來滿足指令的流出。即使是沒有經過編譯器針對超標量結構進行調度優(yōu)化的代碼或是舊的編譯器生成的

27、代碼也可以運行，當然運行的效果不會很好。q要想達到很好的效果，方法之一：要想達到很好的效果，方法之一： 使用動態(tài)超標量調度技術。使用動態(tài)超標量調度技術。3. 下表列出了一些基本的多流出技術、這些技術的特點以及采用這些技術的處理機例子。技技 術術 流出流出結構結構 沖突沖突檢測檢測 調調 度度 主要特點主要特點 處理機實例處理機實例 超標量超標量（靜態(tài)）（靜態(tài)） 動態(tài)動態(tài) 硬件硬件 靜態(tài)靜態(tài)順序執(zhí)行順序執(zhí)行 Sun UltraSPARC/ 超標量超標量（動態(tài)）（動態(tài)） 動態(tài)動態(tài) 硬件硬件 動態(tài)動態(tài)部分亂序執(zhí)行部分亂序執(zhí)行 IBM Power2 超標量超標量（猜測）（猜測） 動態(tài)動態(tài) 硬件硬件 帶

28、有猜帶有猜測的動測的動態(tài)執(zhí)行態(tài)執(zhí)行 帶有猜測的帶有猜測的亂序執(zhí)行亂序執(zhí)行 Pentium /4，MIPS R10K，Alpha 21264， HP PA 8500，IBM RS64 VLIW/LIW 靜態(tài)靜態(tài) 軟件軟件 靜態(tài)靜態(tài)流出包之間流出包之間沒有沖突沒有沖突 Trimedia，i860 EPIC 主要是主要是靜態(tài)靜態(tài) 主要是主要是軟件軟件 主要是主要是靜態(tài)靜態(tài)相關性被編譯相關性被編譯器顯式地標記器顯式地標記出來出來 Itanium 8686/135/1354.4 多指令流出技術在典型的超標量處理器中，每個時鐘周期可流出1到8條指令。指令按序流出，在流出時進行沖突檢測。 在當前流出的指令序

29、列中，不存在數(shù)據(jù)沖突或者相在當前流出的指令序列中，不存在數(shù)據(jù)沖突或者相關沖突。關沖突。舉例：一個4流出的靜態(tài)調度超標量處理機 在取指令階段，流水線將從取指令部件收到14條指令（稱為流出包）。q在一個時鐘周期內，這些指令有可能是全部都能流出，在一個時鐘周期內，這些指令有可能是全部都能流出，也可能是只有一部分能流出。也可能是只有一部分能流出。4.4.1 基于靜態(tài)調度的多流出技術8787/135/1354.4 多指令流出技術流出部件檢測結構沖突或者數(shù)據(jù)沖突。一般分兩階段實現(xiàn)：一般分兩階段實現(xiàn)：q第一階段：第一階段：進行流出包內的沖突檢測，選出初步判定進行流出包內的沖突檢測，選出初步判定可以流出的指令

30、。可以流出的指令。q第二階段：第二階段：檢測所選出的指令與正在執(zhí)行的指令是否檢測所選出的指令與正在執(zhí)行的指令是否有沖突。有沖突。 MIPS處理機是怎樣實現(xiàn)超標量的呢？假設：每個時鐘周期流出兩條指令： 1 1條整數(shù)型指令條整數(shù)型指令1 1條浮點操作指令條浮點操作指令q其中，把其中，把loadload指令、指令、storestore指令、分支指令歸類為整指令、分支指令歸類為整數(shù)型指令。數(shù)型指令。 8888/135/1354.4 多指令流出技術1. 要求：同時取兩條指令（64位），譯碼兩條指令（64位）。2. 對指令的處理包括以下步驟：從Cache中取兩條指令。確定哪幾條指令可以流出（02條指令）。

31、把它們發(fā)送到相應的功能部件。3. 雙流出超標量流水線中指令的執(zhí)行過程 假設：所有的浮點指令都是加法指令，其執(zhí)行時間為兩個時鐘周期。為簡單起見，下圖中總是把整數(shù)指令放在浮點指令的前面。 8989/135/1354.4 多指令流出技術指令類型指令類型 流水線工作情況流水線工作情況 整數(shù)指令整數(shù)指令 IF ID EX MEM WB 浮點指令浮點指令 IF ID EX EXMEMWB 整數(shù)指令整數(shù)指令 IF ID EX MEM WB 浮點指令浮點指令 IF ID EX EXMEMWB 整數(shù)指令整數(shù)指令 IF ID EX MEM WB 浮點指令浮點指令 IF ID EX EXMEMWB 整數(shù)指令整數(shù)指令

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

33、遲 q如果分支指令是流出包中的第一條指令，則其延遲是如果分支指令是流出包中的第一條指令，則其延遲是3 3條條指令指令；q否則就是流出包中的第二條指令，其延遲就是否則就是流出包中的第二條指令，其延遲就是兩條指令。兩條指令。9292/135/1354.4 多指令流出技術擴展Tomasulo算法：支持兩路超標量q每個時鐘周期流出兩條指令；每個時鐘周期流出兩條指令；q一條是整數(shù)指令，另一條是浮點指令。一條是整數(shù)指令，另一條是浮點指令。1. 采用一種比較簡單的方法指令按順序流向保留站，否則會破壞程序語義。 將整數(shù)所用的表結構與浮點用的表結構分離開，分別進行處理，這樣就可以同時地流出一條浮點指令和一條整數(shù)

34、指令到各自的保留站。 4.4.2 基于動態(tài)調度的多流出技術9393/135/1354.4 多指令流出技術2. 有兩種不同的方法可以實現(xiàn)多流出。 關鍵在于：關鍵在于：對保留站的分配和對流水線控制表格的修改。對保留站的分配和對流水線控制表格的修改。在半個時鐘周期里完成流出步驟，這樣一個時鐘周期就能處理兩條指令。設置一次能同時處理兩條指令的邏輯電路。 現(xiàn)代的流出現(xiàn)代的流出4 4條或條或4 4條以上指令的超標量處理機條以上指令的超標量處理機經常是兩種方法都采用。經常是兩種方法都采用。 9494/135/1354.4 多指令流出技術 例例4.44.4 對于采用了對于采用了TomasuloTomasulo

35、算法和多流出技術的算法和多流出技術的MIPSMIPS流水線，流水線，考慮以下簡單循環(huán)的執(zhí)行。該程序把考慮以下簡單循環(huán)的執(zhí)行。該程序把F2F2中的標量加到一個向量的中的標量加到一個向量的每個元素上。每個元素上。 Loop: L.D Loop: L.D F0, 0F0, 0（R1R1） / / 取一個數(shù)組元素放入取一個數(shù)組元素放入F0F0 ADD.D ADD.D F4, F0, F2 F4, F0, F2 / / 加上在加上在F2F2中的標量中的標量 S.D S.D F4, 0F4, 0（R1R1） / / 存結果存結果 DADDIU R1,R1DADDIU R1,R1，#-8#-8 / / 將指

36、針減少將指針減少8 8（每個數(shù)據(jù)占（每個數(shù)據(jù)占8 8個字節(jié)）個字節(jié)） BNE R1,R2,LoopBNE R1,R2,Loop / / 若若R1R1不等于不等于R2R2，表示尚未結束，轉移到，表示尚未結束，轉移到LoopLoop繼續(xù)繼續(xù) 9595/135/1354.4 多指令流出技術現(xiàn)做以下假設：q每個時鐘周期能流出一條整數(shù)指令和一條浮點指令，每個時鐘周期能流出一條整數(shù)指令和一條浮點指令，即使它們相關也是如此。即使它們相關也是如此。q有一個整數(shù)部件，用于整數(shù)有一個整數(shù)部件，用于整數(shù)ALUALU運算和地址計算；并運算和地址計算；并且對于每一種浮點操作類型都有一個獨立的流水化了且對于每一種浮點操作

37、類型都有一個獨立的流水化了的浮點功能部件。的浮點功能部件。q指令流出和寫結果各占用一個時鐘周期。指令流出和寫結果各占用一個時鐘周期。q具有動態(tài)分支預測部件和一個獨立的計算分支條件的具有動態(tài)分支預測部件和一個獨立的計算分支條件的功能部件。功能部件。q分支指令單獨流出，沒有采用延遲分支，但分支預測分支指令單獨流出，沒有采用延遲分支，但分支預測是完美的。分支指令完成前，其后續(xù)指令只能被取出是完美的。分支指令完成前，其后續(xù)指令只能被取出和流出，但不能執(zhí)行。和流出，但不能執(zhí)行。9696/135/1354.4 多指令流出技術q因為寫結果占用一個時鐘周期，所以產生結果的延遲因為寫結果占用一個時鐘周期，所以產

38、生結果的延遲為：整數(shù)運算一個周期，為：整數(shù)運算一個周期，loadload兩個周期，浮點加法運兩個周期，浮點加法運算算3 3個周期。個周期。 列出該程序前面列出該程序前面3 3遍循環(huán)中各條指令的流出、開始執(zhí)行和將結果遍循環(huán)中各條指令的流出、開始執(zhí)行和將結果寫到寫到CDBCDB上的時間。上的時間。 解解 執(zhí)行時，該循環(huán)將動態(tài)展開，并且只要可能就流出兩條指令。執(zhí)行時，該循環(huán)將動態(tài)展開，并且只要可能就流出兩條指令。 為了便于分析，表中列出了訪存發(fā)生的時刻。運行結果如下圖為了便于分析，表中列出了訪存發(fā)生的時刻。運行結果如下圖所示。所示。 遍數(shù)遍數(shù) 指指 令令 流出流出 執(zhí)行執(zhí)行 訪存訪存 寫寫CDB C

39、DB 說明說明 1 1L.D F0,0L.D F0,0（R1R1） 1 12 23 34 4流出第一條指令流出第一條指令 1 1ADD.D F4,F0,F2 ADD.D F4,F0,F2 1 15 58 8等待等待L.DL.D的結果的結果 1 1S.D F4,0S.D F4,0（R1R1） 2 23 39 9等待等待ADD.DADD.D的結果的結果 1 1DADDIU R1,R1,#-8 DADDIU R1,R1,#-8 2 24 45 5等待等待ALUALU1 1BNE R1,R2,Loop BNE R1,R2,Loop 3 36 6等待等待DADDIUDADDIU的結果的結果 2 2L.D

40、 F0,0L.D F0,0（R1R1） 4 47 78 89 9等待等待BNEBNE完成完成 2 2ADD.D F4,F0,F2 ADD.D F4,F0,F2 4 410101313等待等待L.DL.D的結果的結果 2 2S.D F4,0S.D F4,0（R1R1） 5 58 81414等待等待ADD.DADD.D的結果的結果 2 2DADDIU R1,R1,#-8 DADDIU R1,R1,#-8 5 59 91010等待等待ALU ALU 2 2BNE R1,R2,LoopBNE R1,R2,Loop6 61111等待等待DADDIUDADDIU的結果的結果 3 3L.D F0,0L.D

41、F0,0（R1R1） 7 7121213131414等待等待BNEBNE完成完成 3 3ADD.D F4,F0,F2 ADD.D F4,F0,F2 7 715151818等待等待L.DL.D的結果的結果 3 3S.D F4,0S.D F4,0（R1R1） 8 813131919等待等待ADD.DADD.D的結果的結果 3 3DADDIU R1,R1,#-8 DADDIU R1,R1,#-8 8 814141515等待等待ALU ALU 3 3BNE R1,R2,LoopBNE R1,R2,Loop9 91616等待等待DADDIUDADDIU的結果的結果 9898/135/1354.4 多指令

42、流出技術從圖中可以看出：程序基本可以達到3拍流出5條指令 IPCIPC5/35/31.67 1.67 條條/ /拍拍雖然指令的流出率比較高，但是執(zhí)行效率并不是很高。q1616拍共執(zhí)行拍共執(zhí)行1515條指令，條指令，q平均指令執(zhí)行速度為平均指令執(zhí)行速度為15/1615/160.94 0.94 條條/ /拍。拍。原因是浮點運算少，ALU部件成了瓶頸。 解決方法：增加一個加法器，把ALU功能和地址運算功能分開。 9999/135/1354.4 多指令流出技術3. 上述雙流出動態(tài)調度流水線的性能受限于以下3個因素：整數(shù)部件和浮點部件的工作負載不平衡，沒有充分發(fā)揮出浮點部件的作用。 應該設法減少循環(huán)中整

43、數(shù)型指令的數(shù)量。應該設法減少循環(huán)中整數(shù)型指令的數(shù)量。每個循環(huán)迭代中的控制開銷太大。q5 5條指令中有兩條指令是輔助指令。條指令中有兩條指令是輔助指令。q應該設法減少或消除這些指令。應該設法減少或消除這些指令?？刂葡嚓P使得處理機必須等到分支指令的結果出來后才能開始下一條L.D指令的執(zhí)行。 100100/135/1354.4 多指令流出技術1. 把能并行執(zhí)行的多條指令組裝成一條很長的指令。（100100多位到幾百位）多位到幾百位）2. 設置多個功能部件。3. 指令字被分割成一些字段，每個字段稱為一個操作槽，直接獨立地控制一個功能部件。4. 在VLIW處理機中，所有的處理和指令安排都是由編譯器完成的

44、。 4.4.3 超長指令字技術（VLIW）101101/135/135 例例4.54.5 假設假設VLIWVLIW處理機每個時鐘周期可同時流出處理機每個時鐘周期可同時流出5 5條條指令：指令：兩兩條條訪存指令、訪存指令、兩條兩條浮點操作指令和浮點操作指令和一條一條整數(shù)指令或分支指令。對于整數(shù)指令或分支指令。對于例例4.44.4中的循環(huán)展開后的代碼，給出它在該中的循環(huán)展開后的代碼，給出它在該VLIWVLIW中的代碼序列。不考中的代碼序列。不考慮分支指令的延遲槽。慮分支指令的延遲槽。 解解 代碼序列如下圖所示。代碼序列如下圖所示。運行時間為運行時間為8 8個個時鐘周期。時鐘周期。每遍循環(huán)平均每遍循

45、環(huán)平均1.61.6個個時鐘周期。時鐘周期。8 8個個時鐘周期內流出了時鐘周期內流出了1717條指令，每個時鐘周期條指令，每個時鐘周期2.12.1條。條。8 8個個時鐘周期共有操作槽時鐘周期共有操作槽8 8 5=405=40個，有效槽的比例為個，有效槽的比例為42.5%42.5%。 4.4 多指令流出技術102102/135/1354.4 多指令流出技術訪存指令訪存指令1 1 訪存指令訪存指令2 2 浮點指令浮點指令1 1 浮點指令浮點指令2 2 整數(shù)整數(shù)/ /轉移指令轉移指令 L.D F0,0(R1)L.D F0,0(R1)L.D F6,-8(R1)L.D F6,-8(R1)L.D F10,-

46、16(R1)L.D F10,-16(R1)L.D F14,-24(R1)L.D F14,-24(R1)L.D F18,-32(R1)L.D F18,-32(R1)ADD.D F4,F0,F2ADD.D F4,F0,F2ADD.DF8,F6,F2ADD.DF8,F6,F2ADD.DF12,F10,F2ADD.DF12,F10,F2ADD.DF16,F14,F2ADD.DF16,F14,F2ADD.DF20,F18,F2ADD.DF20,F18,F2S.D F4,0(R1)S.D F4,0(R1)S.D F8,-8(R1)S.D F8,-8(R1)S.D F12,-16(R1)S.D F12,-1

47、6(R1)S.D F16,24(R1)S.D F16,24(R1)DADDIUR1,R1,#-40DADDIUR1,R1,#-40S.D F20,8(R1)S.D F20,8(R1)BNE R1,R2,LoopBNE R1,R2,Loop103103/135/1354.4 多指令流出技術5. VLIW存在的一些問題 程序代碼長度增加了q提高并行性而進行的大量的循環(huán)展開。提高并行性而進行的大量的循環(huán)展開。q指令字中的操作槽并非總能填滿。指令字中的操作槽并非總能填滿。 解決：解決：采用指令共享立即數(shù)字段的方法，或者采用指采用指令共享立即數(shù)字段的方法，或者采用指 令壓縮存儲、調入令壓縮存儲、調入Ca

48、cheCache或譯碼時展開的方法?；蜃g碼時展開的方法。采用了鎖步機制 任何一個操作部件出現(xiàn)停頓時，整個處理機都要停頓。任何一個操作部件出現(xiàn)停頓時，整個處理機都要停頓。機器代碼的不兼容性104104/135/1354.4 多指令流出技術指令多流出處理器受哪些因素的限制呢？ 主要受以下三個方面的影響：q程序所固有的指令級并行性。程序所固有的指令級并行性。q硬件實現(xiàn)上的困難。硬件實現(xiàn)上的困難。q超標量和超長指令字處理器固有的技術限制。超標量和超長指令字處理器固有的技術限制。4.4.4 多流出處理器受到的限制105105/135/1354.4 多指令流出技術1. 將每個流水段進一步細分，這樣在一個時

49、鐘周期內能夠分時流出多條指令。這種處理機稱為超流水線處理機。2. 對于一臺每個時鐘周期能流出n條指令的超流水線計算機來說，這n條指令不是同時流出的，而是每隔1/n個時鐘周期流出一條指令。實際上該超流水線計算機的流水線周期為1/n個時鐘周期。 3. 一臺每個時鐘周期分時流出兩條指令的超流水線計算機的時空圖。 4.4.5 超流水線處理機106106/135/1354.4 多指令流出技術 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 E

50、X MEM WBID EX MEM WBIF ID EX MEM WBID EX MEM WB107107/135/1354.4 多指令流出技術4. 在有的資料上，把指令流水線級數(shù)為8或8以上的流水線處理機稱為超流水線處理機。5. 典型的超流水線處理器：SGI公司的MIPS系列R4000R4000微處理器芯片內有2個Cache：q指令指令CacheCache和數(shù)據(jù)和數(shù)據(jù)CacheCacheq容量都是容量都是8 KB8 KBq每個每個CacheCache的數(shù)據(jù)寬度為的數(shù)據(jù)寬度為64 64 b b R4000的核心處理部件：整數(shù)部件 q一個一個32323232位的通用寄存器組位的通用寄存器組q一個

51、算術邏輯部件一個算術邏輯部件（ALUALU）q一個專用的乘法一個專用的乘法/ /除法部件除法部件 108108/135/1354.4 多指令流出技術浮點部件q一個執(zhí)行部件一個執(zhí)行部件n浮點乘法部件浮點乘法部件n浮點除法部件浮點除法部件n浮點加法浮點加法/轉換轉換/求平方根部件求平方根部件 （它們可以并行工作）（它們可以并行工作）q一個一個16166464位的浮點通用寄存器組。浮點通用寄存器位的浮點通用寄存器組。浮點通用寄存器組也可以設置成組也可以設置成3232個個3232位的浮點寄存器。位的浮點寄存器。R4000的指令流水線有8級109109/135/1354.4 多指令流出技術110110/

52、135/1354.4 多指令流出技術各級的功能qIFIF：取指令的前半步，根據(jù)取指令的前半步，根據(jù)PCPC值去啟動對指令值去啟動對指令CacheCache的訪問。的訪問。qISIS：取指令的后半步，在這一級完成對指令取指令的后半步，在這一級完成對指令CacheCache的訪問。的訪問。qRFRF：指令譯碼，訪問寄存器組讀取操作數(shù)，沖突檢測，并判指令譯碼，訪問寄存器組讀取操作數(shù)，沖突檢測，并判斷指令斷指令CacheCache是否命中。是否命中。qEXEX：指令執(zhí)行。包括有效地址計算，：指令執(zhí)行。包括有效地址計算，ALUALU操作，分支目標地操作，分支目標地址計算，條件碼測試。址計算，條件碼測試。

53、qDFDF：取數(shù)據(jù)的前半步，啟動對數(shù)據(jù)取數(shù)據(jù)的前半步，啟動對數(shù)據(jù)CacheCache的訪問。的訪問。qDSDS：取數(shù)據(jù)的后半步，在這一級完成對數(shù)據(jù)取數(shù)據(jù)的后半步，在這一級完成對數(shù)據(jù)CacheCache的訪問。的訪問。qTCTC：標識比較，判斷對數(shù)據(jù)標識比較，判斷對數(shù)據(jù)CacheCache的訪問是否命中。的訪問是否命中。qWBWB：loadload指令或運算型指令把結果寫回寄存器組。指令或運算型指令把結果寫回寄存器組。 111111/135/1354.4 多指令流出技術MIPS R4000指令流水線時空圖 WB WB 時鐘周期時鐘周期 IF IS RF EX DF DS TC IF IS RF

54、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 載入延遲為兩個時鐘周期 Reg ALU Reg 指令指令 Cache 數(shù)據(jù)數(shù)據(jù)Cache 時鐘周期時鐘周期 1 2 3 4 5 6 7 8 9 10 11 LD R1 指令指令 1 指令指令 2 Reg ALU Reg 指令指令 Ca

55、che 數(shù)據(jù)數(shù)據(jù)Cache Reg ALU Reg 指令指令 Cache 數(shù)據(jù)數(shù)據(jù)Cache Reg ALU Reg 指令指令 Cache 數(shù)據(jù)數(shù)據(jù)Cache DADD R2 , R1, 113113/135/1351. 充分開發(fā)指令之間存在的并行性，找出不相關的指令序列，讓它們在流水線上重疊并行執(zhí)行。 2. 增加指令間并行性最簡單和最常用的方法開發(fā)循環(huán)級并行性循環(huán)的不同迭代之間存在的并行性。在把循環(huán)展開后，通過重命名和指令調度來開發(fā)更多的并行性。 4.5 循環(huán)展開和指令調度4.5.1 循環(huán)展開和指令調度的基本方法114114/135/1354.5 循環(huán)展開和指令調度3. 編譯器完成這種指令調

56、度的能力受限于兩個特性：程序固有的指令級并行性；流水線功能部件的執(zhí)行延遲。4. 本節(jié)中，我們使用的浮點流水線延遲為： 產生結果的指令 使用結果的指令 延遲（時鐘周期數(shù)） 浮點計算 另一個浮點計算 3 浮點計算 浮點store（S.D） 2 浮點load（L.D） 浮點計算 1 浮點load（L.D） 浮點store（S.D） 0 115115/135/1354.5 循環(huán)展開和指令調度假設采用第3章的5段整數(shù)流水線：分支的延遲：1個時鐘周期。整數(shù)load指令的延遲：1個時鐘周期。整數(shù)運算部件是全流水或者重復設置了足夠的份數(shù)。 116116/135/1354.5 循環(huán)展開和指令調度 例例4.64.

57、6 對于下面的源代碼，轉換成對于下面的源代碼，轉換成MIPSMIPS匯編語言，匯編語言，在在不進行指令調度不進行指令調度和和進行指令調度進行指令調度兩種情況下，分析其兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時間。代碼一次循環(huán)所需的執(zhí)行時間。 for (i=1for (i=1； i=1000i=1000； i+)i+) xi = xi + s xi = xi + s；解解 把該程序翻譯成把該程序翻譯成MIPSMIPS匯編語言代碼：匯編語言代碼：假設假設R1R1的初值是指向第一個元素，的初值是指向第一個元素，8 8（R2R2）指向最后一個元素。指向最后一個元素。117117/135/1354.5

58、循環(huán)展開和指令調度LoopLoop：L.DL.D F0F0,0,0（R1R1） ADD.DADD.D F4F4, ,F0F0,F2,F2 S.D S.D F4F4, 0, 0（R1R1） DADDIU DADDIU R1R1,R1,R1，#-8#-8 BNE BNE R1R1,R2,Loop,R2,Loop其中：p整數(shù)寄存器整數(shù)寄存器R1R1：指向向量中的當前元素。指向向量中的當前元素。 （初值為向量中最高端元素的地址）（初值為向量中最高端元素的地址）p浮點寄存器浮點寄存器F2F2：用于保存常數(shù)用于保存常數(shù)s s。 118118/135/1354.5 循環(huán)展開和指令調度不進行指令調度的情況下，

59、程序的實際執(zhí)行情況： 指令流出時鐘指令流出時鐘 Loop: L.DLoop: L.D F0F0,0,0（R1R1） 1 1 （空轉）（空轉） 2 2 ADD.D ADD.D F4F4, ,F0F0,F2 ,F2 3 3 （空轉）空轉） 4 4 （空轉）（空轉） 5 5 S.D S.D F4F4, 0, 0（R1R1） 6 6 DADDIU DADDIU R1R1,R1,R1，# -8 # -8 7 7 （空轉）（空轉） 8 8 BNE BNE R1R1,R2,Loop ,R2,Loop 9 9 （空轉）（空轉） 1010 每個元素的操作需要每個元素的操作需要1010個個時鐘周期，其中時鐘周期，

60、其中5 5個個是空轉周期。是空轉周期。119119/135/1354.5 循環(huán)展開和指令調度指令調度以后，程序的執(zhí)行情況如下：q把把DADDIUDADDIU指令調度到了指令調度到了L.DL.D指令和指令和ADD.DADD.D指令之間的指令之間的“空轉空轉”拍。拍。q把把S.DS.D指令放到了分支指令的延遲槽中。指令放到了分支指令的延遲槽中。q對存儲器地址偏移量進行調整。對存儲器地址偏移量進行調整。 120120/135/1354.5 循環(huán)展開和指令調度 Loop: L.DLoop: L.D F0F0,0,0（R1R1） （空轉）（空轉） ADD.DADD.D F4F4, ,F0F0,F2 ,F