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

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

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

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

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

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

6、元素間的別名分析Ai和Aj是否互為別名指針別名分析若p和q相等，則p和q、p-next和q-next、p-data和q-data等都分別互為別名過程間分析引用調用場合：形參和形參之間、形參和全局變量之間因實參而引起互為別名10.2 代碼調度的約束 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若瞄準極小化寄存器的使用個數，則只需使用3個寄存器

7、10.2 代碼調度的約束 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完成整個計算需要7步10.2 代碼調度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷例：(a + b) + c + (d + e)+e+c+ab+d如果對每個中間結果使用不同寄存器，則完成計算只需要4步R1 = aR6 = R1+R2R8 = R6+R3R9 = R8

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

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

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

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

12、集E按如下兩步構造N中的每個操作n有一張資源預留表RTn，其值直接就是n的操作類型的資源預留表每條邊e都標示有延遲de，表示e的目的結點必須在它源結點發(fā)射de個時鐘周期之后才可以發(fā)射10.3 基 本 塊 調 度數據依賴圖資源預留表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 基 本 塊 調 度10.3.2 基本塊的表調度關鍵

13、路徑包括最后5個結點，故第3條指令先調度再調度第1條指令，因為第4條指令還需等1周期第4周期調度2條資源預留表alu men調度表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 基 本 塊 調 度10.3.2 基本塊的表調度根據每個結點同先前已經被調度的各結點之間的數據相關約束，來計算一個結點可以執(zhí)行的最早時間槽這個結點所需資源根據一張資源預留表來進行檢查，該資源預留表收集了所有到目前為止被占用資源。這個結點的調度按有足夠資源的最早時間槽來安排10.

14、4 全局代碼調度對于有適度指令級并行的機器，僅對每個基本塊進行緊湊調度會引起許多資源空閑全局調度：為了更好地利用機器資源，需要考慮把指令從一個基本塊移到另一個基本塊的代碼生成策略必須保證原來程序中所有指令在優(yōu)化程序中都被執(zhí)行當優(yōu)化程序可以投機地執(zhí)行額外指令時，這些指令肯定不能有任何多余的副作用10.4 全局代碼調度10.4.1 簡單的代碼移動先用例子展示操作在基本塊之間移動涉及的問題 L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調度的機器代碼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 全局代碼調度假定a, b, c, d和e的地址不同，分別保存在R1到R5由于數據相關，塊內的指令必須串行執(zhí)行，且插入 NOPL:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調度的機器代碼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 全局代碼調度假定機器在一個時鐘周期執(zhí)

16、行任意的兩個操作讀取操作有2周期的延遲，其他指令1周期的延遲L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調度的機器代碼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 全局代碼調度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)行B2的讀取操作在執(zhí)行B1時投機地完成B2的存儲操作放到B3的一份拷貝中L:if (a = 0) goto Lc = be = d + d(a) 源代碼(b) 局部調

17、度的機器代碼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 全局代碼調度L:全局調度前后的流圖if (a = 0) goto Lc = be = d + d(a) 源代碼ST 0(R5), R8(b) 局部調度的機器代碼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) 全局調度的機器

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 全局代碼調度基本塊之間的支配關系指令在基本塊之間的移動因支配關系不同而不同B1和B3控制等價：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 全局代碼調度10.4.2 向上的代碼移動從塊src向上移動到塊dst，假定移動未違反數據相關，并使得通過dst到src的路徑運行得較快若dst和src等價，則被移動操作應該被執(zhí)行時，它正好僅被執(zhí)行一次dstsrc10.4 全局代碼調度10.4.2 向上的代碼移動從塊src向上移動到塊dst，假定移動未違反數據相關，并使得通過dst到src的路徑運行得較快若dst和src等價，則被移動操作應該被執(zhí)行時，它正好僅被執(zhí)行一次若src未后支配dst，被移動操作可利用空閑資源免費執(zhí)行，在控制流到達src時獲益dstsrc10.4 全局代碼調度10.4.2

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

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

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

