計算機(jī)系統(tǒng)結(jié)構(gòu)第6章.ppt

《計算機(jī)系統(tǒng)結(jié)構(gòu)第6章.ppt》由會員分享，可在線閱讀，更多相關(guān)《計算機(jī)系統(tǒng)結(jié)構(gòu)第6章.ppt（89頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第6章 指令級并行的開發(fā) 軟件方法,6.1 基本指令調(diào)度及循環(huán)展開 6.2 跨越基本塊的靜態(tài)指令調(diào)度 6.3 靜態(tài)多指令流出：VLIW技術(shù) 6.4 顯式并行指令計算EPIC 6.5 開發(fā)更多的指令級并行 6.6 實例：IA-64體系結(jié)構(gòu),指令調(diào)度：找出不相關(guān)的指令序列，讓它們在流水線上重疊并行執(zhí)行。 制約編譯器指令調(diào)度的因素 程序固有的指令級并行 流水線功能部件的延遲,6.1 基本指令調(diào)度及循環(huán)展開,6.1.1 指令調(diào)度的基本方法,,表6.1本節(jié)使用的浮點(diǎn)流水線的延遲,6.1 基本指令調(diào)度及循環(huán)展開,,例6.1 對于下面的源代碼，轉(zhuǎn)換成MIPS匯編語言，在不進(jìn)行指令調(diào)度和進(jìn)行指令調(diào)度兩種情況下

2、，分析其代碼一次循環(huán)所需的執(zhí)行時間。 for (i=1000; i0; i--) 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, Loop,6.1 基本指令調(diào)度及循環(huán)展開,在不進(jìn)行指令調(diào)度的情況下，根據(jù)表中給出的浮點(diǎn)流水線中指令執(zhí)行的延遲，程序的實際執(zhí)行情況如下： 指令流出時鐘 Loop：L.D F0, 0(R1)1 (空轉(zhuǎn))2 ADD.D F4, F0

3、, F23 (空轉(zhuǎn))4(空轉(zhuǎn))5 S.D F4, 0(R1)6 DADDIU R1, R1, #-87 (空轉(zhuǎn))8 BNE R1, R2, Loop9 (空轉(zhuǎn))10,6.1 基本指令調(diào)度及循環(huán)展開,在用編譯器對上述程序進(jìn)行指令調(diào)度以后，程序的執(zhí)行情況如下： 指令流出時鐘 Loop：L.D F0, 0(R1)1 DADDIU R1, R1, #-8 2 ADD.D F4, F0, F23 (空轉(zhuǎn))4BNE R1, R2, Loop 5 S.D F4, 8(R1)6,6.1 基本指令調(diào)度及循環(huán)展開,進(jìn)一步分析： 編譯時指令調(diào)度是怎樣減少整個指令序列在流水線上的執(zhí)行時間的？ 指令調(diào)度能否

4、跨越分支邊界？ 怎樣提高整個執(zhí)行過程中有效操作的比率？,循環(huán)展開 把循環(huán)體的代碼復(fù)制多次并按順序排放， 然后相應(yīng)調(diào)整循環(huán)的結(jié)束條件。 開發(fā)循環(huán)級并行的有效方法 例6.2 將例6.1中的循環(huán)展開3次得到4個循環(huán)體，然后對展開后的指令序列在不調(diào)度和調(diào)度兩種情況下，分析代碼的性能。假定R1的初值為32的倍數(shù)，即循環(huán)次數(shù)為4的倍數(shù)。消除冗余的指令，并且不要重復(fù)使用寄存器。,6.1.2 循環(huán)展開,6.1 基本指令調(diào)度及循環(huán)展開,展開后沒有調(diào)度的代碼如下(需要分配寄存器),指令流出時鐘 Loop:L.DF0, 0(R1)1 （空轉(zhuǎn)）2 ADD.DF4, F0, F23 （空轉(zhuǎn)）4 （空轉(zhuǎn)）5 S.

5、DF4, 0(R1)6 L.DF6, -8(R1)7 （空轉(zhuǎn)）8 ADD.DF8, F6, F29 （空轉(zhuǎn)）10 （空轉(zhuǎn)）11 S.DF8, -8(R1)12 L.DF10, -16(R1)13 （空轉(zhuǎn)）14,指令流出時鐘 ADD.DF12, F10, F215 （空轉(zhuǎn)）16 （空轉(zhuǎn)）17 S.DF12, -16（R1）18 L.DF14, -24（R1）19 （空轉(zhuǎn)）20 ADD.DF16, F14, F221 （空轉(zhuǎn)）22 （空轉(zhuǎn)）23 S.DF16, -24（R1）24 DADDIUR1, R1, # -3225 （空轉(zhuǎn)）26 BNER1, R2, Loop27 （空轉(zhuǎn)）28,,50%是

6、空轉(zhuǎn)周期！,調(diào)度后的代碼如下：,指令流出時鐘 Loop:L.DF0, 0（R1）1 L.DF6, -8（R1）2 L.DF10, -16（R1）3 L.DF14, -24（R1）4 ADD.DF4, F0, F25 ADD.DF8, F6, F26 ADD.DF12, F10, F27 ADD.DF16, F14, F28 S.DF4, 0（R1）9 S.DF8, -8（R1）10 DADDIUR1, R1, # -3212 S.DF12, 16（R1）11 BNER1, R2, Loop13 S.DF16, 8（R1）14,沒有空轉(zhuǎn)周期！,結(jié)論：通過循環(huán)展開、寄存器重命名和指令調(diào)度，可以有效

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

