計算機體系結構第6章

1、1 1/89/89第6章 指令級并行的開發(fā)軟件方法www.GotoS2 2/89/896.1 基本指令調度及循環(huán)展開6.2 跨越基本塊的靜態(tài)指令調度6.3 靜態(tài)多指令流出：VLIW技術6.4 顯式并行指令計算EPIC6.5 開發(fā)更多的指令級并行6.6 實例：IA-64體系結構3 3/89/891. 指令調度：找出不相關的指令序列，讓它們在流水線上重疊并行執(zhí)行。2. 制約編譯器指令調度的因素程序固有的指令級并行流水線功能部件的延遲6.1 基本指令調度及循環(huán)展開6.1.1 指令調度的基本方法4 4/89/89 表表6.16.1本節(jié)使用的浮點流水線的延遲本節(jié)使用的浮點流水線的延遲6.1 基本指令調度

2、及循環(huán)展開產生結果的指令產生結果的指令使用結果的指令使用結果的指令延遲延遲(cycles)浮點計算浮點計算另一個浮點計算另一個浮點計算3浮點計算浮點計算浮點浮點store(S.D)2浮點浮點Load(L.D)浮點計算浮點計算1浮點浮點Load(L.D)浮點浮點store(S.D)05 5/89/89 例例6.1 6.1 對于下面的源代碼，轉換成對于下面的源代碼，轉換成MIPSMIPS匯編語言，在不進行指令調匯編語言，在不進行指令調度和進行指令調度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時間。度和進行指令調度兩種情況下，分析其代碼一次循環(huán)所需的執(zhí)行時間。 for (i=1000; i0; i-)

3、for (i=1000; i0; i-) xi = xi + s; xi = xi + s; 解：解：先把該程序翻譯成先把該程序翻譯成MIPS匯編語言代碼匯編語言代碼 Loop：L.D F0, 0(R1) ADD.D F4, F0, F2 S.D F4, 0(R1) DADDIU R1, R1, #-8 BNE R1, R2, Loop6 6/89/896.1 基本指令調度及循環(huán)展開在不進行指令調度的情況下，根據表中給出的浮點流水線在不進行指令調度的情況下，根據表中給出的浮點流水線中指令執(zhí)行的延遲，程序的實際執(zhí)行情況如下：中指令執(zhí)行的延遲，程序的實際執(zhí)行情況如下：指令流出時鐘指令流出時鐘Loo

4、p：L.D F0, 0(R1)1(空轉空轉)2ADD.D F4, F0, F23(空轉空轉)4(空轉空轉)5S.D F4, 0(R1)6DADDIU R1, R1, #-87(空轉空轉)8BNE R1, R2, Loop9(空轉空轉)107 7/89/896.1 基本指令調度及循環(huán)展開在用編譯器對上述程序進行指令調度以后，程序的執(zhí)行情在用編譯器對上述程序進行指令調度以后，程序的執(zhí)行情況如下：況如下：指令流出時鐘指令流出時鐘Loop：L.D F0, 0(R1)1DADDIU R1, R1, #-8 2ADD.D F4, F0, F23(空轉空轉)4BNE R1, R2, Loop 5S.D F4

5、, 8(R1)68 8/89/896.1 基本指令調度及循環(huán)展開進一步分析：編譯時指令調度是怎樣減少整個指令序列在流水線上的執(zhí)行時間的？指令調度能否跨越分支邊界？怎樣提高整個執(zhí)行過程中有效操作的比率？9 9/89/891. 循環(huán)展開把循環(huán)體的代碼復制多次并按順序排放， 然后相應調整循環(huán)的結束條件。開發(fā)循環(huán)級并行的有效方法 例例6.2 將例將例6.1中的循環(huán)展開中的循環(huán)展開3次得到次得到4個循環(huán)體，然后對展開個循環(huán)體，然后對展開后的指令序列在不調度和調度兩種情況下，分析代碼的性能。后的指令序列在不調度和調度兩種情況下，分析代碼的性能。假定假定R1的初值為的初值為32的倍數，即循環(huán)次數為的倍數，即

6、循環(huán)次數為4的倍數。消除冗余的的倍數。消除冗余的指令，并且不要重復使用寄存器。指令，并且不要重復使用寄存器。 6.1.2 循環(huán)展開6.1 基本指令調度及循環(huán)展開展開后沒有調度的代碼如下展開后沒有調度的代碼如下(需要分配寄存器需要分配寄存器) 指令流出時鐘指令流出時鐘Loop:L.DF0, 0(R1)1（空轉）（空轉）2ADD.DF4, F0, F23（空轉）（空轉）4（空轉）（空轉）5S.DF4, 0(R1)6L.DF6, -8(R1)7（空轉）（空轉）8ADD.DF8, F6, F29（空轉）（空轉）10（空轉）（空轉）11S.DF8, -8(R1)12L.DF10, -16(R1)13（空

7、轉）（空轉）14 指令流出時鐘指令流出時鐘ADD.DF12, F10, F215（空轉）（空轉）16（空轉）（空轉）17S.DF12, -16（R1）18L.DF14, -24（R1）19（空轉）（空轉）20ADD.DF16, F14, F221（空轉）（空轉）22（空轉）（空轉）23S.DF16, -24（R1）24DADDIUR1, R1, # -3225（空轉）（空轉）26BNER1, R2, Loop27（空轉）（空轉）2850%是空轉周期！是空轉周期！調度后的代碼如下：調度后的代碼如下： 指令流出時鐘指令流出時鐘Loop:L.DF0, 0（R1）1L.DF6, -8（R1）2L.DF

8、10, -16（R1）3L.DF14, -24（R1）4ADD.DF4, F0, F25ADD.DF8, F6, F26ADD.DF12, F10, F27ADD.DF16, F14, F28S.DF4, 0（R1）9S.DF8, -8（R1）10DADDIUR1, R1, # -3212S.DF12, 16（R1）11BNER1, R2, Loop13S.DF16, 8（R1）14沒有空轉周期！沒有空轉周期！結論：結論：通過循環(huán)展通過循環(huán)展開、寄存器重命名開、寄存器重命名和指令調度，可以和指令調度，可以有效開發(fā)出指令級有效開發(fā)出指令級并行。并行。1212/89/896.1 基本指令調度及循環(huán)

