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

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

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

3、for (i=1000; i0; i-) xi = xi + s; xi = xi + s; 解：解：先把該程序翻譯成先把該程序翻譯成MIPS匯編語(yǔ)言代碼匯編語(yǔ)言代碼 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 基本指令調(diào)度及循環(huán)展開(kāi)在不進(jìn)行指令調(diào)度的情況下，根據(jù)表中給出的浮點(diǎn)流水線在不進(jìn)行指令調(diào)度的情況下，根據(jù)表中給出的浮點(diǎn)流水線中指令執(zhí)行的延遲，程序的實(shí)際執(zhí)行情況如下：中指令執(zhí)行的延遲，程序的實(shí)際執(zhí)行情況如下：指令流出時(shí)鐘指令流出時(shí)鐘Loo

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

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

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

7、轉(zhuǎn)）（空轉(zhuǎn)）14 指令流出時(shí)鐘指令流出時(shí)鐘ADD.DF12, F10, F215（空轉(zhuǎn)）（空轉(zhuǎn)）16（空轉(zhuǎn)）（空轉(zhuǎn)）17S.DF12, -16（R1）18L.DF14, -24（R1）19（空轉(zhuǎn)）（空轉(zhuǎn)）20ADD.DF16, F14, F221（空轉(zhuǎn)）（空轉(zhuǎn)）22（空轉(zhuǎn)）（空轉(zhuǎn)）23S.DF16, -24（R1）24DADDIUR1, R1, # -3225（空轉(zhuǎn)）（空轉(zhuǎn)）26BNER1, R2, Loop27（空轉(zhuǎn)）（空轉(zhuǎn)）2850%是空轉(zhuǎn)周期！是空轉(zhuǎn)周期！調(diào)度后的代碼如下：調(diào)度后的代碼如下： 指令流出時(shí)鐘指令流出時(shí)鐘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沒(méi)有空轉(zhuǎn)周期！沒(méi)有空轉(zhuǎn)周期！結(jié)論：結(jié)論：通過(guò)循環(huán)展通過(guò)循環(huán)展開(kāi)、寄存器重命名開(kāi)、寄存器重命名和指令調(diào)度，可以和指令調(diào)度，可以有效開(kāi)發(fā)出指令級(jí)有效開(kāi)發(fā)出指令級(jí)并行。并行。1212/89/896.1 基本指令調(diào)度及循環(huán)

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

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

11、段X，基本塊，基本塊elsepartJjointhenpart：/ 基本塊基本塊thenpartSD，0(R2)/ 指令指令I(lǐng)1，對(duì)應(yīng)語(yǔ)句，對(duì)應(yīng)語(yǔ)句3join：SD，0(R3)/ 指令指令I(lǐng)2，對(duì)應(yīng)語(yǔ)句，對(duì)應(yīng)語(yǔ)句51616/89/896.2 跨越基本塊的靜態(tài)指令調(diào)度調(diào)度指令I(lǐng)1q直接將直接將I1移到移到BEQZ前是否會(huì)產(chǎn)生錯(cuò)誤結(jié)果？前是否會(huì)產(chǎn)生錯(cuò)誤結(jié)果？q向基本塊向基本塊elsepart中增加中增加補(bǔ)償代碼補(bǔ)償代碼q補(bǔ)償代碼有可能帶來(lái)額外時(shí)間開(kāi)銷補(bǔ)償代碼有可能帶來(lái)額外時(shí)間開(kāi)銷調(diào)度指令I(lǐng)2q將將I2移動(dòng)到基本塊移動(dòng)到基本塊thenpart中，同時(shí)復(fù)制到中，同時(shí)復(fù)制到elsepart中。中。q若不

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

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

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

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

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

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

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

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

20、期，計(jì)算出計(jì)算出7個(gè)結(jié)果，即平均每得到一個(gè)結(jié)果需要個(gè)結(jié)果，即平均每得到一個(gè)結(jié)果需要1.29個(gè)個(gè)周期。周期。 VLIW的不足：q編碼效率僅比編碼效率僅比50%略高一些略高一些q所需要的寄存器數(shù)量也大大增加所需要的寄存器數(shù)量也大大增加 2828/89/896.3 靜態(tài)多指令流出VLIW技術(shù)訪存操作訪存操作1訪存操作訪存操作2浮點(diǎn)操作浮點(diǎn)操作1浮點(diǎn)操作浮點(diǎn)操作2整數(shù)分支操作整數(shù)分支操作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，F(xiàn)0，F(xiàn)2ADD.D F8，F(xiàn)6，F(xiàn)2nopL.D F26，-48（R1）nopADD.D F12，F(xiàn)10，F(xiàn)2ADD.D F16，F(xiàn)14，F(xiàn)2nopnopnopADD.D F20，F(xiàn)18，F(xiàn)2ADD.D F24，F(xiàn)22，F(xiàn)2nopS.D 0（R1），），F(xiàn)4S.D -8（R1），），F(xiàn)8ADD.D F28，F(xiàn)26，F(xiàn)2nopnopS.D -16（R1），），F(xiàn)12S.D -24（R1），），F(xiàn)16nopnopnopS.D -32（R1），），F(xiàn)20S.D -40（R1），），F(xiàn)24nopnopDADDUI R1，R1，#56S.D 8（R1），），F(xiàn)28nopnopnopBNE R1，

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

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

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

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

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

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

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

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

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

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

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