8、支條件為true(轉(zhuǎn)移)的概率大，全局指令調(diào)度時會將語句1、2、3、5合并為一個更大的基本塊。,,一個分支結(jié)構(gòu)的代碼段,如何保證分支條件為false時結(jié)果依然正確？ 如何將語句3和5調(diào)度到語句2之前？,6.2 跨越基本塊的靜態(tài)指令調(diào)度,將上圖中的代碼轉(zhuǎn)換為下面的MIPS匯編指令,,LDR4，0(R1)// 取A LDR5，0(R2)// 取B DADDUR4，R4，R5// A=A+B SD0(R1)，R4// 存A BNEZR4，elsepart// A=0則轉(zhuǎn)移 X// 代碼段X，基本塊elsepart Jjoin thenpart：// 基本塊thenpart SD，0(R2)// 指令

9、I1，對應(yīng)語句3 join： SD，0(R3)// 指令I(lǐng)2，對應(yīng)語句5,6.2 跨越基本塊的靜態(tài)指令調(diào)度,調(diào)度指令I(lǐng)1 直接將I1移到BEQZ前是否會產(chǎn)生錯誤結(jié)果？ 向基本塊elsepart中增加補(bǔ)償代碼 補(bǔ)償代碼有可能帶來額外時間開銷 調(diào)度指令I(lǐng)2 將I2移動到基本塊thenpart中，同時復(fù)制到elsepart中。 若不影響執(zhí)行結(jié)果，將I2調(diào)度到BEQZ前，同時刪除elsepart中的副本。,,6.2 跨越基本塊的靜態(tài)指令調(diào)度,全局指令調(diào)度是一個很復(fù)雜的問題 以I1的調(diào)度為例： 需要確定分支中基本塊thenpart和elsepart的執(zhí)行頻率各是多少？ 在分支語句前完成I1所需的開銷是

10、多大？ 調(diào)度I1是否能夠縮短thenpart塊的執(zhí)行時間？ I1是否是最佳的被調(diào)度對象？ 是否需要向elsepart塊中增加補(bǔ)償代碼，補(bǔ)償代碼開銷如何？怎樣生成補(bǔ)償代碼？,,概述 蹤跡（trace）：程序執(zhí)行的指令序列，通常由一個或多個基本塊組成，trace內(nèi)可以有分支，但一定不能包含循環(huán)。 蹤跡調(diào)度（trace scheduling）會優(yōu)化執(zhí)行頻率高的trace，減少其執(zhí)行開銷。由于需要添加補(bǔ)償代碼以確保正確性，那些執(zhí)行頻率較低的trace的開銷反而會有所增加。 蹤跡調(diào)度非常適合多流出處理器。,6.2.2 蹤跡調(diào)度,6.2 跨越基本塊的靜態(tài)指令調(diào)度,蹤跡調(diào)度的步驟 分為兩步：蹤跡選擇和蹤跡壓

11、縮 蹤跡選擇 從程序的控制流圖中選擇執(zhí)行頻率較高的路徑，每條路徑就是一條trace。 處理轉(zhuǎn)移成功與失敗概率相差較大的情況 循環(huán)結(jié)構(gòu)：循環(huán)展開 分支結(jié)構(gòu)：根據(jù)典型輸入集下的運(yùn)行統(tǒng)計信息,6.2 跨越基本塊的靜態(tài)指令調(diào)度,蹤跡選擇實例分析,6.2 跨越基本塊的靜態(tài)指令調(diào)度,,,將左邊的循環(huán)展開4次并把陰影部分(執(zhí)行頻率高)拼接在一起就可以得到一條trace； 一條trace可以有多個入口和多個出口。,蹤跡壓縮 對已生成的trace進(jìn)行指令調(diào)度和優(yōu)化，盡可能地縮短其執(zhí)行時間； 跨越trace內(nèi)部的入口或出口調(diào)度指令時必須非常小心，有時還需要增加補(bǔ)償代碼 。,6.2 跨越基本塊的靜態(tài)指令調(diào)度,,

12、三條trace：B1-B3、B4以及B5-B7 指令“y = x - y”被從B1調(diào)度到B3中，跨越了trace的一個出口； 需要向塊B2中增加補(bǔ)償代碼，即將指令“y = x - y”復(fù)制到B2的第一條指令之前 。,蹤跡調(diào)度的性能特點(diǎn) 蹤跡調(diào)度能夠提升性能的最根本原因在于選出的trace都是執(zhí)行頻率很高的路徑，減少它們的執(zhí)行開銷有助于縮短程序的總執(zhí)行時間。 對于某些應(yīng)用，補(bǔ)償代碼引起的開銷很有可能降低蹤跡調(diào)度的優(yōu)化效果。 蹤跡調(diào)度會大大增加編譯器的實現(xiàn)復(fù)雜度。,6.2 跨越基本塊的靜態(tài)指令調(diào)度,概述 在蹤跡調(diào)度中，如果trace入口或出口位于trace內(nèi)部，編譯器生成補(bǔ)償代碼的難度將大大增加，

13、而且編譯器很難評估這些補(bǔ)償代碼究竟會帶來多少性能損失。 超塊（superblock）是只能擁有一個入口，但可以擁有多個出口的結(jié)構(gòu) 超塊的構(gòu)造過程與trace相似，但怎樣確保只有一個入口？,6.2.3 超塊調(diào)度,6.2 跨越基本塊的靜態(tài)指令調(diào)度,,超塊構(gòu)造尾復(fù)制技術(shù),6.2 跨越基本塊的靜態(tài)指令調(diào)度,,,將左邊的循環(huán)展開4次并把陰影部分(執(zhí)行頻率高)拼接在一起就可以得到一個超塊； 超塊有1個入口和5個出口(n=4/3/2/1/0)。 除了n=0外，從其他4個出口退出超塊后，還需要繼續(xù)完成余下的n次疊代(黃色部分)。,,超塊調(diào)度的性能特點(diǎn) 尾復(fù)制技術(shù)簡化了補(bǔ)償代碼的生成過程，并降低了指令調(diào)