9、展開 循環(huán)展開和指令調度的注意事項 保證正確性注意有效性使用不同的寄存器刪除多余的測試指令和分支指令，并對循環(huán)結束代碼和新的循環(huán)體代碼進行相應的修正。注意對存儲器數據的相關性分析注意新的相關性1313/89/891. 概述目標：在保持原有數據相關和控制相關不變的前提下，盡可能地縮短包含分支結構的代碼段的總執(zhí)行時間。q單流出處理器單流出處理器減少指令數減少指令數q多流出處理器多流出處理器縮短關鍵路徑長度縮短關鍵路徑長度基本思想：在循環(huán)體內的多個基本塊間移動指令，擴大那些執(zhí)行頻率較高的基本塊的體積。6.2 跨越基本塊的靜態(tài)指令調度6.2.1 全局指令調度1414/89/896.2 跨越基本塊的靜態(tài)

10、指令調度 實例分析由于分支條件為true(轉移)的概率大，全局指令調度時會將語句1、2、3、5合并為一個更大的基本塊。一個分支結構的代碼段一個分支結構的代碼段q如何保證分支條件如何保證分支條件為為false時結果依然時結果依然正確？正確？q 如何將語句如何將語句3和和5調調度到語句度到語句2之前？之前？ 1515/89/896.2 跨越基本塊的靜態(tài)指令調度將上圖中的代碼轉換為下面的MIPS匯編指令LDR4，0(R1)/ 取取ALDR5，0(R2)/ 取取BDADDU R4，R4，R5/ A=A+BSD0(R1)，R4/ 存存ABNEZR4，elsepart/ A=0則轉移則轉移X/ 代碼段代碼

11、段X，基本塊，基本塊elsepartJjointhenpart：/ 基本塊基本塊thenpartSD，0(R2)/ 指令指令I1，對應語句，對應語句3join：SD，0(R3)/ 指令指令I2，對應語句，對應語句51616/89/896.2 跨越基本塊的靜態(tài)指令調度調度指令I1q直接將直接將I1移到移到BEQZ前是否會產生錯誤結果？前是否會產生錯誤結果？q向基本塊向基本塊elsepart中增加中增加補償代碼補償代碼q補償代碼有可能帶來額外時間開銷補償代碼有可能帶來額外時間開銷調度指令I2q將將I2移動到基本塊移動到基本塊thenpart中，同時復制到中，同時復制到elsepart中。中。q若不

12、影響執(zhí)行結果，將若不影響執(zhí)行結果，將I2調度到調度到BEQZ前，同前，同時刪除時刪除elsepart中的副本。中的副本。1717/89/896.2 跨越基本塊的靜態(tài)指令調度 全局指令調度是一個很復雜的問題 以I1的調度為例：需要確定分支中基本塊thenpart和elsepart的執(zhí)行頻率各是多少？在分支語句前完成I1所需的開銷是多大？調度I1是否能夠縮短thenpart塊的執(zhí)行時間？I1是否是最佳的被調度對象？是否需要向elsepart塊中增加補償代碼，補償代碼開銷如何？怎樣生成補償代碼？1818/89/891. 概述蹤跡（trace）：程序執(zhí)行的指令序列，通常由一個或多個基本塊組成，trac

13、e內可以有分支，但一定不能包含循環(huán)。 蹤跡調度（trace scheduling）會優(yōu)化執(zhí)行頻率高的trace，減少其執(zhí)行開銷。由于需要添加補償代碼以確保正確性，那些執(zhí)行頻率較低的trace的開銷反而會有所增加。蹤跡調度非常適合多流出處理器。 6.2.2 蹤跡調度6.2 跨越基本塊的靜態(tài)指令調度1919/89/89 蹤跡調度的步驟分為兩步：蹤跡選擇和蹤跡壓縮蹤跡選擇q從程序的控制流圖中選擇執(zhí)行頻率較高的路徑，從程序的控制流圖中選擇執(zhí)行頻率較高的路徑，每條路徑就是一條每條路徑就是一條trace。q處理轉移成功與失敗概率相差較大的情況處理轉移成功與失敗概率相差較大的情況q循環(huán)結構：循環(huán)展開循環(huán)結構

14、：循環(huán)展開q分支結構：根據典型輸入集下的運行統(tǒng)計信息分支結構：根據典型輸入集下的運行統(tǒng)計信息6.2 跨越基本塊的靜態(tài)指令調度2020/89/89蹤跡選擇實例分析6.2 跨越基本塊的靜態(tài)指令調度 將左邊的循環(huán)展開將左邊的循環(huán)展開4次次并把陰影部分并把陰影部分(執(zhí)行頻率高執(zhí)行頻率高)拼接在一起就可以得到一拼接在一起就可以得到一條條trace； 一條一條trace可以有多個可以有多個入口和多個出口。入口和多個出口。2121/89/89蹤跡壓縮q對已生成的對已生成的trace進行指令調度和優(yōu)化，盡可能地縮短其進行指令調度和優(yōu)化，盡可能地縮短其執(zhí)行時間；執(zhí)行時間；q跨越跨越trace內部的入口或出口調度

15、指令時必須非常小心，內部的入口或出口調度指令時必須非常小心，有時還需要增加補償代碼有時還需要增加補償代碼 。6.2 跨越基本塊的靜態(tài)指令調度三條三條trace：B1-B3、B4以及以及B5-B7指令指令“y = x - y”被從被從B1調度到調度到B3中，跨越了中，跨越了trace的一個出口；的一個出口；需要向塊需要向塊B2中增加補償代碼，即中增加補償代碼，即將指令將指令“y = x - y”復制到復制到B2的第的第一條指令之前一條指令之前 。2222/89/89 蹤跡調度的性能特點蹤跡調度能夠提升性能的最根本原因在于選出的trace都是執(zhí)行頻率很高的路徑，減少它們的執(zhí)行開銷有助于縮短程序的總

