依賴于機(jī)器的優(yōu)化課件

1、第十章 依賴于機(jī)器的優(yōu)化在指令級并行的機(jī)器上，程序的運(yùn)行速度依賴于下面幾個(gè)因素 程序中潛在的并行 處理器上可用的并行 從串行程序提取并行的能力 在給定的調(diào)度約束下發(fā)現(xiàn)最佳并行調(diào)度的能力并行的提取和并行執(zhí)行的調(diào)度都可以靜態(tài)地在軟件中或動態(tài)地在硬件中完成第十章 依賴于機(jī)器的優(yōu)化本章內(nèi)容 使用指令級并行的基礎(chǔ)問題 提取并行的數(shù)據(jù)相關(guān)性分析 代碼調(diào)度的基本概念 基本塊調(diào)度的技術(shù)、發(fā)現(xiàn)通用程序中的高度數(shù)據(jù)相關(guān)控制流的方法、調(diào)度數(shù)值程序的軟件流水線技術(shù) 在多處理器系統(tǒng)上，使用數(shù)組的計(jì)算密集型程序的并行化和數(shù)據(jù)局部性優(yōu)化的概念和方法10.1 處理器體系結(jié)構(gòu)在考慮指令級并行時(shí)，通常想象成一個(gè)處理器在單個(gè)時(shí)鐘周

2、期內(nèi)發(fā)射幾個(gè)操作事實(shí)上，在每周期內(nèi)發(fā)射一個(gè)操作是可能的, 而指令級并行的獲得是通過使用流水線技術(shù)本節(jié)先解釋流水線，然后討論多指令發(fā)射10.1 處理器體系結(jié)構(gòu)10.1.1 指令流水線和分支延遲 ii + 1i + 2i + 3i + 41. IF2. IDIF3. EXIDIF4. MEMEXIDIF5. WBMEMEXIDIF6.WBMEMEXID7.WBMEMEX8.WBMEM9.WB取指令I(lǐng)F, 譯碼ID, 執(zhí)行操作EX, 訪問內(nèi)存MEM, 回寫結(jié)果WB5級指令流水線中的5條連續(xù)指令 10.1 處理器體系結(jié)構(gòu)10.1.1 指令流水線和分支延遲分支延遲發(fā)現(xiàn)應(yīng)該執(zhí)行一個(gè)分支而不是直接后繼轉(zhuǎn)向一

3、個(gè)分支時(shí)會引起取分支目的地址指令的延遲并引起指令流水線“打嗝”可以通過使用硬件，根據(jù)分支的執(zhí)行歷史來預(yù)測分支結(jié)果并從預(yù)測的目的地址預(yù)取指令分支延遲不可避免，因?yàn)榉种ьA(yù)測會發(fā)生偏差10.1 處理器體系結(jié)構(gòu)10.1.2 流水化的執(zhí)行如果不依賴一條指令結(jié)果的隨后指令在該結(jié)果產(chǎn)生前就被允許執(zhí)行有些指令的執(zhí)行需要幾個(gè)周期，幾個(gè)操作同時(shí)出現(xiàn)在它們的執(zhí)行級上可能的如果最長的執(zhí)行流水線是n級，n個(gè)操作同時(shí)進(jìn)行的可能性是存在的并非所有的指令都能被完全流水化，例如浮點(diǎn)除 通用處理器大都動態(tài)察覺相繼指令之間的依賴性 嵌入式系統(tǒng)把數(shù)據(jù)相關(guān)性的檢查交給軟件10.1 處理器體系結(jié)構(gòu)10.1.3 多指令發(fā)射 每周期發(fā)射幾個(gè)

4、操作，讓更多操作同時(shí)進(jìn)行超長指令字機(jī)器將若干個(gè)操作編碼在單周期中發(fā)射編譯器需要確定哪些操作可以并行發(fā)射超標(biāo)量機(jī)器超標(biāo)量機(jī)器有按普通順序執(zhí)行語義的正規(guī)指令集硬件自動察覺指令之間的相關(guān)性，并且在它們的操作數(shù)可用時(shí)就發(fā)射它們更復(fù)雜的調(diào)度器能夠“亂序”執(zhí)行指令10.2 代碼調(diào)度的約束 代碼調(diào)度用在代碼生成器產(chǎn)生的機(jī)器代碼上的優(yōu)化技術(shù)本節(jié)討論代碼調(diào)度的約束控制相關(guān)約束 在原程序中執(zhí)行的所有操作都必須在優(yōu)化代碼中執(zhí)行數(shù)據(jù)相關(guān)約束 優(yōu)化程序中的操作產(chǎn)生的結(jié)果必須同原程序?qū)?yīng)操作的結(jié)果一樣資源約束 調(diào)度不能過分占用機(jī)器的資源優(yōu)化程序很難調(diào)試內(nèi)存狀態(tài)可能和順序執(zhí)行的任何內(nèi)存狀態(tài)不匹配10.2 代碼調(diào)度的約束 1