14、度的復(fù)雜度。 超塊結(jié)構(gòu)目標(biāo)代碼的體積也大大增加。 補(bǔ)償代碼的生成使得編譯過程更加復(fù)雜，而且由于無法準(zhǔn)確評估由補(bǔ)償代碼引起的時間開銷，這限制方法超塊調(diào)度的應(yīng)用范圍。,6.2 跨越基本塊的靜態(tài)指令調(diào)度,VLIW vs. 超標(biāo)量 在動態(tài)調(diào)度的超標(biāo)量處理器中，相關(guān)檢測和指令調(diào)度基本都由硬件完成。 在靜態(tài)調(diào)度的超標(biāo)量處理器中，部分相關(guān)檢測和指令調(diào)度工作交由編譯器完成。 在VLIW處理器中，相關(guān)檢測和指令調(diào)度工作全部由編譯器完成，它需要更“智能”的編譯器。,6.3 靜態(tài)多指令流出：VLIW技術(shù),,實例分析,6.3 靜態(tài)多指令流出VLIW技術(shù),例6.3 假設(shè)某VLIW處理器每個時鐘周期可以同時流出5個操作，

15、包括2個訪存操作，2個浮點(diǎn)操作以及1個整數(shù)或分支操作。將例6.1中的代碼循環(huán)展開，并調(diào)度到該VLIW處理器上執(zhí)行。循環(huán)展開次數(shù)不定，但至少要能夠保證消除所有流水線“空轉(zhuǎn)”周期，同時不考慮分支延遲。,解：循環(huán)被展開7次，經(jīng)調(diào)度后可以消除所有流水線“空轉(zhuǎn)”。在不考慮分支延遲的情況下，每執(zhí)行一個疊代需要9個時鐘周期，計算出7個結(jié)果，即平均每得到一個結(jié)果需要1.29個周期。 VLIW的不足： 編碼效率僅比50%略高一些 所需要的寄存器數(shù)量也大大增加,6.3 靜態(tài)多指令流出VLIW技術(shù),VLIW性能分析 VLIW目標(biāo)代碼編碼效率低 為消除流水線“空轉(zhuǎn)”需要增加循環(huán)展開的次數(shù) 很難從應(yīng)用程序中找到足夠多的

16、并行指令填滿VLIW指 令中的每一個slot VLIW流水線的互鎖機(jī)制 VLIW處理器中沒有實現(xiàn)任何相關(guān)檢測邏輯，而是靠互 鎖機(jī)制保證執(zhí)行結(jié)果的正確 這種簡單的互鎖機(jī)制將造成較大的開銷 目標(biāo)代碼兼容性差 二進(jìn)制翻譯,6.3 靜態(tài)多指令流出VLIW技術(shù),性能比較多流出處理器 vs. 向量處理器 即使對于一些結(jié)構(gòu)不規(guī)則的代碼，多流出處理器也能從中挖掘出一些指令級并行。 多流出處理器對存儲系統(tǒng)沒有過高的要求，價格較便宜、由Cache和主存構(gòu)成的多層次存儲子系統(tǒng)即可滿足其對性能的要求。,6.3 靜態(tài)多指令流出VLIW技術(shù),結(jié)論：多流出處理器已成為當(dāng)前實現(xiàn)指令級并行的主要選擇，而向量處理器則通常是作為

17、協(xié)處理器集成到計算機(jī)系統(tǒng)中，以加速特定類型的應(yīng)用程序。,超標(biāo)量和VLIW結(jié)構(gòu)都存在嚴(yán)重不足 超標(biāo)量硬件復(fù)雜度太高，8流出成為極限； VLIW存在代碼兼容問題，編譯器智能程度不夠。 EPIC技術(shù)在VLIW基礎(chǔ)上融合了超標(biāo)量的一些優(yōu)點(diǎn) 編譯器通過蹤跡調(diào)度、超塊調(diào)度等帶有極強(qiáng)猜測性的優(yōu)化 技術(shù)盡可能多地挖掘指令級并行。 流水線硬件則提供豐富的計算資源實現(xiàn)這些指令級并行， 并通過專門的機(jī)制確保在程序執(zhí)行過程中出現(xiàn)預(yù)測錯誤時 仍然能得到正確的運(yùn)行結(jié)果，盡量減少由此引起的額外開 銷。,6.4 顯示并行指令計算EPIC,,什么是EPIC？ 指令級并行主要由編譯器負(fù)責(zé)開發(fā)，處理器為保證代碼正 確執(zhí)行提供必要

18、的硬件支持，只有在這些硬件機(jī)制的輔助 下這些優(yōu)化技術(shù)才能高效完成。 系統(tǒng)結(jié)構(gòu)必須提供某種通信機(jī)制，使得流水線硬件能夠了 解編譯器“安排”好的指令執(zhí)行順序。 EPIC編譯器的高級優(yōu)化技術(shù) 非綁定分支 謂詞執(zhí)行 前瞻執(zhí)行,6.4 顯示并行指令計算EPIC,分支指令在傳統(tǒng)流水線上的執(zhí)行過程 計算分支轉(zhuǎn)移條件 生成分支目標(biāo)地址 取下一條指令 譯碼并流出下一條指令,6.4.1 非綁定分支,6.4 顯示并行指令計算EPIC,在傳統(tǒng)流水線上，分支指令都具有“原子性”，即上述各操作被綁定在一起，不能分開。,非綁定分支技術(shù) 核心思想：將分支指令劃分為多條粒度更小的指令，獨(dú)立執(zhí)行。 準(zhǔn)備操作：計算分支目標(biāo)地址 比