16、執(zhí)行時間。對于某些應用，補償代碼引起的開銷很有可能降低蹤跡調度的優(yōu)化效果。蹤跡調度會大大增加編譯器的實現復雜度。6.2 跨越基本塊的靜態(tài)指令調度2323/89/891. 概述在蹤跡調度中，如果trace入口或出口位于trace內部，編譯器生成補償代碼的難度將大大增加，而且編譯器很難評估這些補償代碼究竟會帶來多少性能損失。超塊（superblock）是只能擁有一個入口，但可以擁有多個出口的結構超塊的構造過程與trace相似，但怎樣確保只有一個入口？6.2.3 超塊調度6.2 跨越基本塊的靜態(tài)指令調度2424/89/89 超塊構造尾復制技術6.2 跨越基本塊的靜態(tài)指令調度 將左邊的循環(huán)展開將左邊的

17、循環(huán)展開4次次并把陰影部分并把陰影部分(執(zhí)行頻率高執(zhí)行頻率高)拼接在一起就可以得到一拼接在一起就可以得到一個超塊；個超塊； 超塊有超塊有1個入口和個入口和5個個出口出口(n=4/3/2/1/0)。 除了除了n=0外，從其他外，從其他4個出口退出超塊后，還需個出口退出超塊后，還需要繼續(xù)完成余下的要繼續(xù)完成余下的n次疊代次疊代(黃色部分黃色部分)。 2525/89/89 超塊調度的性能特點尾復制技術簡化了補償代碼的生成過程，并降低了指令調度的復雜度。超塊結構目標代碼的體積也大大增加。補償代碼的生成使得編譯過程更加復雜，而且由于無法準確評估由補償代碼引起的時間開銷，這限制方法超塊調度的應用范圍。6.

18、2 跨越基本塊的靜態(tài)指令調度2626/89/891. VLIW vs. 超標量在動態(tài)調度的超標量處理器中，相關檢測和指令調度基本都由硬件完成。在靜態(tài)調度的超標量處理器中，部分相關檢測和指令調度工作交由編譯器完成。在VLIW處理器中，相關檢測和指令調度工作全部由編譯器完成，它需要更“智能”的編譯器。6.3 靜態(tài)多指令流出：VLIW技術 slotslotslotslot32bit32bit32bit32bit128bit VLIW指令指令2727/89/89 實例分析 6.3 靜態(tài)多指令流出VLIW技術 例例6.3 假設某假設某VLIW處理器每個時鐘周期可以同時流出處理器每個時鐘周期可以同時流出5

19、個操個操作，包括作，包括2個訪存操作，個訪存操作，2個浮點操作以及個浮點操作以及1個整數或分支操作。個整數或分支操作。將將例例6.1中的代碼循環(huán)展開，并調度到該中的代碼循環(huán)展開，并調度到該VLIW處理器上執(zhí)行。循處理器上執(zhí)行。循環(huán)展開次數不定，但至少要能夠保證消除所有流水線環(huán)展開次數不定，但至少要能夠保證消除所有流水線“空轉空轉”周周期，同時不考慮分支延遲。期，同時不考慮分支延遲。解：解：循環(huán)被展開循環(huán)被展開7次，經調度后可以消除所有流水線次，經調度后可以消除所有流水線“空轉空轉”。在。在不考慮分支延遲的情況下，每執(zhí)行一個疊代需要不考慮分支延遲的情況下，每執(zhí)行一個疊代需要9個時鐘周期，個時鐘周

20、期，計算出計算出7個結果，即平均每得到一個結果需要個結果，即平均每得到一個結果需要1.29個個周期。周期。 VLIW的不足：q編碼效率僅比編碼效率僅比50%略高一些略高一些q所需要的寄存器數量也大大增加所需要的寄存器數量也大大增加 2828/89/896.3 靜態(tài)多指令流出VLIW技術訪存操作訪存操作1訪存操作訪存操作2浮點操作浮點操作1浮點操作浮點操作2整數分支操作整數分支操作L.D F0，0（R1）L.D F6，-8（R1）nopnopnopL.D F10，-16（R1）L.D F14，-24（R1）nopnopnopL.D F18，-32（R1）L.D F22，-40（R1）ADD.D

21、F4，F0，F2ADD.D F8，F6，F2nopL.D F26，-48（R1）nopADD.D F12，F10，F2ADD.D F16，F14，F2nopnopnopADD.D F20，F18，F2ADD.D F24，F22，F2nopS.D 0（R1），），F4S.D -8（R1），），F8ADD.D F28，F26，F2nopnopS.D -16（R1），），F12S.D -24（R1），），F16nopnopnopS.D -32（R1），），F20S.D -40（R1），），F24nopnopDADDUI R1，R1，#56S.D 8（R1），），F28nopnopnopBNE R1，

22、R2，Loop2929/89/89 VLIW性能分析VLIW目標代碼編碼效率低q 為消除流水線為消除流水線“空轉空轉”需要增加循環(huán)展開的次數需要增加循環(huán)展開的次數 q 很難從應用程序中找到足夠多的并行指令填滿很難從應用程序中找到足夠多的并行指令填滿VLIW指指 令中的每一個令中的每一個slot VLIW流水線的互鎖機制q VLIW處理器中沒有實現任何相關檢測邏輯，而是靠互處理器中沒有實現任何相關檢測邏輯，而是靠互 鎖機制保證執(zhí)行結果的正確鎖機制保證執(zhí)行結果的正確q 這種簡單的互鎖機制將造成較大的開銷這種簡單的互鎖機制將造成較大的開銷目標代碼兼容性差q 二進制翻譯二進制翻譯6.3 靜態(tài)多指令流出

23、VLIW技術3030/89/89 性能比較多流出處理器 vs. 向量處理器即使對于一些結構不規(guī)則的代碼，多流出處理器也能從中挖掘出一些指令級并行。多流出處理器對存儲系統(tǒng)沒有過高的要求，價格較便宜、由Cache和主存構成的多層次存儲子系統(tǒng)即可滿足其對性能的要求。6.3 靜態(tài)多指令流出VLIW技術結論：結論：多流出處理器已成為當前實現指令級并行的主要選多流出處理器已成為當前實現指令級并行的主要選擇，而向量處理器則通常是作為協處理器集成到計算機系擇，而向量處理器則通常是作為協處理器集成到計算機系統(tǒng)中，以加速特定類型的應用程序。統(tǒng)中，以加速特定類型的應用程序。 3131/89/89超標量和VLIW結構