5、0.2.1 數(shù)據(jù)相關(guān)真相關(guān) 如果對同一個(gè)單元先寫后讀，那么讀依賴于所寫的值反相關(guān) 如果對同一個(gè)單元先讀后寫?？梢酝ㄟ^把值存在不同的單元來刪除反相關(guān)輸出相關(guān) 如果對同一個(gè)單元先后寫兩次。也可刪除數(shù)據(jù)相關(guān)概念可同時(shí)用于內(nèi)存訪問和寄存器訪問10.2 代碼調(diào)度的約束 10.2.2 發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性例(1) a = 1(2) p = 2(3) x = a語句(1)和(2)可能構(gòu)成輸出相關(guān)語句(1)和(3)可能構(gòu)成真相關(guān)語句(2)和(3)可能構(gòu)成真相關(guān)除非編譯器知道p不可能指向a，否則3個(gè)操作必須串行執(zhí)行10.2 代碼調(diào)度的約束 10.2.2 發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性發(fā)現(xiàn)數(shù)據(jù)相關(guān)需要不同形式的分析數(shù)組

6、元素間的別名分析Ai和Aj是否互為別名指針別名分析若p和q相等，則p和q、p-next和q-next、p-data和q-data等都分別互為別名過程間分析引用調(diào)用場合：形參和形參之間、形參和全局變量之間因?qū)崊⒍鸹閯e名10.2 代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷例：(a + b) + c + (d + e)LD R1, aLD R2, bADD R1, R1, R2LD R2, cADD R1, R1, R2LD R2, dLD R3, eADD R2, R2, R3ADD R1, R1, R2+e+c+ab+d若瞄準(zhǔn)極小化寄存器的使用個(gè)數(shù)，則只需使用3個(gè)寄存器

7、10.2 代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷例：(a + b) + c + (d + e)LD R1, aLD R2, bADD R1, R1, R2LD R2, cADD R1, R1, R2LD R2, dLD R3, eADD R2, R2, R3ADD R1, R1, R2+e+c+ab+d完成整個(gè)計(jì)算需要7步10.2 代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷例：(a + b) + c + (d + e)+e+c+ab+d如果對每個(gè)中間結(jié)果使用不同寄存器，則完成計(jì)算只需要4步R1 = aR6 = R1+R2R8 = R6+R3R9 = R8

8、+R7R2 = bR7 = R4+R5R3 = cR4 = dR5 = e10.2 代碼調(diào)度的約束 10.2.4 寄存器分配和代碼調(diào)度的次序安排先寄存器分配結(jié)果代碼中會有很多存儲相關(guān)非數(shù)值應(yīng)用本質(zhì)上沒有多少并行，采用這種方式先代碼調(diào)度導(dǎo)致寄存器溢出，抵消指令級并行的優(yōu)點(diǎn)適用于有許多大表達(dá)式的數(shù)值應(yīng)用在假定偽寄存器就是物理寄存器情況下，先調(diào)度指令，然后寄存器分配，把處理寄存器溢出的代碼附加在必要的地方，并再次進(jìn)行代碼調(diào)度10.2 代碼調(diào)度的約束 10.2.5 控制相關(guān) 在非數(shù)值計(jì)算中，基本塊非常小，其中的操作通常高度相關(guān)，幾乎不能并行調(diào)查跨基本塊的并行是至關(guān)重要的若一條指令很可能被執(zhí)行且有空閑的