19、較操作：計算分支轉(zhuǎn)移條件 轉(zhuǎn)移操作：根據(jù)分支轉(zhuǎn)移條件是true還是false，改變控 制流或執(zhí)行順序的下一條指令。 運(yùn)行時，流水線硬件根據(jù)前兩個操作的結(jié)果，動態(tài)地將第三個操作轉(zhuǎn)換為空操作或無條件轉(zhuǎn)移。 前兩個操作應(yīng)盡早完成,6.4 顯示并行指令計算EPIC,條件執(zhí)行機(jī)制 條件執(zhí)行：指指令的執(zhí)行依賴于一定的條件，當(dāng)條件為真時指令將正常執(zhí)行，否則將什么也不做。 實例：條件傳輸指令 例6.4 在下面的語句中， if（A=0）S=T； 假設(shè)變量A、S、T的值分別保存在寄存器R1、R2和R3內(nèi)。請 用分支指令和條件傳輸指令編寫功能相同的匯編代碼。,6.4.2 謂詞執(zhí)行,6.4 顯示并行指令

20、計算EPIC,解：包含分支指令的MIPS匯編代碼如下： BNEZ R1，L ADDU R2，R3，R0 L： 而使用條件傳輸指令CMOVZ時的匯編代碼為： CMOVZ R2，R3，R1 指令CMOVZ有3個操作數(shù)，R2為目的操作數(shù)，R1和R3是源操作 數(shù)，執(zhí)行條件保存在寄存器R1中。 當(dāng)R1=0時，R3的值被復(fù)制到R2中，否則R2的內(nèi)容不變。,6.4 顯示并行指令計算EPIC,分析 條件傳輸指令將分支指令引起的控制相關(guān)轉(zhuǎn)換為相對于分支轉(zhuǎn)移條件（R1）的數(shù)據(jù)相關(guān)。 條件執(zhí)行機(jī)制能夠刪除代碼中那些行為難以預(yù)測的分支指令，提高分支預(yù)測準(zhǔn)確率，并減少由于分支預(yù)測錯誤帶來的性能損失。 無論指令的執(zhí)

21、行條件是否為真，指令都將被讀出、譯碼并執(zhí)行。 這種編譯優(yōu)化技術(shù)叫做條件轉(zhuǎn)換。,6.4 顯示并行指令計算EPIC,條件傳輸指令的應(yīng)用計算絕對值 求絕對值的運(yùn)算A = abs(B)，對應(yīng)的C語句為： if（B<0）A=-B; else A=B; 使用條件傳輸指令后，代碼段如下（假設(shè)變量A和B分別被保存在寄存器R1和R2中）： SUB R1，R0，R2 // A = -B SLT R3，R2，R0 // 若B<0，R3=1， // 否則R3=0 CMOVZ R1，R2，R3// R3=0時，A = B,6.4 顯示并行指令計算EPIC,謂詞執(zhí)行機(jī)制 條件傳輸指令的性能問題 隨著指令數(shù)的

22、增加，經(jīng)過條件轉(zhuǎn)換得到的條件傳輸指令和條件計算指令的數(shù)量也將增加，這會大大降低目標(biāo)代碼的效率。 謂詞執(zhí)行（predicated execution） 給指令集中的每條指令都增加一個執(zhí)行條件，這個執(zhí)行條件就叫做謂詞（predicate）。 若謂詞為真，指令正常執(zhí)行，否則什么也不做。,6.4 顯示并行指令計算EPIC,謂詞執(zhí)行機(jī)制實例分析,6.4 顯示并行指令計算EPIC,例6.5 假設(shè)在一個周期內(nèi)，某雙流出的超標(biāo)量處理器可以同時 執(zhí)行一個訪存操作和一個ALU操作，或者僅執(zhí)行一個分支操作。受 此限制，下面這段匯編代碼的執(zhí)行效率并不高，表現(xiàn)在： （1）第二個周期只能流出一條ALU指令，訪存單元空閑

23、； （2）當(dāng)分支轉(zhuǎn)移不成功時，BEQZ指令后的兩條LW指令之間存 在的數(shù)據(jù)相關(guān)將引起流水線暫停。 試通過謂詞執(zhí)行機(jī)制解決這兩個問題，減少此段代碼的執(zhí)行開銷。,例6.5的代碼段,6.4 顯示并行指令計算EPIC,解 我們用LWC表示帶謂詞的LW指令，并假設(shè)該指令的執(zhí)行條 件為謂詞不等于0。這樣，BEQZ后的第一條LW指令就可以被轉(zhuǎn)換 為LWC指令，并被調(diào)度到第二個周期執(zhí)行，如下所示：,6.4 顯示并行指令計算EPIC,分析 調(diào)度后代碼的執(zhí)行時間縮短了。 若分支轉(zhuǎn)移成功，LWC將被轉(zhuǎn)換為空操作，這不影響結(jié)果的正確性，但也不會縮短執(zhí)行時間。 周期4中的LW指令轉(zhuǎn)換為LWC，結(jié)果如何？,6.4 顯示

24、并行指令計算EPIC,謂詞執(zhí)行機(jī)制異常處理 謂詞執(zhí)行增加了異常處理的復(fù)雜度 例若LWC指令執(zhí)行時發(fā)生缺頁中斷，如何處理？ LWC的謂詞為true，中斷本應(yīng)發(fā)生； LWC的謂詞為false，中斷不應(yīng)發(fā)生。,6.4 顯示并行指令計算EPIC,如何將謂詞為假的指令轉(zhuǎn)換為空操作？ 兩種方法 流水線前端指令流出時 流水線后端結(jié)果確認(rèn)時 一般采用第二種方法 為什么？,6.4 顯示并行指令計算EPIC,概述 謂詞執(zhí)行與全局指令調(diào)度的不足之處 僅有少量結(jié)構(gòu)全面實現(xiàn)謂詞執(zhí)行 全局指令調(diào)度往往需要補(bǔ)償代碼 EPIC通過前瞻執(zhí)行提高猜測執(zhí)行的效果 什么是前瞻執(zhí)行？ 在數(shù)據(jù)相關(guān)或控制相關(guān)尚未消除時，將指令調(diào)度到相關(guān)