33、BEQZ指令后的兩條指令后的兩條LW指令之間存指令之間存在的數(shù)據(jù)相關(guān)將引起流水線暫停。在的數(shù)據(jù)相關(guān)將引起流水線暫停。試通過(guò)謂詞執(zhí)行機(jī)制解決這兩個(gè)問(wèn)題，減少此段代碼的執(zhí)行開(kāi)銷。試通過(guò)謂詞執(zhí)行機(jī)制解決這兩個(gè)問(wèn)題，減少此段代碼的執(zhí)行開(kāi)銷。4141/89/89例例6.5的代碼段的代碼段6.4 顯示并行指令計(jì)算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指令，并假設(shè)該指令的執(zhí)行條指令，并假設(shè)該指令的執(zhí)行條件為謂詞不等于件為謂詞不等于0。這樣，。這樣，BEQZ后的第一條后的第一條LW指令就可以被轉(zhuǎn)換指令就可以被轉(zhuǎn)換為為L(zhǎng)WC指令，并被調(diào)度到第二個(gè)周期執(zhí)行，如下所示：指令，并被調(diào)度到第二個(gè)周期執(zhí)行，如下所示：6.4 顯示并行指令計(jì)算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調(diào)度后代碼的執(zhí)行時(shí)間縮短了。調(diào)度后代碼的執(zhí)行時(shí)間縮短了。q若分支轉(zhuǎn)移成功，若分支轉(zhuǎn)移成功，LWC將被轉(zhuǎn)換為空操作，這不影響結(jié)將被轉(zhuǎn)換為空操作，這不影響結(jié)果的正確性，但也不會(huì)縮短執(zhí)行時(shí)間。果的正確性，但也不會(huì)縮短執(zhí)行時(shí)間。q周期周期4中的中的LW指令轉(zhuǎn)換為指令轉(zhuǎn)換為L(zhǎng)WC，結(jié)果如何？，結(jié)果如何？6.4 顯示并行指令計(jì)算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í)行機(jī)制異常處理謂詞執(zhí)行增加了異常處理的復(fù)雜度例若LWC指令執(zhí)行時(shí)發(fā)生缺頁(yè)中斷，如何處理？qLWC的謂詞為的謂詞為true，中斷本應(yīng)發(fā)生；，中斷本應(yīng)發(fā)生；qLWC的謂詞為的謂詞為false，中斷不應(yīng)發(fā)生。，中斷不應(yīng)發(fā)生。6.4 顯示并行指令計(jì)算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 如何將謂詞為假的指令轉(zhuǎn)換為空操作？?jī)煞N方法q 流水線前端指令流出時(shí)流水線前端指令流出時(shí)q 流水線后端結(jié)果確認(rèn)時(shí)流水線后端結(jié)果確認(rèn)時(shí)一般采用第二種方法q 為什么？為什么？6.4 顯示并行指令計(jì)算EPIC4646/89/891. 概述謂詞執(zhí)行與全局指令調(diào)度的不足之處q 僅有少量結(jié)構(gòu)全面實(shí)現(xiàn)謂詞執(zhí)行僅有少量結(jié)構(gòu)全面實(shí)現(xiàn)謂詞執(zhí)行q 全局指令調(diào)度往往

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

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

40、度到分支指令指令調(diào)度到分支指令BNEZ前執(zhí)行。假設(shè)寄存器前執(zhí)行。假設(shè)寄存器R14空閑。空閑。4949/89/89C C語(yǔ)句：語(yǔ)句： 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 顯示并行指令計(jì)算EPIC5050/89/89解解 調(diào)度結(jié)果如下：調(diào)度結(jié)果如下：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 顯示并行指令計(jì)算EPIC5151/89/89 前瞻執(zhí)行異常處理機(jī)制問(wèn)題：若執(zhí)行sLD時(shí)發(fā)生異常應(yīng)該如何處理？q 有四種方法有四

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

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

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

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

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

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

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