9、資源可“免費(fèi)”用于完成該指令的操作，則可以投機(jī)地執(zhí)行該指令；若投機(jī)成功，則程序運(yùn)行得快一些例if (a t) b = a a依賴于比較a t的結(jié)果 b = a a; 若a a不會產(chǎn)生副作用，則d = a + c; a a可以投機(jī)地執(zhí)行10.2 代碼調(diào)度的約束 10.2.6 投機(jī)執(zhí)行的支持內(nèi)存讀取是一類使用頻繁，且能從投機(jī)執(zhí)行大大獲益的指令但在 if (p != null)q = p中，投機(jī)地對p脫引用將引起該程序因p等于null而錯(cuò)誤地停止許多高性能處理器提供專門的特性來支持投機(jī)地內(nèi)存訪問10.2 代碼調(diào)度的約束 10.2.6 投機(jī)執(zhí)行的支持預(yù)取指令在數(shù)據(jù)使用前將其從內(nèi)存取到緩存,若該單元無效

10、或訪問它會引起缺頁，則忽略 抑制位允許投機(jī)地從內(nèi)存將數(shù)據(jù)讀取到寄存器堆，若出現(xiàn)非法內(nèi)存訪問或缺頁，則設(shè)置目標(biāo)寄存器的抑制位判定指令在判定條件為真時(shí)才執(zhí)行的指令例 if (a = 0)翻譯成 ADD R3, R4, R5b = c + d; CMOVZ R2, R3, R1假定a、b、c和d分別被分配了R1、R2、R4和R5可用來將相鄰基本塊組合成一個(gè)更大基本塊10.2 代碼調(diào)度的約束 10.2.7 一個(gè)基本的機(jī)器模型機(jī)器模型M = (R, T)T：操作類型集，如讀取、存儲和算術(shù)運(yùn)算等R = r1, r2, ：硬件資源向量集，如內(nèi)存訪問部件、算術(shù)運(yùn)算部件和浮點(diǎn)功能部件ri代表第i類資源中可用的部

11、件數(shù)每個(gè)操作有一組輸入操作數(shù)、一組輸出操作數(shù)和一個(gè)資源需求和每個(gè)輸入操作數(shù)相關(guān)的是一個(gè)輸入延遲和每個(gè)輸出操作數(shù)相關(guān)的是一個(gè)輸出延遲10.2 代碼調(diào)度的約束 10.2.7 一個(gè)基本的機(jī)器模型機(jī)器模型M = (R, T)對每種操作類型t，資源使用由一張二維資源預(yù)留表RTt來建模條目RTti, j是t類型的一個(gè)操作在它被發(fā)射i時(shí)鐘周期后，使用第j種資源的部件數(shù)對任何t、i和j，RTti, j必須小于或等于Rj10.3 基 本 塊 調(diào) 度10.3.1 數(shù)據(jù)依賴圖基本塊由數(shù)據(jù)依賴圖G = (N, E)來表示結(jié)點(diǎn)集合N表示該塊的機(jī)器指令中的操作集合有向邊集合E表示這些操作之間的數(shù)據(jù)相關(guān)約束G的結(jié)點(diǎn)集N和邊

12、集E按如下兩步構(gòu)造N中的每個(gè)操作n有一張資源預(yù)留表RTn，其值直接就是n的操作類型的資源預(yù)留表每條邊e都標(biāo)示有延遲de，表示e的目的結(jié)點(diǎn)必須在它源結(jié)點(diǎn)發(fā)射de個(gè)時(shí)鐘周期之后才可以發(fā)射10.3 基 本 塊 調(diào) 度數(shù)據(jù)依賴圖資源預(yù)留表alu menLD R2, 0(R1)ST 4(R1), R2 LD R3, 8(R1)ADD R3, R3, R2ADD R3, R3, R4ST 0(R7), R7 ST 12(R1), R3 222111111i1i2i3i4i5i6i7灰色表示1 白色表示0操作是全流水的，只需顯示在第1行使用的資源 10.3 基 本 塊 調(diào) 度10.3.2 基本塊的表調(diào)度關(guān)鍵