25、指令前猜測執(zhí)行。 通過硬件機(jī)制完成異常處理，確保正確性。,6.4.3 前瞻執(zhí)行,6.4 顯示并行指令計算EPIC,影響前瞻執(zhí)行效果的因素 編譯器能力的高低：能否準(zhǔn)確識別可以被前瞻執(zhí)行的指令。 異常處理機(jī)制：能否推遲處理由被前瞻執(zhí)行的指令引起的 異常，直到確定前瞻指令確實被執(zhí)行后。 如何避免前瞻引起的錯誤？,6.4 顯示并行指令計算EPIC,實例分析,6.4 顯示并行指令計算EPIC,例6.6 下面是一個if-then-else結(jié)構(gòu)的C程序段以及相應(yīng)的MIPS匯 編代碼段，其中變量A和B分別被保存在地址為0(R3)和0(R2)的存儲 單元中。若分支轉(zhuǎn)移不成功的概率很大，請利用前瞻執(zhí)行技術(shù)將第 二

26、條LD指令調(diào)度到分支指令BNEZ前執(zhí)行。假設(shè)寄存器R14空閑。,C語句： if （A0）A=A+4；else A=B； 匯編指令： LDR1，0（R3） // 取A BNEZR1，L1 //（A0）? LDR1，0（R2） // A=B（else部分） JL2 L1：DADDIR1，R1，#4 // A=A+4(then部分) L2：SDR1，0（R3） // 存A,6.4 顯示并行指令計算EPIC,解 調(diào)度結(jié)果如下： LDR1，0（R3）// 取A sLDR14，0（R2） // 取B，前瞻執(zhí)行 BEQZR1，L3 DADDI R14，R1，#4 // A=A+4 L3：SDR

27、14，0（R3） // A=B,6.4 顯示并行指令計算EPIC,前瞻執(zhí)行異常處理機(jī)制 問題：若執(zhí)行sLD時發(fā)生異常應(yīng)該如何處理？ 有四種方法 終止性異常 vs 可繼續(xù)異常 方法一： 立即處理 此前瞻指令引起的異常只是簡單地返回一個未定義值即可 ，而不是立即結(jié)束程序的運(yùn)行。 前瞻正確時，正在執(zhí)行的程序不會被終止，但它的執(zhí)行結(jié) 果肯定是錯誤的。 前瞻錯誤時，程序也將繼續(xù)執(zhí)行下去，只是處理該異常的 返回值不會被使用。,6.4 顯示并行指令計算EPIC,方法二：借助專門的檢測指令判斷是否需要處理 代碼實例 LDR1，0（R3） // 取A sLDR14，0（R2） // 取B，前瞻執(zhí)行 BEQ

28、ZR1，L1 SPECCK0（R2） // sLD是否產(chǎn)生異常 JL2 L1：DADDIR14，R1，#4 // A=A+4 L2：SDR14，0（R3） // A=B SPECCK的執(zhí)行條件與sLD指令相同（分支轉(zhuǎn)移失?。?基本思想：推遲處理由前瞻指令sLD引發(fā)的異常，直到已確定該指令確實應(yīng)該被執(zhí)行 。,6.4 顯示并行指令計算EPIC,方法三：借助寄存器狀態(tài)位判斷是否需要處理 為每個通用寄存器增加一個特殊的狀態(tài)標(biāo)志位：“poison”位 前瞻指令引發(fā)的可繼續(xù)異常都將被立即處理。 前瞻指令引發(fā)終止性異常時，其目的寄存器R的poison位將被置1，否則該位將被清0。 當(dāng)前瞻指令之后的另一

29、條指令訪問R時，若R的poison位為1將觸發(fā)一個終止性異常。 基本思想：將前瞻指令引起異常的處理推遲到另一條指令訪問前瞻指令的目的寄存器時。,6.4 顯示并行指令計算EPIC,方法四：借助再定序緩沖器完成 將指令的執(zhí)行結(jié)果保存在再定序緩沖器內(nèi)，并按指令流出 的順序依次確認(rèn)。 前瞻指令的確認(rèn)時機(jī)被推遲，直至能夠確定該指令的前瞻 執(zhí)行是正確（或錯誤）的。 除了需要再定序緩沖器等硬件機(jī)制的支持外，也需要在編 譯時標(biāo)出所有被前瞻的指令，以及這些指令所跨越的條件 分支。,6.4 顯示并行指令計算EPIC,數(shù)據(jù)前瞻 將load調(diào)度到store之前前瞻執(zhí)行最常見的數(shù)據(jù)前瞻 為保證正確性，編譯器總是會選擇

30、保守的調(diào)度方法，認(rèn)為相鄰的store與load間存在地址沖突，但在很多情況下，地址并不沖突。 盡早完成load指令有助于縮短關(guān)鍵路徑的長度。 硬件地址沖突檢測機(jī)制 當(dāng)load指令前瞻執(zhí)行時，流水線硬件會將它訪存的地址記錄在一個特殊的地址表中。,6.4 顯示并行指令計算EPIC,每執(zhí)行一條store指令，流水線硬件將該指令的訪存地址與地址表中的各有效項進(jìn)行匹配，命中則說明出現(xiàn)地址沖突，前瞻失敗。 若控制流抵達(dá)load指令原來所在的位置時未出現(xiàn)沖突（編譯時在此位置放置檢測指令），說明前瞻成功，流水線硬件從地址表中刪除對應(yīng)的項。,6.4 顯示并行指令計算EPIC,數(shù)據(jù)前瞻失敗時的處理 僅load指令