49、易預(yù)測(cè)的不容易預(yù)測(cè)的謂詞執(zhí)行謂詞執(zhí)行指令間的數(shù)據(jù)相關(guān)對(duì)指令級(jí)并行開(kāi)發(fā)的限制作用反而越來(lái)越大6.5 開(kāi)發(fā)更多的指令級(jí)并行 5858/89/891. 循環(huán)攜帶相關(guān)循環(huán)攜帶相關(guān)是指一個(gè)循環(huán)的某個(gè)疊代中的指令與其他疊代中的指令之間的數(shù)據(jù)相關(guā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 * */ / 假設(shè)數(shù)組假設(shè)數(shù)組A A、

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

51、分析:q 循環(huán)攜帶相關(guān)迫使指令只能按照所在疊代的先后順序依循環(huán)攜帶相關(guān)迫使指令只能按照所在疊代的先后順序依 次執(zhí)行。次執(zhí)行。q 限制了同一疊代內(nèi)存在數(shù)據(jù)相關(guān)的各語(yǔ)句之間的相對(duì)順序。限制了同一疊代內(nèi)存在數(shù)據(jù)相關(guān)的各語(yǔ)句之間的相對(duì)順序。6.5 開(kāi)發(fā)更多的指令級(jí)并行6060/89/89怎樣消除循環(huán)攜帶數(shù)據(jù)相關(guān)？ 例例6.8 6.8 在下面的循環(huán)中，語(yǔ)句在下面的循環(huán)中，語(yǔ)句S1S1和和S2S2之間存在哪些數(shù)據(jù)相關(guān)？之間存在哪些數(shù)據(jù)相關(guān)？該循環(huán)的各次疊代是否可以并行執(zhí)行？如果不能，請(qǐng)修改其代碼，該循環(huán)的各次疊代是否可以并行執(zhí)行？如果不能，請(qǐng)修改其代碼，使之可以并行。使之可以并行。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 開(kāi)發(fā)更多的指令級(jí)并行6161/89/89 解解 第第i i次疊代中語(yǔ)句次疊代中語(yǔ)句S1S1與第與第i-1i-1次疊代中語(yǔ)句次疊代中語(yǔ)句S2S2之間存在之間存在RAWRAW類型類型的循環(huán)攜帶數(shù)據(jù)相關(guān)，但它們之間沒(méi)有形成環(huán)的循環(huán)攜帶數(shù)據(jù)相關(guān)，但它們之間沒(méi)有形成環(huán)( (S2S2與上次疊代的與上次疊代的S1S1不不相關(guān)相關(guān)) )。修改后代碼。修改后代碼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 開(kāi)發(fā)更多的指令級(jí)并行修改方法：修改方法：將存在循環(huán)攜帶相關(guān)的各條指令放在同一個(gè)疊代中將存在循環(huán)攜帶相關(guān)的各條指令放在同一個(gè)疊代中6262/89/89復(fù)雜循環(huán)攜帶數(shù)據(jù)相關(guān)的處理forfor

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

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

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

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

58、術(shù)消除其中的輸出相關(guān)、輸出相關(guān)、還是反相關(guān)，并利用重命名技術(shù)消除其中的輸出相關(guān)和反相關(guān)。相關(guān)和反相關(guān)。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 開(kāi)發(fā)更多的指令級(jí)并行6767/89/89解解 這這4 4條語(yǔ)句中存在以下相關(guān)：條語(yǔ)

59、句中存在以下相關(guān)：1. 1. S3S3與與S1S1和和S4S4與與S1S1之間分別存在真數(shù)據(jù)相關(guān)。之間分別存在真數(shù)據(jù)相關(guān)。2. 2. S2S2和和S1S1之間存在反相關(guān)。之間存在反相關(guān)。3. 3. S3S3和和S4S4之間存在反相關(guān)。之間存在反相關(guān)。4. 4. S1S1和和S4S4之間存在輸出相關(guān)。之間存在輸出相關(guān)。 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 開(kāi)發(fā)更多的指令級(jí)并行6868/89/89 將原代碼變換為下面的形式，可以消除所有輸出相關(guān)和反相關(guān)。將原代碼變換為下面的形式，可以消除所有輸出相關(guān)和反相關(guān)。forfor（i=1i=1；i=100i=100；i=i+1i=i+1） / /* * 將數(shù)組將數(shù)組Y Y重命名為重命名為T T以消除輸出相關(guān)以消除輸出相關(guān) * */ /Ti = Xi / cTi = Xi / c；/ /* * 將數(shù)組將數(shù)組X X重命名為重命名為X1X1以消除反相關(guān)以消除反相關(guān)