24、都存在嚴重不足q 超標量硬件復雜度太高，超標量硬件復雜度太高，8流出成為極限；流出成為極限；q VLIW存在代碼兼容問題，編譯器智能程度不夠。存在代碼兼容問題，編譯器智能程度不夠。EPIC技術在VLIW基礎上融合了超標量的一些優(yōu)點q 編譯器通過蹤跡調度、超塊調度等帶有極強猜測性的優(yōu)化編譯器通過蹤跡調度、超塊調度等帶有極強猜測性的優(yōu)化 技術盡可能多地挖掘指令級并行。技術盡可能多地挖掘指令級并行。 q 流水線硬件則提供豐富的計算資源實現這些指令級并行，流水線硬件則提供豐富的計算資源實現這些指令級并行， 并通過專門的機制確保在程序執(zhí)行過程中出現預測錯誤時并通過專門的機制確保在程序執(zhí)行過程中出現預測錯

25、誤時 仍然能得到正確的運行結果，盡量減少由此引起的額外開仍然能得到正確的運行結果，盡量減少由此引起的額外開 銷。銷。6.4 顯示并行指令計算EPIC 3232/89/89什么是EPIC？q 指令級并行主要由編譯器負責開發(fā)，處理器為保證代碼正指令級并行主要由編譯器負責開發(fā)，處理器為保證代碼正 確執(zhí)行提供必要的硬件支持，只有在這些硬件機制的輔助確執(zhí)行提供必要的硬件支持，只有在這些硬件機制的輔助 下這些優(yōu)化技術才能高效完成。下這些優(yōu)化技術才能高效完成。q 系統(tǒng)結構必須提供某種通信機制，使得流水線硬件能夠了系統(tǒng)結構必須提供某種通信機制，使得流水線硬件能夠了 解編譯器解編譯器“安排安排”好的指令執(zhí)行順序

26、。好的指令執(zhí)行順序。EPIC編譯器的高級優(yōu)化技術q 非綁定分支非綁定分支q 謂詞執(zhí)行謂詞執(zhí)行q 前瞻執(zhí)行前瞻執(zhí)行6.4 顯示并行指令計算EPIC3333/89/891. 分支指令在傳統(tǒng)流水線上的執(zhí)行過程計算分支轉移條件生成分支目標地址取下一條指令譯碼并流出下一條指令 6.4.1 非綁定分支6.4 顯示并行指令計算EPIC 在傳統(tǒng)流水線上，分支指令都具有在傳統(tǒng)流水線上，分支指令都具有“原子原子性性”，即上述各操作被綁定在一起，不能分開。，即上述各操作被綁定在一起，不能分開。3434/89/89 非綁定分支技術核心思想：將分支指令劃分為多條粒度更小的指令，獨立執(zhí)行。q 準備操作：計算分支目標地址準

27、備操作：計算分支目標地址q 比較操作：計算分支轉移條件比較操作：計算分支轉移條件q 轉移操作：根據分支轉移條件是轉移操作：根據分支轉移條件是true還是還是false，改變控，改變控 制流或執(zhí)行順序的下一條指令。制流或執(zhí)行順序的下一條指令。運行時，流水線硬件根據前兩個操作的結果，動態(tài)地將第三個操作轉換為空操作或無條件轉移。q 前兩個操作應盡早完成前兩個操作應盡早完成6.4 顯示并行指令計算EPIC3535/89/891. 條件執(zhí)行機制條件執(zhí)行：指指令的執(zhí)行依賴于一定的條件，當條件為真時指令將正常執(zhí)行，否則將什么也不做。q實例：條件傳輸指令實例：條件傳輸指令例例6.4 在下面的語句中，在下面的語

28、句中， if（A=0）S=T；假設變量假設變量A、S、T的值分別保存在寄存器的值分別保存在寄存器R1、R2和和R3內。請內。請用分支指令和條件傳輸指令編寫功能相同的匯編代碼。用分支指令和條件傳輸指令編寫功能相同的匯編代碼。6.4.2 謂詞執(zhí)行6.4 顯示并行指令計算EPIC3636/89/89解：解：包含分支指令的包含分支指令的MIPS匯編代碼如下：匯編代碼如下：BNEZ R1，LADDU R2，R3，R0L：而使用條件傳輸指令而使用條件傳輸指令CMOVZ時的匯編代碼為：時的匯編代碼為：CMOVZ R2，R3，R1 指令指令CMOVZ有有3個操作數，個操作數，R2為目的操作數，為目的操作數，R

29、1和和R3是源操作是源操作數，執(zhí)行條件保存在寄存器數，執(zhí)行條件保存在寄存器R1中。中。 當當R1=0時，時，R3的值被復制到的值被復制到R2中，否則中，否則R2的內容不變。的內容不變。6.4 顯示并行指令計算EPIC3737/89/89分析q條件傳輸指令將分支指令引起的控制相關轉換為相對于條件傳輸指令將分支指令引起的控制相關轉換為相對于分支轉移條件（分支轉移條件（R1）的數據相關。）的數據相關。q條件執(zhí)行機制能夠刪除代碼中那些行為難以預測的分支條件執(zhí)行機制能夠刪除代碼中那些行為難以預測的分支指令，提高分支預測準確率，并減少由于分支預測錯誤指令，提高分支預測準確率，并減少由于分支預測錯誤帶來的性

30、能損失。帶來的性能損失。q無論指令的執(zhí)行條件是否為真，指令都將被讀出、譯碼無論指令的執(zhí)行條件是否為真，指令都將被讀出、譯碼并執(zhí)行。并執(zhí)行。q這種編譯優(yōu)化技術叫做條件轉換。這種編譯優(yōu)化技術叫做條件轉換。6.4 顯示并行指令計算EPIC3838/89/89 條件傳輸指令的應用計算絕對值求絕對值的運算A = abs(B)，對應的C語句為：if（B0）A=-B; else A=B;使用條件傳輸指令后，代碼段如下（假設變量A和B分別被保存在寄存器R1和R2中）：SUB R1，R0，R2 / A = -BSLT R3，R2，R0 / 若若B0，R3=1，/ 否則否則R3=0CMOVZ R1，R2，R3/