31、被前瞻執(zhí)行：由檢測指令重新執(zhí)行l(wèi)oad指令即可 數(shù)據(jù)相關(guān)于load的其他指令也被前瞻執(zhí)行：需要補(bǔ)償代碼,why？ 全局指令調(diào)度技術(shù)已經(jīng)能夠很好地處理由分支指令引起的控制相關(guān) 容易預(yù)測的前瞻執(zhí)行 不容易預(yù)測的謂詞執(zhí)行 指令間的數(shù)據(jù)相關(guān)對指令級并行開發(fā)的限制作用反而越來越大,6.5 開發(fā)更多的指令級并行,,循環(huán)攜帶相關(guān) 循環(huán)攜帶相關(guān)是指一個循環(huán)的某個疊代中的指令與其他疊代中的指令之間的數(shù)據(jù)相關(guān)。 例6.7 在下面的循環(huán)中， for（i=1；i<=100；i=i+1） Ai+1 = Ai + Ci； /* S1 */ Bi+1 = Bi + Ai+1； /* S2 */ 假設(shè)數(shù)組A、B

32、和C中所有元素的存儲地址都互不相同，請問語句 S1與S2之間存在哪些數(shù)據(jù)相關(guān)？,6.5.1 挖掘更多的循環(huán)級并行,6.5 開發(fā)更多的指令級并行,解 S1和S2之間存在兩種不同類型的數(shù)據(jù)相關(guān)： 循環(huán)攜帶RAW數(shù)據(jù)相關(guān)：相鄰連詞疊代的語句S1之間，相鄰 兩次疊代中的語句S2之間。 RAW數(shù)據(jù)相關(guān)：同一疊代內(nèi)的語句S2與S1之間。 分析: 循環(huán)攜帶相關(guān)迫使指令只能按照所在疊代的先后順序依 次執(zhí)行。 限制了同一疊代內(nèi)存在數(shù)據(jù)相關(guān)的各語句之間的相對順序。,6.5 開發(fā)更多的指令級并行,怎樣消除循環(huán)攜帶數(shù)據(jù)相關(guān)？ 例6.8 在下面的循環(huán)中，語句S1和S2之間存在哪些數(shù)據(jù)相關(guān)？ 該循環(huán)的各次疊代是否可

33、以并行執(zhí)行？如果不能，請修改其代碼， 使之可以并行。 for（i=1；i<=100；i=i+1） Ai = Ai + Bi；/* S1 */ Bi+1 = Ci + Di；/* S2 */ ,6.5 開發(fā)更多的指令級并行,解 第i次疊代中語句S1與第i-1次疊代中語句S2之間存在RAW類型 的循環(huán)攜帶數(shù)據(jù)相關(guān)，但它們之間沒有形成環(huán)(S2與上次疊代的S1不 相關(guān))。修改后代碼 A1 = A1 + B1； for（i=1；i<=99；i=i+1） Bi+1 = Ci + Di； /* 原S2 */ Ai+1 = Ai+1 + Bi+1； /* 原S1 */ B101 = C100 + D10

34、0；,6.5 開發(fā)更多的指令級并行,修改方法：將存在循環(huán)攜帶相關(guān)的各條指令放在同一個疊代中,復(fù)雜循環(huán)攜帶數(shù)據(jù)相關(guān)的處理 for（i=6；i<=100；i=i+1） Yi = Yi-5 + Yi； // 相關(guān)距離為5 for（i=2；i<=100；i=i+1） Yi = Yi-1 + Yi； // 相關(guān)距離為1,6.5 開發(fā)更多的指令級并行,編譯器必須檢測出這種遞歸關(guān)系 (1) 某些系統(tǒng)結(jié)構(gòu)（特別是向量計算機(jī)）為遞歸提供了專門的硬件支持 (2) 這樣的遞歸結(jié)構(gòu)中通常隱藏著大量的循環(huán)級并行,存儲別名分析 什么是存儲別名 一個元素可能同時擁有多個合法的地址表達(dá)式 Ai+5、Aj*2-6、Ak 數(shù)組是

35、仿射的 如果一個一維數(shù)組Am:n的下標(biāo)可以被表示為形如 ai+b的形式，那么就稱該數(shù)組是仿射的（affine）。 一個多維數(shù)組，如果它每一維的下標(biāo)都是仿射的，那 么它就是仿射的。,6.5 開發(fā)更多的指令級并行,GCD測試法 算法描述 如果GCD(c, a)可以整除(d-b)，那么有可能存在存儲別名。 如果GCD測試的結(jié)果為假（不能整除），那么一定沒有存儲別名存在。 例6.9 使用GCD測試方法判斷下面的循環(huán)中是否存在存儲別名。 for（i=1；i<=100；i=i+1） x2*i+3 = x2*i * 5.0； 解 在這個循環(huán)中，a=2，b=3，c=2，d=0， 那么GCD(

36、a, c)=2，而d-b=-3。 由于2不能整除-3，因此沒有存儲別名，即無論i取何值，x2*i+3 與x2*i都將表示數(shù)組x的不同元素。,6.5 開發(fā)更多的指令級并行,數(shù)據(jù)相關(guān)分析 除了檢測指令之間是否存在數(shù)據(jù)相關(guān)外，編譯器還會將識別出的數(shù)據(jù)相關(guān)進(jìn)一步細(xì)分為真數(shù)據(jù)相關(guān)、輸出相關(guān)和反相關(guān)等不同類型，以便利用不同的優(yōu)化技術(shù)消除這些相關(guān)。 常用的優(yōu)化有重命名、值傳播、高度消減等。,6.5 開發(fā)更多的指令級并行,重命名優(yōu)化實例 例6.10 找出下面循環(huán)中的所有數(shù)據(jù)相關(guān)，指出它們究竟是真數(shù)據(jù) 相關(guān)、輸出相關(guān)、還是反相關(guān)，并利用重命名技術(shù)消除其中的輸出 相關(guān)和反相關(guān)。 for（i=1；i<=100；