13、路徑包括最后5個(gè)結(jié)點(diǎn)，故第3條指令先調(diào)度再調(diào)度第1條指令，因?yàn)榈?條指令還需等1周期第4周期調(diào)度2條資源預(yù)留表alu men調(diào)度表LD R3, 8(R1) ADD R3, R3, R2ADD R3, R3, R4ST 0(R7), R7ST 12(R1), R3ST 4(R1), R2 LD R2, 0(R1) 10.3 基 本 塊 調(diào) 度10.3.2 基本塊的表調(diào)度根據(jù)每個(gè)結(jié)點(diǎn)同先前已經(jīng)被調(diào)度的各結(jié)點(diǎn)之間的數(shù)據(jù)相關(guān)約束，來計(jì)算一個(gè)結(jié)點(diǎn)可以執(zhí)行的最早時(shí)間槽這個(gè)結(jié)點(diǎn)所需資源根據(jù)一張資源預(yù)留表來進(jìn)行檢查，該資源預(yù)留表收集了所有到目前為止被占用資源。這個(gè)結(jié)點(diǎn)的調(diào)度按有足夠資源的最早時(shí)間槽來安排10.

14、4 全局代碼調(diào)度對于有適度指令級并行的機(jī)器，僅對每個(gè)基本塊進(jìn)行緊湊調(diào)度會引起許多資源空閑全局調(diào)度：為了更好地利用機(jī)器資源，需要考慮把指令從一個(gè)基本塊移到另一個(gè)基本塊的代碼生成策略必須保證原來程序中所有指令在優(yōu)化程序中都被執(zhí)行當(dāng)優(yōu)化程序可以投機(jī)地執(zhí)行額外指令時(shí)，這些指令肯定不能有任何多余的副作用10.4 全局代碼調(diào)度10.4.1 簡單的代碼移動先用例子展示操作在基本塊之間移動涉及的問題 L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調(diào)度的機(jī)器代碼LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R

15、7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度假定a, b, c, d和e的地址不同，分別保存在R1到R5由于數(shù)據(jù)相關(guān)，塊內(nèi)的指令必須串行執(zhí)行，且插入 NOPL:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調(diào)度的機(jī)器代碼LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度假定機(jī)器在一個(gè)時(shí)鐘周期執(zhí)

16、行任意的兩個(gè)操作讀取操作有2周期的延遲，其他指令1周期的延遲L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調(diào)度的機(jī)器代碼LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)行B2的讀取操作在執(zhí)行B1時(shí)投機(jī)地完成B2的存儲操作放到B3的一份拷貝中L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調(diào)

17、度的機(jī)器代碼LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度L:全局調(diào)度前后的流圖if (a = 0) goto Lc = be = d + d(a) 源代碼ST 0(R5), R8(b) 局部調(diào)度的機(jī)器代碼LD R6, 0(R1), LD R8, 0(R4) LD R7, 0(R2)ADD R8, R8, R8, BEQZ R6, LST 0(R5), R8, ST 0(R3), R7L:(c) 全局調(diào)度的機(jī)器

18、代碼B1B3B3LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度基本塊之間的支配關(guān)系指令在基本塊之間的移動因支配關(guān)系不同而不同B1和B3控制等價(jià)：B1支配B3，B3后支配B1B1支配B2，但是B2并非后支配B1B2不支配B3，但是B3后支配B2LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8S

19、T 0(R5), R8B2B1B3L:10.4 全局代碼調(diào)度10.4.2 向上的代碼移動從塊src向上移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次dstsrc10.4 全局代碼調(diào)度10.4.2 向上的代碼移動從塊src向上移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次若src未后支配dst，被移動操作可利用空閑資源免費(fèi)執(zhí)行，在控制流到達(dá)src時(shí)獲益dstsrc10.4 全局代碼調(diào)度10.4.2

20、向上的代碼移動從塊src向上移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次若src未后支配dst，被移動操作可利用空閑資源免費(fèi)執(zhí)行，在控制流到達(dá)src時(shí)獲益若dst不支配src，需要插入被移動操作的拷貝 dstsrc10.4 全局代碼調(diào)度10.4.3 向下的代碼移動從塊src向下移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次srcdst10.4 全局代碼調(diào)度10.4.3 向下的代碼移動從塊src向

21、下移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次src未后支配dst, 向下移動的代碼經(jīng)常是存儲操作, 復(fù)制從src到dst路徑上的各塊，并把被移動操作僅放置在dst的新拷貝中srcdst10.4 全局代碼調(diào)度9.5節(jié)的例子可作為參考B1B2B3B4a = b + cB5B6B7d = b + cB1B2B3B4t = b + ca = tB4B5d = td = b + cB6B6B710.4 全局代碼調(diào)度10.4.3 向下的代碼移動從塊src向下移動到塊dst，假定移動未違反數(shù)據(jù)相關(guān)，并使得