31、R3=0時，時，A = B6.4 顯示并行指令計算EPIC3939/89/89 謂詞執(zhí)行機制條件傳輸指令的性能問題q隨著指令數的增加，經過條件轉換得到的條件傳輸指令隨著指令數的增加，經過條件轉換得到的條件傳輸指令和條件計算指令的數量也將增加，這會大大降低目標代和條件計算指令的數量也將增加，這會大大降低目標代碼的效率。碼的效率。謂詞執(zhí)行（predicated execution）q給指令集中的每條指令都增加一個執(zhí)行條件，這個執(zhí)行給指令集中的每條指令都增加一個執(zhí)行條件，這個執(zhí)行條件就叫做條件就叫做謂詞謂詞（predicate）。）。q若謂詞為真，指令正常執(zhí)行，否則什么也不做。若謂詞為真，指令正常執(zhí)

32、行，否則什么也不做。6.4 顯示并行指令計算EPIC4040/89/89 謂詞執(zhí)行機制實例分析6.4 顯示并行指令計算EPIC 例例6.5 假設在一個周期內，某雙流出的超標量處理器可以同時假設在一個周期內，某雙流出的超標量處理器可以同時執(zhí)行一個訪存操作和一個執(zhí)行一個訪存操作和一個ALU操作，或者僅執(zhí)行一個分支操作。受操作，或者僅執(zhí)行一個分支操作。受此限制，下面這段匯編代碼的執(zhí)行效率并不高，表現在：此限制，下面這段匯編代碼的執(zhí)行效率并不高，表現在： （1）第二個周期只能流出一條）第二個周期只能流出一條ALU指令，訪存單元空閑；指令，訪存單元空閑； （2）當分支轉移不成功時，）當分支轉移不成功時，

33、BEQZ指令后的兩條指令后的兩條LW指令之間存指令之間存在的數據相關將引起流水線暫停。在的數據相關將引起流水線暫停。試通過謂詞執(zhí)行機制解決這兩個問題，減少此段代碼的執(zhí)行開銷。試通過謂詞執(zhí)行機制解決這兩個問題，減少此段代碼的執(zhí)行開銷。4141/89/89例例6.5的代碼段的代碼段6.4 顯示并行指令計算EPIC周期周期指令指令1 1指令指令2 21 1LW R1LW R1，4040（R2R2）ADD R3ADD R3，R4R4，R5R52 2ADD R6ADD R6，R3R3，R7R73 3BEQZ R10BEQZ R10，L L4 4LW R8LW R8，0 0（R10R10）5 5LW R9

34、LW R9，0 0（R8R8）4242/89/89 解解 我們用我們用LWC表示帶謂詞的表示帶謂詞的LW指令，并假設該指令的執(zhí)行條指令，并假設該指令的執(zhí)行條件為謂詞不等于件為謂詞不等于0。這樣，。這樣，BEQZ后的第一條后的第一條LW指令就可以被轉換指令就可以被轉換為為LWC指令，并被調度到第二個周期執(zhí)行，如下所示：指令，并被調度到第二個周期執(zhí)行，如下所示：6.4 顯示并行指令計算EPIC周期周期指令指令1 1指令指令2 21 1LW R1LW R1，4040（R2R2）ADD R3ADD R3，R4R4，R5R52 2LWC R8LWC R8，2020（R10R10），），R10R10ADD

35、 R6ADD R6，R3R3，R7R73 3BEQZ R10BEQZ R10，L L4 4LW R9LW R9，0 0（R8R8）4343/89/89分析q調度后代碼的執(zhí)行時間縮短了。調度后代碼的執(zhí)行時間縮短了。q若分支轉移成功，若分支轉移成功，LWC將被轉換為空操作，這不影響結將被轉換為空操作，這不影響結果的正確性，但也不會縮短執(zhí)行時間。果的正確性，但也不會縮短執(zhí)行時間。q周期周期4中的中的LW指令轉換為指令轉換為LWC，結果如何？，結果如何？6.4 顯示并行指令計算EPIC周期周期指令指令1 1指令指令2 21 1LW R1LW R1，4040（R2R2）ADD R3ADD R3，R4R4

36、，R5R52 2LWC R8LWC R8，2020（R10R10），），R10R10ADD R6ADD R6，R3R3，R7R73 3BEQZ R10BEQZ R10，L L4 4LW R9LW R9，0 0（R8R8）4444/89/89 謂詞執(zhí)行機制異常處理謂詞執(zhí)行增加了異常處理的復雜度例若LWC指令執(zhí)行時發(fā)生缺頁中斷，如何處理？qLWC的謂詞為的謂詞為true，中斷本應發(fā)生；，中斷本應發(fā)生；qLWC的謂詞為的謂詞為false，中斷不應發(fā)生。，中斷不應發(fā)生。6.4 顯示并行指令計算EPIC周期周期指令指令1 1指令指令2 21 1LW R1LW R1，4040（R2R2）ADD R3ADD

37、 R3，R4R4，R5R52 2LWC R8LWC R8，2020（R10R10），），R10R10ADD R6ADD R6，R3R3，R7R73 3BEQZ R10BEQZ R10，L L4 4LW R9LW R9，0 0（R8R8）4545/89/89 如何將謂詞為假的指令轉換為空操作？兩種方法q 流水線前端指令流出時流水線前端指令流出時q 流水線后端結果確認時流水線后端結果確認時一般采用第二種方法q 為什么？為什么？6.4 顯示并行指令計算EPIC4646/89/891. 概述謂詞執(zhí)行與全局指令調度的不足之處q 僅有少量結構全面實現謂詞執(zhí)行僅有少量結構全面實現謂詞執(zhí)行q 全局指令調度往往