23、把對它的投機定值移到該點的上面x = 1x = 210.4 全局代碼調度10.4.5 全局調度的其他問題 程序調度應該使經常執(zhí)行的路徑運行得快一些，不經常執(zhí)行的路徑可能會因調度變得慢一些 編譯器可用來估計執(zhí)行頻率的技術有若干種(1) 內循環(huán)比外循環(huán)執(zhí)行得更頻繁(2) 分支指令往回跳轉比不跳轉要更經常(3)看守程序出口或異常處理例程的分支語句很少被執(zhí)行最好的頻率估計來自動態(tài)剖析，程序被靜態(tài)插樁以用來運行時記錄條件分支每次的走向10.4 全局代碼調度10.4.5 全局調度的其他問題 最簡單的全局調度算法也相當復雜，不介紹 在一些全局調度算法中，循環(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 全局代碼調度10.4.6 靜態(tài)調度器和動態(tài)調度器的相互影響動態(tài)調度器的優(yōu)點是可以根據運行時的情況建立新的調度表，無需事先編碼所有可能的調度表10.4 全局代碼調度10.4.6 靜態(tài)調度器和動態(tài)調度器的相互影響存在動態(tài)調度情況下，靜態(tài)調度器的作用保證盡早地取高延遲的指令，使得動態(tài)調度器能夠盡早發(fā)射它們盡早安排預取指令，使數據到要用時已經在緩存, 或盡早安排可能不命中緩存的操

25、作只需要給數據相關的操作安排正確的次序，無需通過極小化延遲來分離每一對數據相關的操作給分支預測指令較高優(yōu)先級，以減少預測錯誤的代價10.5 軟 件 流 水 10.5.1 引言軟件流水是一種調度算法，它每次調度一個完整的循環(huán)，以充分利用穿越迭代的并行性單次迭代的操作中幾乎沒有什么并行性軟件流水技術不斷地重疊一些相繼迭代，直到所有迭代都填入流水線為止能產生高效和緊湊的代碼以一周期內可以同時發(fā)射一個讀取、一個存儲、一個算術運算（全流水）和一個分支操作的機器來舉例10.5 軟 件 流 水 每次調度一個迭代的結果見右邊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 該計算大部分是串行的，它需要7周期，只有循環(huán)回跳指令和迭代中最后一條指令重疊 10.5 軟 件 流 水 循環(huán)展開4次迭代的調度結果見右邊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)軟件流水也可以用到迭代之間存在數據相關的循環(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次迭代即使有更多的加法器或乘法器，也不可能更快吞吐能力受到穿越迭代的數據相關鏈的限制10.5 軟 件 流 水 10.5.5 軟件流水的目標和約束目標基本目標是極大化耗時較長的循環(huán)的吞吐能力次要目標是保持所產生代碼的規(guī)模較小達到目標的體現軟件流水化

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

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

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

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

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

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

34、緩存行上的元素一起被使用的情況是空間局部性的一種重要形式這種空間局部性將緩存未命中降到最低，因此使得程度獲得明顯的加速10.6 并行性和數據局部性優(yōu)化概述10.6.4 數據局部性for (i = 0; i n; i+) / 該程序段對向量機來 Zi = Xi Yi;/ 說是一種優(yōu)化形式 for (i = 0; i n; i+) Zi = Zi Zi;for (i = 0; i n; i+) / 有較好的數據局部性 Zi = Xi Yi; Zi = Zi Zi;10.6 并行性和數據局部性優(yōu)化概述10.6.4 數據局部性對行為主的數組Z，根據空間局部性，顯然更愿意逐行地給該數組元素置零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;為了獲得最好的性能，應該并行化外循環(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 并行性和數據局部性優(yōu)化概述10.6.4 數據局部性操作在數組上的數值應用的幾個重要特征數組代碼經常有許多可以并行化的循環(huán)當循環(huán)有并行性時，它們的迭代可按任意次序執(zhí)行，因而可重新安排計算次序以徹底改進數據局部性在創(chuàng)建相互獨立的并行計算大單元時，串行執(zhí)行這些單元往往會產生較好的數據局部性10.6 并行性和數據局部性優(yōu)化概述10.6.5 矩陣乘法算法該算法是計算密集型的，原則上內存訪問不應該構成瓶頸假定矩陣的布局是行為主假定正好c個數組元素能夠放滿一個緩存行，X的一行僅散布在n/c個緩