22、通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次src未后支配dst, 向下移動的代碼經(jīng)常是存儲操作, 復(fù)制從src到dst路徑上的各塊，并把被移動操作僅放置在dst的新拷貝中 dst沒有后支配src，插入補(bǔ)償代碼以保證被移動操作在不經(jīng)dst路徑上也執(zhí)行srcdst10.4 全局代碼調(diào)度10.4.4 更新數(shù)據(jù)相關(guān)代碼移動會改變操作之間的數(shù)據(jù)相關(guān)關(guān)系兩個(gè)對x的賦值之一可以移動到最上面的基本塊，該變換能維持原來程序中的所有相關(guān)性一旦一個(gè)對x的賦值被上移，另一個(gè)就不能移動了移動使得x在最上面塊的出口由不活躍變成活躍一個(gè)變量在某個(gè)程序點(diǎn)活躍，則就不能

23、把對它的投機(jī)定值移到該點(diǎn)的上面x = 1x = 210.4 全局代碼調(diào)度10.4.5 全局調(diào)度的其他問題 程序調(diào)度應(yīng)該使經(jīng)常執(zhí)行的路徑運(yùn)行得快一些，不經(jīng)常執(zhí)行的路徑可能會因調(diào)度變得慢一些 編譯器可用來估計(jì)執(zhí)行頻率的技術(shù)有若干種(1) 內(nèi)循環(huán)比外循環(huán)執(zhí)行得更頻繁(2) 分支指令往回跳轉(zhuǎn)比不跳轉(zhuǎn)要更經(jīng)常(3)看守程序出口或異常處理例程的分支語句很少被執(zhí)行最好的頻率估計(jì)來自動態(tài)剖析，程序被靜態(tài)插樁以用來運(yùn)行時(shí)記錄條件分支每次的走向10.4 全局代碼調(diào)度10.4.5 全局調(diào)度的其他問題 最簡單的全局調(diào)度算法也相當(dāng)復(fù)雜，不介紹 在一些全局調(diào)度算法中，循環(huán)迭代的邊界是代碼移動的一種屏障，需循環(huán)展開for(

24、i = 0; i N; i +) for ( i = 0; i + 4 N; i += 4) S(i);S(i); S(i +1);S(i +2); S(i +3); for ( ; i N; i +) S(i); 10.4 全局代碼調(diào)度10.4.6 靜態(tài)調(diào)度器和動態(tài)調(diào)度器的相互影響動態(tài)調(diào)度器的優(yōu)點(diǎn)是可以根據(jù)運(yùn)行時(shí)的情況建立新的調(diào)度表，無需事先編碼所有可能的調(diào)度表10.4 全局代碼調(diào)度10.4.6 靜態(tài)調(diào)度器和動態(tài)調(diào)度器的相互影響存在動態(tài)調(diào)度情況下，靜態(tài)調(diào)度器的作用保證盡早地取高延遲的指令，使得動態(tài)調(diào)度器能夠盡早發(fā)射它們盡早安排預(yù)取指令，使數(shù)據(jù)到要用時(shí)已經(jīng)在緩存, 或盡早安排可能不命中緩存的操

25、作只需要給數(shù)據(jù)相關(guān)的操作安排正確的次序，無需通過極小化延遲來分離每一對數(shù)據(jù)相關(guān)的操作給分支預(yù)測指令較高優(yōu)先級，以減少預(yù)測錯(cuò)誤的代價(jià)10.5 軟 件 流 水 10.5.1 引言軟件流水是一種調(diào)度算法，它每次調(diào)度一個(gè)完整的循環(huán)，以充分利用穿越迭代的并行性單次迭代的操作中幾乎沒有什么并行性軟件流水技術(shù)不斷地重疊一些相繼迭代，直到所有迭代都填入流水線為止能產(chǎn)生高效和緊湊的代碼以一周期內(nèi)可以同時(shí)發(fā)射一個(gè)讀取、一個(gè)存儲、一個(gè)算術(shù)運(yùn)算（全流水）和一個(gè)分支操作的機(jī)器來舉例10.5 軟 件 流 水 每次調(diào)度一個(gè)迭代的結(jié)果見右邊f(xié)or (i = 0; i n; i +) / R1, R2, R3 = &A, &B