38、需要補償代碼全局指令調度往往需要補償代碼EPIC通過前瞻執(zhí)行提高猜測執(zhí)行的效果什么是前瞻執(zhí)行？q 在數據相關或控制相關尚未消除時，將指令調度到相關在數據相關或控制相關尚未消除時，將指令調度到相關 指令前猜測執(zhí)行。指令前猜測執(zhí)行。q 通過硬件機制完成異常處理，確保正確性。通過硬件機制完成異常處理，確保正確性。6.4.3 前瞻執(zhí)行6.4 顯示并行指令計算EPIC4747/89/89影響前瞻執(zhí)行效果的因素q 編譯器能力的高低：能否準確識別可以被前瞻執(zhí)行的指令。編譯器能力的高低：能否準確識別可以被前瞻執(zhí)行的指令。q 異常處理機制：能否推遲處理由被前瞻執(zhí)行的指令引起的異常處理機制：能否推遲處理由被前瞻執(zhí)

39、行的指令引起的 異常，直到確定前瞻指令確實被執(zhí)行后。異常，直到確定前瞻指令確實被執(zhí)行后。q 如何避免前瞻引起的錯誤？如何避免前瞻引起的錯誤？6.4 顯示并行指令計算EPIC4848/89/89 實例分析6.4 顯示并行指令計算EPIC 例例6.6 下面是一個下面是一個if-then-else結構的結構的C程序段以及相應的程序段以及相應的MIPS匯匯編代碼段，其中變量編代碼段，其中變量A和和B分別被保存在地址為分別被保存在地址為0(R3)和和0(R2)的存儲的存儲單元中。若分支轉移不成功的概率很大，請利用前瞻執(zhí)行技術將第單元中。若分支轉移不成功的概率很大，請利用前瞻執(zhí)行技術將第二條二條LD指令調

40、度到分支指令指令調度到分支指令BNEZ前執(zhí)行。假設寄存器前執(zhí)行。假設寄存器R14空閑。空閑。4949/89/89C C語句：語句： if if （A0A0）A=A+4A=A+4；else A=Belse A=B；匯編指令：匯編指令： LD LDR1R1，0 0（R3R3） / / 取取A A BNEZ BNEZR1R1，L1L1 /（A0A0）? ? LD LDR1R1，0 0（R2R2） / A=B/ A=B（elseelse部分）部分） J JL2L2L1L1：DADDIDADDIR1R1，R1R1，#4 #4 / A=A+4(then/ A=A+4(then部分部分) )L2L2：SDS

41、DR1R1，0 0（R3R3） / / 存存A A6.4 顯示并行指令計算EPIC5050/89/89解解 調度結果如下：調度結果如下：LDLDR1R1，0 0（R3R3）/ / 取取A AsLDsLDR14R14，0 0（R2R2） / / 取取B B，前瞻執(zhí)行，前瞻執(zhí)行BEQZBEQZR1R1，L3L3DADDI R14DADDI R14，R1R1，#4#4 / / A=A+4A=A+4L3L3：SDSDR14R14，0 0（R3R3） / / A=BA=B6.4 顯示并行指令計算EPIC5151/89/89 前瞻執(zhí)行異常處理機制問題：若執(zhí)行sLD時發(fā)生異常應該如何處理？q 有四種方法有四

42、種方法q 終止性異常終止性異常 vs 可繼續(xù)異?？衫^續(xù)異常方法一： 立即處理q 此前瞻指令引起的異常只是簡單地返回一個未定義值即可此前瞻指令引起的異常只是簡單地返回一個未定義值即可 ，而不是立即結束程序的運行。，而不是立即結束程序的運行。q 前瞻正確時，正在執(zhí)行的程序不會被終止，但它的執(zhí)行結前瞻正確時，正在執(zhí)行的程序不會被終止，但它的執(zhí)行結 果肯定是錯誤的。果肯定是錯誤的。q 前瞻錯誤時，程序也將繼續(xù)執(zhí)行下去，只是處理該異常的前瞻錯誤時，程序也將繼續(xù)執(zhí)行下去，只是處理該異常的 返回值不會被使用。返回值不會被使用。6.4 顯示并行指令計算EPIC5252/89/89方法二：借助專門的檢測指令判斷

43、是否需要處理q代碼實例代碼實例LDLDR1R1，0 0（R3R3） / / 取取A AsLDsLD R14R14，0 0（R2R2） / / 取取B B，前瞻執(zhí)行，前瞻執(zhí)行BEQZBEQZR1R1，L1L1SPECCKSPECCK0 0（R2R2） / sLD/ sLD是否產生異常是否產生異常J JL2L2L1L1：DADDIDADDIR14R14，R1R1，#4#4 / A=A+4/ A=A+4L2L2：SDSD R14R14，0 0（R3R3） / / A=BA=BqSPECCK的執(zhí)行條件與的執(zhí)行條件與sLD指令相同（分支轉移失?。┲噶钕嗤ǚ种мD移失敗）q基本思想：基本思想：推遲推遲處理

44、由前瞻指令處理由前瞻指令sLD引發(fā)的異常，直到已確引發(fā)的異常，直到已確定該指令確實應該被執(zhí)行定該指令確實應該被執(zhí)行 。6.4 顯示并行指令計算EPIC5353/89/89方法三：借助寄存器狀態(tài)位判斷是否需要處理p為每個通用寄存器增加一個特殊的狀態(tài)標志位：為每個通用寄存器增加一個特殊的狀態(tài)標志位：“poison”位位p前瞻指令引發(fā)的可繼續(xù)異常都將被立即處理。前瞻指令引發(fā)的可繼續(xù)異常都將被立即處理。p前瞻指令引發(fā)終止性異常時，其目的寄存器前瞻指令引發(fā)終止性異常時，其目的寄存器R的的poison位將位將被置被置1，否則該位將被清，否則該位將被清0。p當前瞻指令之后的另一條指令訪問當前瞻指令之后的另一

45、條指令訪問R時，若時，若R的的poison位為位為1將觸發(fā)一個終止性異常。將觸發(fā)一個終止性異常。q基本思想：基本思想：將前瞻指令引起異常的處理推遲到另一條指令訪將前瞻指令引起異常的處理推遲到另一條指令訪問前瞻指令的目的寄存器時。問前瞻指令的目的寄存器時。6.4 顯示并行指令計算EPIC5454/89/89方法四：借助再定序緩沖器完成q 將指令的執(zhí)行結果保存在再定序緩沖器內，并按指令流出將指令的執(zhí)行結果保存在再定序緩沖器內，并按指令流出 的順序依次確認。的順序依次確認。q 前瞻指令的確認時機被推遲，直至能夠確定該指令的前瞻前瞻指令的確認時機被推遲，直至能夠確定該指令的前瞻 執(zhí)行是正確（或錯誤）的