37、i=i+1） Yi = Xi / a；/* S1 */ Xi = Xi + a； /* S2 */ Zi = Yi + a； /* S3 */ Yi = a Yi；/* S4 */ ,6.5 開發(fā)更多的指令級并行,解 這4條語句中存在以下相關(guān)： 1. S3與S1和S4與S1之間分別存在真數(shù)據(jù)相關(guān)。 2. S2和S1之間存在反相關(guān)。 3. S3和S4之間存在反相關(guān)。 4. S1和S4之間存在輸出相關(guān)。 for（i=1；i<=100；i=i+1） Yi = Xi / a；/* S1 */ Xi = Xi + a； /* S2 */ Zi = Yi + a； /* S3 */

38、 Yi = a Yi；/* S4 */ ,6.5 開發(fā)更多的指令級并行,將原代碼變換為下面的形式，可以消除所有輸出相關(guān)和反相關(guān)。 for（i=1；i<=100；i=i+1） /* 將數(shù)組Y重命名為T以消除輸出相關(guān) */ Ti = Xi / c； /* 將數(shù)組X重命名為X1以消除反相關(guān) */ X1i = Xi + c； /* 將Y重命名為T以消除反相關(guān) */ Zi = Ti + c； Yi = c Ti； ,6.5 開發(fā)更多的指令級并行,值傳播優(yōu)化實例 優(yōu)化前代碼 DADDUIR1，R2，#4 DADDUIR1，R1，#4 優(yōu)化后代碼 DADDUIR1，R2，#8 值傳播優(yōu)化通過將變量替換為

39、已知的值或表達(dá)式以達(dá)到消除數(shù)據(jù)相關(guān),6.5 開發(fā)更多的指令級并行,高度消減優(yōu)化實例 目的：縮短數(shù)據(jù)流圖中關(guān)鍵路徑的長度 優(yōu)化前代碼I ADDR1，R2，R3/* I1 */ ADDR4，R1，R6/* I2 */ ADDR8，R4，R7/* I3 */ 優(yōu)化后代碼I ADDR1，R2，R3 ADDR4，R6，R7 ADDR8，R1，R4,6.5 開發(fā)更多的指令級并行,高度消減優(yōu)化實例 優(yōu)化前代碼II sum = sum + Xi； sum = sum + Xi+1； sum = sum + Xi+2； sum = sum + Xi+3； sum = sum + Xi+4； 優(yōu)化后代碼II su

40、m = sum + Xi； t1 = Xi+1 + Xi+2； t2 = Xi+3 + Xi+4； t1 = t1 + t2； sum = sum + t1；,6.5 開發(fā)更多的指令級并行,關(guān)鍵路徑長度為5,關(guān)鍵路徑長度為3,,簡介 軟流水技術(shù)的核心思想是從循環(huán)不同的疊代中抽取一部分指令（循環(huán)控制指令除外）拼成一個新的循環(huán)疊代。 目的 將同一疊代中的相關(guān)指令分布到不同的疊代中 將不同疊代中的相關(guān)指令封裝到同一疊代中,6.5.2 軟流水,實例分析 例6.11 試用軟流水技術(shù)處理例6.1中的循環(huán)，假設(shè)數(shù)組x有n個元素。 解 軟流水需要從原循環(huán)的多個疊代中選擇指令拼成新的循環(huán)，因此 我們首先將原循環(huán)

41、展開。 疊代i：；修改xi并保存 L.DF0，0（R1） ADD.DF4，F(xiàn)0，F(xiàn)2 S.DF4，0（R1） 疊代i+1：；修改xi-1并保存 L.DF0，0（R1） ADD.DF4，F(xiàn)0，F(xiàn)2 S.DF4，0（R1） 疊代i+2：；修改xi-2并保存 L.DF0，0（R1） ADD.DF4，F(xiàn)0，F(xiàn)2 S.DF4，0（R1）,,從這3個疊代中分別選出一條指令，與原有的循環(huán)控制指令拼在一起得到一個新的疊代。 DADDUIR1，R1，#-16// I1：R1保存xn-2的地址 L.DF0，16（R1）// I2：取xn ADD.DF4，F(xiàn)0，F(xiàn)2// I3：xn = xn + F2 L.DF0，

42、8（R1）// I4：取xn-1 Loop：S.DF4，16（R1）// I5：存xi+2 ADD.DF4，F(xiàn)0，F(xiàn)2// I6：xi+1 = xi+1 + F2 L.DF0，0（R1）// I7：取xi BNER1，R2，Loop// I8 DADDUIR1，R1，#-8// I9：填充分支延遲槽 S.DF0，8（R1）// I10：存x2 ADD.DF4，F(xiàn)0，F(xiàn)2 // I11：x1 = x1 + F2 S.DF4，0（R1）// I12：存x1,6.5 開發(fā)更多的指令級并行,,分析： 新循環(huán)的結(jié)束條件仍為：R1=R2 新循環(huán)從元素xn-2開始從頭處理的，元素xn與xn-1 只是從半途

43、開始處理。 新循環(huán)的最后一次疊代只處理完元素x3，x2剛被修 改完結(jié)果尚未寫回，x1 剛被取出，需要被修改并寫回。 新循環(huán)的每個疊代相當(dāng)于流水執(zhí)行了原循環(huán)的3個疊代。 元素xn/n-1/2/1的處理相當(dāng)于充滿和排空這條“流水 線”。,6.5 開發(fā)更多的指令級并行,性能比較：軟流水 vs. 循環(huán)展開 循環(huán)展開主要減少由分支指令和修改循環(huán)索引變量的指令所引起的循環(huán)控制開銷。 軟流水使疊代內(nèi)的指令級并行達(dá)到最大。,6.5 開發(fā)更多的指令級并行,,IA-64簡介 IA-64是Intel與HP合作研制出的64位EPIC體系結(jié)構(gòu)，其設(shè)計遵循以下原則： 按照EPIC的思想開發(fā)指令級并行； 提供大量的硬件資源