26、, &D Di = Ai Bi + c; / R4= c / R10= n 1 L: LD R5, 0(R1+) LD R6, 0(R2+) MUL R7, R5, R6 NOP ADD R8, R7, R4 NOP ST 0(R3+),R8, BL R10, L 該計(jì)算大部分是串行的，它需要7周期，只有循環(huán)回跳指令和迭代中最后一條指令重疊 10.5 軟 件 流 水 循環(huán)展開4次迭代的調(diào)度結(jié)果見右邊f(xié)or (i = 0; i = 5)N2 = 1 + 2 (N 1) / 2);elseN2 = 0;for (i = 0; i N2; i +)/ 該循環(huán)被流水化Di = Ai Bi + c;fo

27、r (i = N2; i N; i +)/ 不需要優(yōu)化Di = Ai Bi + c;10.5 軟 件 流 水 10.5.4 Do-Across循環(huán)軟件流水也可以用到迭代之間存在數(shù)據(jù)相關(guān)的循環(huán)，這樣的循環(huán)叫做do-across循環(huán)for (i = 0; i n; i +) sum = sum + Ai;Bi = Ai b;該循環(huán)的執(zhí)行不可能快于每2周期1次迭代即使有更多的加法器或乘法器，也不可能更快吞吐能力受到穿越迭代的數(shù)據(jù)相關(guān)鏈的限制10.5 軟 件 流 水 10.5.5 軟件流水的目標(biāo)和約束目標(biāo)基本目標(biāo)是極大化耗時(shí)較長的循環(huán)的吞吐能力次要目標(biāo)是保持所產(chǎn)生代碼的規(guī)模較小達(dá)到目標(biāo)的體現(xiàn)軟件流水化

28、的循環(huán)應(yīng)該有較小的流水線穩(wěn)定狀態(tài)實(shí)現(xiàn)策略 讓每次迭代的相對調(diào)度都相同，并且這些迭代以同樣的時(shí)間間隔逐步啟動10.5 軟 件 流 水 10.5.5 軟件流水的目標(biāo)和約束資源約束令機(jī)器資源由R = r1, r2, .表示，其中ri是第i類資源可用部件數(shù)若循環(huán)的一次迭代需要第i類資源ni個(gè)部件流水化循環(huán)的平均啟動間隔至少是maxi(ni/ri)周期如果maxi(ni/ri)小于1，則將源代碼展開幾次是有用的10.5 軟 件 流 水 10.5.5 軟件流水的目標(biāo)和約束數(shù)據(jù)相關(guān)一個(gè)操作可能依賴于前一次迭代中同樣操作的結(jié)果，不同于到目前為止碰到的數(shù)據(jù)相關(guān)僅用延遲來標(biāo)記邊不夠用，需要區(qū)別不同迭代中同一操作的

29、實(shí)例，例如：for (i = 2; i n; i +)Ai = Bi + Ai 2寫Ai和讀Ai 2的依賴邊上標(biāo)記的迭代次數(shù)差是210.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行編程模型任務(wù)并行數(shù)據(jù)并行流水線并行（前面幾節(jié)涉及較多）本節(jié)內(nèi)容圍繞任務(wù)并行和數(shù)據(jù)并行介紹并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的概況給出并行化的基本概念，程序循環(huán)的變換，還有對并行化有用的概念類似的考慮怎樣用于優(yōu)化數(shù)據(jù)局部性以矩陣乘算法的優(yōu)化為例 10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1 多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器多個(gè)高性能處理器集成在一塊

30、芯片上10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1 多處理器對稱多處理器的體系結(jié)構(gòu)二級緩存內(nèi)存總線二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器多個(gè)高性能處理器集成在一塊芯片上 通過共享內(nèi)存來進(jìn)行通信必須在處理器的緩存中找到它操作的大部分?jǐn)?shù)據(jù)，以保證性能10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1 多處理器分布式內(nèi)存機(jī)器總線或其它互連二級緩存二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器局部內(nèi)存局部內(nèi)存局部內(nèi)存局部內(nèi)存在內(nèi)存分層中又引入一層處理器能迅速訪問自己的局部內(nèi)存 10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1