46、。執(zhí)行是正確（或錯誤）的。q 除了需要再定序緩沖器等硬件機制的支持外，也需要在編除了需要再定序緩沖器等硬件機制的支持外，也需要在編 譯時標出所有被前瞻的指令，以及這些指令所跨越的條件譯時標出所有被前瞻的指令，以及這些指令所跨越的條件 分支。分支。6.4 顯示并行指令計算EPIC5555/89/89 控制前瞻將load調度到store之前前瞻執(zhí)行最常見的數據前瞻q為保證正確性，編譯器總是會選擇保守的調度方法，認為相為保證正確性，編譯器總是會選擇保守的調度方法，認為相鄰的鄰的store與與load間存在地址沖突，但在很多情況下，地址并間存在地址沖突，但在很多情況下，地址并不沖突。不沖突。q盡早完成

47、盡早完成load指令有助于縮短關鍵路徑的長度。指令有助于縮短關鍵路徑的長度。硬件地址沖突檢測機制q當當loadload指令前瞻執(zhí)行時，流水線硬件會將它訪存的地址記錄指令前瞻執(zhí)行時，流水線硬件會將它訪存的地址記錄在一個特殊的地址表中。在一個特殊的地址表中。6.4 顯示并行指令計算EPIC5656/89/89q每執(zhí)行一條每執(zhí)行一條storestore指令，流水線硬件將該指令的訪存地址與指令，流水線硬件將該指令的訪存地址與地址表中的各有效項進行匹配，命中則說明出現地址沖突，地址表中的各有效項進行匹配，命中則說明出現地址沖突，前瞻失敗。前瞻失敗。q若控制流抵達若控制流抵達loadload指令原來所在的

48、位置時未出現沖突（編譯指令原來所在的位置時未出現沖突（編譯時在此位置放置檢測指令），說明前瞻成功，流水線硬件從時在此位置放置檢測指令），說明前瞻成功，流水線硬件從地址表中刪除對應的項。地址表中刪除對應的項。6.4 顯示并行指令計算EPIC數據前瞻失敗時的處理q僅僅load指令被前瞻執(zhí)行：由檢測指令重新執(zhí)行指令被前瞻執(zhí)行：由檢測指令重新執(zhí)行l(wèi)oad指令即可指令即可q數據相關于數據相關于load的其他指令也被前瞻執(zhí)行：需要補償代碼的其他指令也被前瞻執(zhí)行：需要補償代碼5757/89/89why？全局指令調度技術已經能夠很好地處理由分支指令引起的控制相關q 容易預測的容易預測的前瞻執(zhí)行前瞻執(zhí)行q 不容

49、易預測的不容易預測的謂詞執(zhí)行謂詞執(zhí)行指令間的數據相關對指令級并行開發(fā)的限制作用反而越來越大6.5 開發(fā)更多的指令級并行 5858/89/891. 循環(huán)攜帶相關循環(huán)攜帶相關是指一個循環(huán)的某個疊代中的指令與其他疊代中的指令之間的數據相關。 例例6.7 6.7 在下面的循環(huán)中，在下面的循環(huán)中， forfor（i=1i=1；i=100i=100；i=i+1i=i+1） Ai+1 = Ai + Ci Ai+1 = Ai + Ci； / /* * S1 S1 * */ / Bi+1 = Bi + Ai+1 Bi+1 = Bi + Ai+1； / /* * S2 S2 * */ / 假設數組假設數組A A、

50、B B和和C C中所有元素的存儲地址都互不相同，請問語句中所有元素的存儲地址都互不相同，請問語句S1S1與與S2S2之間存在哪些數據相關？之間存在哪些數據相關？6.5.1 挖掘更多的循環(huán)級并行6.5 開發(fā)更多的指令級并行5959/89/89 解解 S1S1和和S2S2之間存在兩種不同類型的數據相關：之間存在兩種不同類型的數據相關：q循環(huán)攜帶循環(huán)攜帶RAWRAW數據相關：相鄰連詞疊代的語句數據相關：相鄰連詞疊代的語句S1S1之間，相鄰之間，相鄰 兩次疊代中的語句兩次疊代中的語句S2S2之間。之間。qRAWRAW數據相關：同一疊代內的語句數據相關：同一疊代內的語句S2S2與與S1S1之間。之間。

51、分析:q 循環(huán)攜帶相關迫使指令只能按照所在疊代的先后順序依循環(huán)攜帶相關迫使指令只能按照所在疊代的先后順序依 次執(zhí)行。次執(zhí)行。q 限制了同一疊代內存在數據相關的各語句之間的相對順序。限制了同一疊代內存在數據相關的各語句之間的相對順序。6.5 開發(fā)更多的指令級并行6060/89/89怎樣消除循環(huán)攜帶數據相關？ 例例6.8 6.8 在下面的循環(huán)中，語句在下面的循環(huán)中，語句S1S1和和S2S2之間存在哪些數據相關？之間存在哪些數據相關？該循環(huán)的各次疊代是否可以并行執(zhí)行？如果不能，請修改其代碼，該循環(huán)的各次疊代是否可以并行執(zhí)行？如果不能，請修改其代碼，使之可以并行。使之可以并行。forfor（i=1i=

52、1；i=100i=100；i=i+1i=i+1） Ai = Ai + BiAi = Ai + Bi；/ /* * S1 S1 * */ /Bi+1 = Ci + DiBi+1 = Ci + Di；/ /* * S2 S2 * */ / 6.5 開發(fā)更多的指令級并行6161/89/89 解解 第第i i次疊代中語句次疊代中語句S1S1與第與第i-1i-1次疊代中語句次疊代中語句S2S2之間存在之間存在RAWRAW類型類型的循環(huán)攜帶數據相關，但它們之間沒有形成環(huán)的循環(huán)攜帶數據相關，但它們之間沒有形成環(huán)( (S2S2與上次疊代的與上次疊代的S1S1不不相關相關) )。修改后代碼。修改后代碼A1 =