44、實現(xiàn)指令級并行； 提供一系列輔助軟件指令級并行開發(fā)技術(shù)的硬件機(jī)制。,6.6 實例：IA-64體系結(jié)構(gòu),,Intel IA-64產(chǎn)品Itanium 主頻：800MHz 采用3級Cache 第一級為分離的指令和數(shù)據(jù)Cache 后兩級為混合Cache 第三級Cache（在片外） 流水線共分為10級，其中實現(xiàn)了一些基于硬件的動態(tài)指令調(diào)度機(jī)制，如分支預(yù)測、重命名、記分牌等。 提供了豐富的功能單元，所有的功能單元都是流水的。 每個周期最多流出6條指令，最多可同時執(zhí)行3條分支指令和2個訪存操作，提高了分支處理和存儲訪問的能力。,6.6 實例：IA-64體系結(jié)構(gòu),,,整數(shù)性能(SPECint 2000) 主頻

45、為800MHz的Itanium性能僅為2GHz主頻Pentium 4的 60%，1GHz主頻Alpha 21264的68%。 Alpha 21264主頻的功耗比Itanium低20%。 浮點(diǎn)性能(SPECfp 2000) 800MHz Itanium的性能是2GHz Pentium 4的1.04倍，是 1GHz Alpha 21264的1.20倍。 Intel IA-64產(chǎn)品Itanium 2 其性能在不經(jīng)過任何調(diào)試和優(yōu)化的條件下比Itanium提高50%到100%。,6.6 實例：IA-64體系結(jié)構(gòu),,6.6 實例：IA-64體系結(jié)構(gòu),,,IA-64功能單元和操作的類型,6.6.1 IA-

46、64指令格式,IA-64的目標(biāo)代碼被劃分為多個指令組，并按照流出的時間順序依次排列，編譯器指出組邊界。 IA-64的指令被稱為“bundle”，長128位，包含123位操作信息（3個操作41位/操作=123位）和5位模板信息。 模板位的作用 簡化譯碼，模板信息指明了bundle中3個操作的類型以及 它們分別需要在哪類功能單元上執(zhí)行。 顯式指出指令組邊界，模板中定義了停止位。,6.6 實例：IA-64體系結(jié)構(gòu),,,6.6 實例：IA-64體系結(jié)構(gòu),IA-64模板值及其含義,例6.12 將例6.1中的代碼展開7次并生成IA-64指令，使得： (1) bundle數(shù)最少； (2) 執(zhí)行時間最

47、短。 假設(shè)每時鐘周期可流出1個bundle，bundle中任何操作的暫停將導(dǎo) 致整個流水線暫停。各操作延遲如表6.1所示。 解 調(diào)度結(jié)果中“s”表示停止位，nop表示空操作。 第一種情況下只有9個bundle，15%的槽為空，但需要21個周期才能完成。 第二種情況代碼體積和空槽均有所增加，需要11個bundle，有30%的槽是空槽，但執(zhí)行時間大大縮短，僅用12個周期就可以完成 。,6.6 實例：IA-64體系結(jié)構(gòu),,解 (1) bundle最少,6.6 實例：IA-64體系結(jié)構(gòu),,(2) 執(zhí)行時間最短,6.6 實例：IA-64體系結(jié)構(gòu),,6.6.2 IA-64的謂詞執(zhí)行機(jī)制 IA-64提供

48、的硬件支持 設(shè)置了大量的謂詞寄存器（64個），每個謂詞寄存器的寬 度都是1位。 所有類型的IA-64操作都可以按照謂詞執(zhí)行方式執(zhí)行，每 個操作41位編碼的最低6位指明了保存執(zhí)行條件的謂詞寄 存器。 增強(qiáng)了比較（compare）操作和測試（test）操作的功 能，都可以同時修改多個謂詞寄存器。,6.6 實例：IA-64體系結(jié)構(gòu),,IA-64所支持的不同比較模式,6.6 實例：IA-64體系結(jié)構(gòu),例6.13 將下面的C語句轉(zhuǎn)換為IA-64匯編指令，使其執(zhí)行時間最短。 if （r1==1 || r2==2 || r3==3 || r4==4）s； 解 對應(yīng)的IA-64匯編代碼如下。 IA-64

49、cmp指令的格式為：cmp.op.mod p, q = r1, r2 這里op為要進(jìn)行的比較操作，mod為上表所示的比較模式中的一 種，p，q為兩個目的謂詞寄存器，r1和r2為要比較的操作數(shù)，可以是 寄存器名，也可以是立即數(shù)。 cmp.ne p1, p0 = r0, r0 ；； cmp.eq.or p1, p0 = 1, r1 cmp.eq.or p1, p0 = 2, r2 cmp.eq.or p1, p0 = 3, r3 cmp.eq.or p1, p0 = 4, r4；； （p1）s,6.6 實例：IA-64體系結(jié)構(gòu),,6.6.3 IA-64的前瞻執(zhí)行機(jī)制 為了標(biāo)識被前瞻執(zhí)行的load指令并檢測前瞻是否成功，IA-64專門設(shè)置了3條指令。 ld.a：表示被前瞻執(zhí)行的load指令 ld.c：編譯器將ld.c指令放在被前瞻執(zhí)行的load指令最初所 在的位置，ld.c執(zhí)行則前瞻成功 chk.a：編譯器將它放在與ld.c相同的位置。若執(zhí)行chk.a時 發(fā)現(xiàn)對應(yīng)的load前瞻執(zhí)行失敗，它會將控制流轉(zhuǎn)移到一段補(bǔ)償代碼中，重新執(zhí)行。 前瞻l(fā)oad指令的地址被記錄在ALAT表中 每個寄存器有一個狀態(tài)位NaT(Not A Thing),6.6 實例：IA-64體系結(jié)構(gòu),,