31、 多處理器分布式內(nèi)存機(jī)器總線或其它互連二級緩存二級緩存二級緩存二級緩存一級緩存一級緩存一級緩存一級緩存處理器處理器處理器處理器局部內(nèi)存局部內(nèi)存局部內(nèi)存局部內(nèi)存在內(nèi)存分層中又引入一層處理器能迅速訪問自己的局部內(nèi)存 非均勻內(nèi)存訪問的機(jī)器和消息傳遞的機(jī)器；為獲得良好的性能軟件都必須有很好局部性 10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.2 應(yīng)用中的并行性并行應(yīng)用性能衡量的兩種標(biāo)準(zhǔn)并行覆蓋：整個(gè)計(jì)算中并行運(yùn)行部分的百分比并行粒度：處理器上無需和其它處理器同步或通信的計(jì)算量循環(huán)對并行化來說特別有吸引力，循環(huán)可以有許多次迭代計(jì)算，如果這些計(jì)算相互獨(dú)立，則它們是并行計(jì)算的主要來源許多控制結(jié)構(gòu)簡單、數(shù)據(jù)量

32、大并且耗時(shí)長的科學(xué)和工程應(yīng)用，很容易以較細(xì)粒度被并行化 10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3 循環(huán)級并行耗時(shí)的應(yīng)用一般都使用大數(shù)組，導(dǎo)致程序中出現(xiàn)有許多次迭代的循環(huán)，這些迭代經(jīng)常相互獨(dú)立，可以把這類循環(huán)的大量迭代分到各處理器上10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3 循環(huán)級并行for (i = 0; i n; i+) Zi = Xi Yi;Zi = Zi Zi;/ 變換成如下代碼b = ceil (n/M); / M個(gè)處理器, p = 0, 1, , M 1 for (i = bp; i min(n, b(p+1); i+) Zi = Xi Yi;Zi = Zi Zi; /

33、 數(shù)據(jù)并行的例子10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3 循環(huán)級并行對并行化來說，任務(wù)級不像循環(huán)級那樣有吸引力對一個(gè)程序而言，獨(dú)立的任務(wù)數(shù)是一個(gè)常數(shù)，它不像典型的循環(huán)那樣，獨(dú)立的計(jì)算單元隨迭代次數(shù)增加而增加任務(wù)通常不是等規(guī)模的，因此很難保證所有的處理器在所有時(shí)間都處于忙碌10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性程序局部性大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼，并且僅涉及一小部分?jǐn)?shù)據(jù)時(shí)間局部性 程序訪問的內(nèi)存單元在很短的時(shí)間內(nèi)可能再次被程序訪問空間局部性毗鄰被訪問單元的內(nèi)存單元在很短的時(shí)間內(nèi)可能被訪問10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性同一個(gè)

34、緩存行上的元素一起被使用的情況是空間局部性的一種重要形式這種空間局部性將緩存未命中降到最低，因此使得程度獲得明顯的加速10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性for (i = 0; i n; i+) / 該程序段對向量機(jī)來 Zi = Xi Yi;/ 說是一種優(yōu)化形式 for (i = 0; i n; i+) Zi = Zi Zi;for (i = 0; i n; i+) / 有較好的數(shù)據(jù)局部性 Zi = Xi Yi; Zi = Zi Zi;10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性對行為主的數(shù)組Z，根據(jù)空間局部性，顯然更愿意逐行地給該數(shù)組元素置零for (

35、j = 0; j n; j+)for (i = 0; i n; i+) for (i = 0; i n; i+) for (j = 0; j n; j+) Zi, j = 0; Zi, j = 0;為了獲得最好的性能，應(yīng)該并行化外循環(huán) b = ceil (n/M); for (i = bp; i min(n, b(p+1); i+) for (j = 0; j n; j+) Zi, j = 0;10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性操作在數(shù)組上的數(shù)值應(yīng)用的幾個(gè)重要特征數(shù)組代碼經(jīng)常有許多可以并行化的循環(huán)當(dāng)循環(huán)有并行性時(shí)，它們的迭代可按任意次序執(zhí)行，因而可重新安排計(jì)算次序以徹底改進(jìn)數(shù)據(jù)局部性在創(chuàng)建相互獨(dú)立的并行計(jì)算大單元時(shí)，串行執(zhí)行這些單元往往會產(chǎn)生較好的數(shù)據(jù)局部性10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5 矩陣乘法算法該算法是計(jì)算密集型的，原則上內(nèi)存訪問不應(yīng)該構(gòu)成瓶頸假定矩陣的布局是行為主假定正好c個(gè)數(shù)組元素能夠放滿一個(gè)緩存行，X的一行僅散布在n/c個(gè)緩