53、A1 + B1A1 = A1 + B1；forfor（i=1i=1；i=99i=99；i=i+1i=i+1） Bi+1 = Ci + DiBi+1 = Ci + Di； / /* * 原原S2 S2 * */ /Ai+1 = Ai+1 + Bi+1Ai+1 = Ai+1 + Bi+1； / /* * 原原S1 S1 * */ / B101 = C100 + D100B101 = C100 + D100；6.5 開發(fā)更多的指令級并行修改方法：修改方法：將存在循環(huán)攜帶相關的各條指令放在同一個疊代中將存在循環(huán)攜帶相關的各條指令放在同一個疊代中6262/89/89復雜循環(huán)攜帶數據相關的處理forfor

54、（i=6i=6；i=100i=100；i=i+1i=i+1）Yi = Yi-5 + YiYi = Yi-5 + Yi； / / 相關距離為相關距離為5 5forfor（i=2i=2；i=100i=100；i=i+1i=i+1）Yi = Yi-1 + YiYi = Yi-1 + Yi； / / 相關距離為相關距離為1 16.5 開發(fā)更多的指令級并行編譯器必須檢測出這種遞歸關系編譯器必須檢測出這種遞歸關系(1) (1) 某些系統(tǒng)結構（特別是向量計算機）為遞歸提供了專門的硬件支持某些系統(tǒng)結構（特別是向量計算機）為遞歸提供了專門的硬件支持(2) (2) 這樣的遞歸結構中通常隱藏著大量的循環(huán)級并行這樣的

55、遞歸結構中通常隱藏著大量的循環(huán)級并行 6363/89/89 存儲別名分析什么是存儲別名q 一個元素可能同時擁有多個合法的地址表達式一個元素可能同時擁有多個合法的地址表達式q Ai+5、Aj*2-6、Ak數組是仿射的q 如果一個一維數組如果一個一維數組Am:n的下標可以被表示為形如的下標可以被表示為形如 ai+b的形式，那么就稱該數組是的形式，那么就稱該數組是仿射的仿射的（affine）。）。q 一個多維數組，如果它每一維的下標都是仿射的，那一個多維數組，如果它每一維的下標都是仿射的，那 么它就是仿射的。么它就是仿射的。6.5 開發(fā)更多的指令級并行6464/89/89GCD測試法q算法描述算法描

56、述n如果如果GCD(c, a)可以整除可以整除(d-b)，那么有可能存在存儲別名。，那么有可能存在存儲別名。n如果如果GCD測試的結果為假（不能整除），那么一定沒有存測試的結果為假（不能整除），那么一定沒有存儲別名存在。儲別名存在。 例例6.9 使用使用GCD測試方法判斷下面的循環(huán)中是否存在存儲別名。測試方法判斷下面的循環(huán)中是否存在存儲別名。for（i=1；i=100；i=i+1） x2*i+3 = x2*i * 5.0； 解解 在這個循環(huán)中，在這個循環(huán)中，a=2，b=3，c=2，d=0， 那么那么GCD(a, c)=2，而，而d-b=-3。 由于由于2不能整除不能整除-3，因此沒有存儲別名，

57、即無論，因此沒有存儲別名，即無論i取何值，取何值，x2*i+3與與x2*i都將表示數組都將表示數組x的不同元素。的不同元素。6.5 開發(fā)更多的指令級并行6565/89/89 數據相關分析除了檢測指令之間是否存在數據相關外，編譯器還會將識別出的數據相關進一步細分為真數據相關、輸出相關和反相關等不同類型，以便利用不同的優(yōu)化技術消除這些相關。常用的優(yōu)化有重命名、值傳播、高度消減等。 6.5 開發(fā)更多的指令級并行6666/89/89重命名優(yōu)化實例 例例6.10 找出下面循環(huán)中的所有數據相關，指出它們究竟是真數據找出下面循環(huán)中的所有數據相關，指出它們究竟是真數據相關、輸出相關、還是反相關，并利用重命名技

58、術消除其中的輸出相關、輸出相關、還是反相關，并利用重命名技術消除其中的輸出相關和反相關。相關和反相關。forfor（i=1i=1；i=100i=100；i=i+1i=i+1） Yi = Xi / aYi = Xi / a；/ /* * S1 S1 * */ /Xi = Xi + aXi = Xi + a； / /* * S2 S2 * */ /Zi = Yi + aZi = Yi + a； / /* * S3 S3 * */ /Yi = a YiYi = a Yi；/ /* * S4 S4 * */ / 6.5 開發(fā)更多的指令級并行6767/89/89解解 這這4 4條語句中存在以下相關：條語

59、句中存在以下相關：1. 1. S3S3與與S1S1和和S4S4與與S1S1之間分別存在真數據相關。之間分別存在真數據相關。2. 2. S2S2和和S1S1之間存在反相關。之間存在反相關。3. 3. S3S3和和S4S4之間存在反相關。之間存在反相關。4. 4. S1S1和和S4S4之間存在輸出相關。之間存在輸出相關。 forfor（i=1i=1；i=100i=100；i=i+1i=i+1） Yi = Xi / aYi = Xi / a；/ /* * S1 S1 * */ / Xi = Xi + a Xi = Xi + a； / /* * S2 S2 * */ / Zi = Yi + a Zi

60、= Yi + a； / /* * S3 S3 * */ / Yi = a Yi Yi = a Yi；/ /* * S4 S4 * */ / 6.5 開發(fā)更多的指令級并行6868/89/89 將原代碼變換為下面的形式，可以消除所有輸出相關和反相關。將原代碼變換為下面的形式，可以消除所有輸出相關和反相關。forfor（i=1i=1；i=100i=100；i=i+1i=i+1） / /* * 將數組將數組Y Y重命名為重命名為T T以消除輸出相關以消除輸出相關 * */ /Ti = Xi / cTi = Xi / c；/ /* * 將數組將數組X X重命名為重命名為X1X1以消除反相關以消除反相關