1、第十章第十章 依賴于機器的優化依賴于機器的優化 在指令級并行的機器上，程序的運行速度依在指令級并行的機器上，程序的運行速度依賴于下面幾個因素賴于下面幾個因素 程序中潛在的并行程序中潛在的并行 處理器上可用的并行處理器上可用的并行 從串行程序提取并行的能力從串行程序提取并行的能力 在給定的調度約束下發現最佳并行調度的能力在給定的調度約束下發現最佳并行調度的能力 并行的提取和并行執行的調度都可以靜態地并行的提取和并行執行的調度都可以靜態地在軟件中或動態地在硬件中完成在軟件中或動態地在硬件中完成第十章第十章 依賴于機器的優化依賴于機器的優化 本章內容本章內容 使用使用指令級并行指令級并行的基礎問題的

2、基礎問題 提取并行的數據相關性分析提取并行的數據相關性分析 代碼調度的基本概念代碼調度的基本概念 基本塊調度的技術、發現通用程序中的高度數據基本塊調度的技術、發現通用程序中的高度數據相關控制流的方法、調度數值程序的軟件流水線相關控制流的方法、調度數值程序的軟件流水線技術技術 在在多處理器系統多處理器系統上，使用數組的計算密集型程序上，使用數組的計算密集型程序的并行化和數據局部性優化的概念和方法的并行化和數據局部性優化的概念和方法10.1 處理器體系結構處理器體系結構 在考慮指令級并行時，通常想象成一個處理在考慮指令級并行時，通常想象成一個處理器在單個時鐘周期內發射幾個操作器在單個時鐘周期內發射

3、幾個操作 事實上，在每周期內發射一個操作是可能的事實上，在每周期內發射一個操作是可能的, 而指令級并行的獲得是通過使用流水線技術而指令級并行的獲得是通過使用流水線技術 本節先解釋流水線，然后討論多指令發射本節先解釋流水線，然后討論多指令發射10.1 處理器體系結構處理器體系結構10.1.1 指令流水線和分支延遲指令流水線和分支延遲 ii + 1i + 2i + 3i + 41. IF2. IDIF3. EXIDIF4. MEMEXIDIF5. WBMEMEXIDIF6.WBMEMEXID7.WBMEMEX8.WBMEM9.WB取指令取指令IF, 譯碼譯碼ID, 執行操作執行操作EX, 訪問內存

4、訪問內存MEM, 回寫結果回寫結果WB5級指令流水線中級指令流水線中的的5條連續指令條連續指令 10.1 處理器體系結構處理器體系結構10.1.1 指令流水線和分支延遲指令流水線和分支延遲 分支延遲分支延遲 發現應該執行一個分支而不是直接后繼發現應該執行一個分支而不是直接后繼 轉向一個分支時會引起取分支目的地址指令的延轉向一個分支時會引起取分支目的地址指令的延遲并引起指令流水線遲并引起指令流水線“打嗝打嗝” 可以通過使用硬件，根據分支的執行歷史來預測可以通過使用硬件，根據分支的執行歷史來預測分支結果并從預測的目的地址預取指令分支結果并從預測的目的地址預取指令 分支延遲不可避免，因為分支預測會發

5、生偏差分支延遲不可避免，因為分支預測會發生偏差10.1 處理器體系結構處理器體系結構10.1.2 流水化的執行流水化的執行如果不依賴一條指令結果的隨后指令在該結如果不依賴一條指令結果的隨后指令在該結果產生前就被允許執行果產生前就被允許執行 有些指令的執行需要幾個周期，幾個操作同時出有些指令的執行需要幾個周期，幾個操作同時出現在它們的執行級上可能的現在它們的執行級上可能的 如果最長的執行流水線是如果最長的執行流水線是n級，級，n個操作同時進行個操作同時進行的可能性是存在的的可能性是存在的 并非所有的指令都能被完全流水化，例如浮點除并非所有的指令都能被完全流水化，例如浮點除 通用處理器大都動態察覺

6、相繼指令之間的依賴性通用處理器大都動態察覺相繼指令之間的依賴性 嵌入式系統把數據相關性的檢查交給軟件嵌入式系統把數據相關性的檢查交給軟件10.1 處理器體系結構處理器體系結構10.1.3 多指令發射多指令發射 每周期發射幾個操作，讓更多操作同時進行每周期發射幾個操作，讓更多操作同時進行 超長指令字機器超長指令字機器 將若干個操作編碼在單周期中發射將若干個操作編碼在單周期中發射 編譯器需要確定哪些操作可以并行發射編譯器需要確定哪些操作可以并行發射 超標量機器超標量機器 超標量機器有按普通順序執行語義的正規指令集超標量機器有按普通順序執行語義的正規指令集 硬件自動察覺指令之間的相關性，并且在它們的

7、硬件自動察覺指令之間的相關性，并且在它們的操作數可用時就發射它們操作數可用時就發射它們 更復雜的調度器能夠更復雜的調度器能夠“亂序亂序”執行指令執行指令10.2 代碼調度的約束代碼調度的約束 代碼調度代碼調度 用在代碼生成器產生的機器代碼上的優化技術用在代碼生成器產生的機器代碼上的優化技術 本節討論代碼調度的約束本節討論代碼調度的約束 控制相關約束控制相關約束 在原程序中執行的所有操作都在原程序中執行的所有操作都必須在優化代碼中執行必須在優化代碼中執行 數據相關約束數據相關約束 優化程序中的操作產生的結果優化程序中的操作產生的結果必須同原程序對應操作的結果一樣必須同原程序對應操作的結果一樣 資

8、源約束資源約束 調度不能過分占用機器的資源調度不能過分占用機器的資源 優化程序很難調試優化程序很難調試 內存狀態可能和順序執行的任何內存狀態不匹配內存狀態可能和順序執行的任何內存狀態不匹配10.2 代碼調度的約束代碼調度的約束 10.2.1 數據相關數據相關 真相關真相關 如果對同一個單元先寫后讀，那么如果對同一個單元先寫后讀，那么讀依賴于所寫的值讀依賴于所寫的值 反相關反相關 如果對同一個單元先讀后寫。可以如果對同一個單元先讀后寫。可以通過把值存在不同的單元來刪除反相關通過把值存在不同的單元來刪除反相關 輸出相關輸出相關 如果對同一個單元先后寫兩次。也如果對同一個單元先后寫兩次。也可刪除可刪

9、除 數據相關概念可同時用于內存訪問和寄存器數據相關概念可同時用于內存訪問和寄存器訪問訪問10.2 代碼調度的約束代碼調度的約束 10.2.2 發現內存訪問中的相關性發現內存訪問中的相關性 例例(1) a = 1(2) p = 2(3) x = a 語句語句(1)和和(2)可能構成輸出相關可能構成輸出相關 語句語句(1)和和(3)可能構成真相關可能構成真相關 語句語句(2)和和(3)可能構成真相關可能構成真相關 除非編譯器知道除非編譯器知道p不可能指向不可能指向a，否則，否則3個操作必個操作必須串行執行須串行執行10.2 代碼調度的約束代碼調度的約束 10.2.2 發現內存訪問中的相關性發現內存

10、訪問中的相關性 發現數據相關需要不同形式的分析發現數據相關需要不同形式的分析 數組元素間的別名分析數組元素間的別名分析Ai和和Aj是否互為別名是否互為別名 指針別名分析指針別名分析若若p和和q相等，則相等，則 p和和 q、p-next和和q-next、p-data和和q-data等都分別互為別名等都分別互為別名 過程間分析過程間分析引用調用場合：形參和形參之間、形參和全局變引用調用場合：形參和形參之間、形參和全局變量之間因實參而引起互為別名量之間因實參而引起互為別名10.2 代碼調度的約束代碼調度的約束 10.2.3 寄存器使用和并行執行之間的折衷寄存器使用和并行執行之間的折衷例：例：(a +

11、 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個寄存器個寄存器 10.2 代碼調度的約束代碼調度的約束 10.2.3 寄存器使用和并行執行之間的折衷寄存器使用和并行執行之間的折衷例：例：(a + b) + c + (d + e)LD R1, aLD R2, bADD R1, R1, R2LD R2, cADD R1,

12、R1, R2LD R2, dLD R3, eADD R2, R2, R3ADD R1, R1, R2+e+c+ab+d完成整個計算需要完成整個計算需要7步步10.2 代碼調度的約束代碼調度的約束 10.2.3 寄存器使用和并行執行之間的折衷寄存器使用和并行執行之間的折衷例：例：(a + b) + c + (d + e)+e+c+ab+d如果對每個中間結果如果對每個中間結果使用不同寄存器，則使用不同寄存器，則完成計算只需要完成計算只需要4步步R1 = aR6 = R1+R2R8 = R6+R3R9 = R8+R7R2 = bR7 = R4+R5R3 = cR4 = d R5 = e10.2 代碼

13、調度的約束代碼調度的約束 10.2.4 寄存器分配和代碼調度的次序安排寄存器分配和代碼調度的次序安排 先寄存器分配先寄存器分配 結果代碼中會有很多存儲相關結果代碼中會有很多存儲相關 非數值應用本質上沒有多少并行，采用這種方式非數值應用本質上沒有多少并行，采用這種方式 先代碼調度先代碼調度 導致寄存器溢出，抵消指令級并行的優點導致寄存器溢出，抵消指令級并行的優點 適用于有許多大表達式的數值應用適用于有許多大表達式的數值應用 在假定偽寄存器就是物理寄存器情況下，先調度在假定偽寄存器就是物理寄存器情況下，先調度指令，然后寄存器分配，把處理寄存器溢出的代指令，然后寄存器分配，把處理寄存器溢出的代碼附加

14、在必要的地方，并再次進行代碼調度碼附加在必要的地方，并再次進行代碼調度10.2 代碼調度的約束代碼調度的約束 10.2.5 控制相關控制相關 在非數值計算中，基本塊非常小，其中的操作通在非數值計算中，基本塊非常小，其中的操作通常高度相關，幾乎不能并行常高度相關，幾乎不能并行 調查跨基本塊的并行是至關重要的調查跨基本塊的并行是至關重要的 若一條指令很可能被執行且有空閑的資源可若一條指令很可能被執行且有空閑的資源可“免免費費”用于完成該指令的操作，則可以投機地執行用于完成該指令的操作，則可以投機地執行該指令；若投機成功，則程序運行得快一些該指令；若投機成功，則程序運行得快一些例例 if (a t)

15、 b = a a依賴于比較依賴于比較a t的結果的結果 b = a a; 若若a a不會產生副作用，則不會產生副作用，則d = a + c; a a可以投機地執行可以投機地執行10.2 代碼調度的約束代碼調度的約束 10.2.6 投機執行的支持投機執行的支持 內存讀取是一類使用頻繁，且能從投機執行大大內存讀取是一類使用頻繁，且能從投機執行大大獲益的指令獲益的指令 但在但在 if (p != null)q = p中，投機地對中，投機地對p脫引用將引起該程序因脫引用將引起該程序因p等于等于null而錯誤地停止而錯誤地停止 許多高性能處理器提供專門的特性來支持投機地許多高性能處理器提供專門的特性來支

16、持投機地內存訪問內存訪問10.2 代碼調度的約束代碼調度的約束 10.2.6 投機執行的支持投機執行的支持 預取指令預取指令在數據使用前將其從內存取到緩存在數據使用前將其從內存取到緩存,若該單元無效或訪問它會引起缺頁，則忽略若該單元無效或訪問它會引起缺頁，則忽略 抑制位抑制位允許投機地從內存將數據讀取到寄允許投機地從內存將數據讀取到寄存器堆，若出現非法內存訪問或缺頁，則設置目存器堆，若出現非法內存訪問或缺頁，則設置目標寄存器的抑制位標寄存器的抑制位 判定指令判定指令在判定條件為真時才執行的指令在判定條件為真時才執行的指令例例 if (a = 0)翻譯成翻譯成 ADD R3, R4, R5b =

17、 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類資源中可用的部件數類資源中可用

18、的部件數 每個操作有一組輸入操作數、一組輸出操作數和每個操作有一組輸入操作數、一組輸出操作數和一個資源需求一個資源需求 和每個輸入操作數相關的是一個輸入延遲和每個輸入操作數相關的是一個輸入延遲 和每個輸出操作數相關的是一個輸出延遲和每個輸出操作數相關的是一個輸出延遲10.2 代碼調度的約束代碼調度的約束 10.2.7 一個基本的機器模型一個基本的機器模型 機器模型機器模型M = (R, T) 對每種操作類型對每種操作類型t，資源使用由一張二維資源預留，資源使用由一張二維資源預留表表RTt來建模來建模 條目條目RTti, j是是t類型的一個操作在它被發射類型的一個操作在它被發射i時鐘時鐘周期后，

19、使用第周期后，使用第j種資源的部件數種資源的部件數 對任何對任何t、i和和j，RTti, j必須小于或等于必須小于或等于Rj10.3 基基 本本 塊塊 調調 度度10.3.1 數據依賴圖數據依賴圖 基本塊由數據依賴圖基本塊由數據依賴圖G = (N, E)來表示來表示 結點集合結點集合N表示該塊的機器指令中的操作集合表示該塊的機器指令中的操作集合 有向邊集合有向邊集合E表示這些操作之間的數據相關約束表示這些操作之間的數據相關約束 G的結點集的結點集N和邊集和邊集E按如下兩步構造按如下兩步構造 N中的每個操作中的每個操作n有一張資源預留表有一張資源預留表RTn，其值直，其值直接就是接就是n的操作類

20、型的資源預留表的操作類型的資源預留表 每條邊每條邊e都標示有延遲都標示有延遲de，表示，表示e的目的結點必須的目的結點必須在它源結點發射在它源結點發射de個時鐘周期之后才可以發射個時鐘周期之后才可以發射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操作是全流水操作是全流水的，只需顯示的

21、，只需顯示在第在第1行使用行使用的資源的資源 10.3 基基 本本 塊塊 調調 度度10.3.2 基本塊的表調度基本塊的表調度 關鍵路徑包括最后關鍵路徑包括最后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.

22、3.2 基本塊的表調度基本塊的表調度 根據每個結點同先前已經被調度的各結點之間的根據每個結點同先前已經被調度的各結點之間的數據相關約束，來計算一個結點可以執行的最早數據相關約束，來計算一個結點可以執行的最早時間槽時間槽 這個結點所需資源根據一張資源預留表來進行檢這個結點所需資源根據一張資源預留表來進行檢查，該資源預留表收集了所有到目前為止被占用查，該資源預留表收集了所有到目前為止被占用資源。這個結點的調度按有足夠資源的最早時間資源。這個結點的調度按有足夠資源的最早時間槽來安排槽來安排10.4 全局代碼調度全局代碼調度 對于有適度指令級并行的機器，僅對每個基對于有適度指令級并行的機器，僅對每個基

23、本塊進行緊湊調度會引起許多資源空閑本塊進行緊湊調度會引起許多資源空閑 全局調度：為了更好地利用機器資源，需要全局調度：為了更好地利用機器資源，需要考慮把指令從一個基本塊移到另一個基本塊考慮把指令從一個基本塊移到另一個基本塊的代碼生成策略的代碼生成策略必須保證必須保證 原來程序中所有指令在優化程序中都被執行原來程序中所有指令在優化程序中都被執行 當優化程序可以投機地執行額外指令時，這些指當優化程序可以投機地執行額外指令時，這些指令肯定不能有任何多余的副作用令肯定不能有任何多余的副作用10.4 全局代碼調度全局代碼調度10.4.1 簡單的代碼移動簡單的代碼移動 先用例子展示操作在基本塊之間移動涉及

24、的問題先用例子展示操作在基本塊之間移動涉及的問題 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 全局代碼調度全局代碼調度 假定假定a, b, c, d和和e的地址不同，分別保存在的地址不同，分別保存在R1到到R5 由于數據相關，塊內的指令必須串行執行，且插由于數據相關，塊內的指令必須串行執行，且

25、插入入 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 全局代碼調度全局代碼調度 假定機器在一個時鐘周期執行任意的兩個操作假定機器在一個時鐘周期執行任意的兩個操作 讀取操作有讀取操作有2周期的延遲，其他指令周期的延遲，其他指令1周期的延遲周期的延遲L:if (a = 0) goto Lc =

26、 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肯定要執行，因而可以和肯定要執行，因而可以和B1并行執行并行執行 B2的讀取操作在執行的讀取操作在執行B1時投機地完成時投機地完成 B2的存儲操作放到的存儲操作放到B3的的一份拷貝中一份拷貝中L:if (a = 0) goto Lc = be = d + d(a)

27、 源代碼源代碼(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 全局代碼調度全局代碼調度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,

28、 BEQZ R6, LST 0(R5), R8, ST 0(R3), R7L:(c) 全局調度的機器代碼全局調度的機器代碼B1B3 B3LD 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后支配后支配B1 B1支配支配B2，但

29、是但是B2并非后支配并非后支配B1 B2不支配不支配B3，但是但是B3后支配后支配B2LD 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 全局代碼調度全局代碼調度10.4.2 向上的代碼移動向上的代碼移動從塊從塊src向上移動到塊向上移動到塊dst，假定移動未違反數據相，假定移動未違反數據相關，并使得通過關，并使得通過dst到到src的路徑運行得較快的路徑運行得較快 若若dst和和src等價，則被移動操作應該被執行時，它等價，則

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

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

32、.4 全局代碼調度全局代碼調度10.4.3 向下的代碼移動向下的代碼移動從塊從塊src向下移動到塊向下移動到塊dst，假定移動未違反數據相，假定移動未違反數據相關，并使得通過關，并使得通過dst到到src的路徑運行得較快的路徑運行得較快 若若dst和和src等價，則被移動操作應該被執行時，它等價，則被移動操作應該被執行時，它正好僅被執行一次正好僅被執行一次srcdst10.4 全局代碼調度全局代碼調度10.4.3 向下的代碼移動向下的代碼移動從塊從塊src向下移動到塊向下移動到塊dst，假定移動未違反數據相，假定移動未違反數據相關，并使得通過關，并使得通過dst到到src的路徑運行得較快的路徑

33、運行得較快 若若dst和和src等價，則被移動操作應該被執行時，它等價，則被移動操作應該被執行時，它正好僅被執行一次正好僅被執行一次 src未后支配未后支配dst, 向下移動的代碼經常是存儲操作向下移動的代碼經常是存儲操作, 復制從復制從src到到dst路徑上的各塊，并把路徑上的各塊，并把被移動操作僅放置在被移動操作僅放置在dst的新拷貝中的新拷貝中srcdst10.4 全局代碼調度全局代碼調度9.5節的例子可作為參考節的例子可作為參考B1B2B3B4a = b + cB5B6B7d = b + cB1B2B3B4t = b + ca = tB4 B5d = td = b + cB6B6 B7

34、10.4 全局代碼調度全局代碼調度10.4.3 向下的代碼移動向下的代碼移動從塊從塊src向下移動到塊向下移動到塊dst，假定移動未違反數據相，假定移動未違反數據相關，并使得通過關，并使得通過dst到到src的路徑運行得較快的路徑運行得較快 若若dst和和src等價，則被移動操作應該被執行時，它等價，則被移動操作應該被執行時，它正好僅被執行一次正好僅被執行一次 src未后支配未后支配dst, 向下移動的代碼經常是存儲操作向下移動的代碼經常是存儲操作, 復制從復制從src到到dst路徑上的各塊，并把路徑上的各塊，并把被移動操作僅放置在被移動操作僅放置在dst的新拷貝中的新拷貝中 dst沒有后支配

35、沒有后支配src，插入補償代碼以，插入補償代碼以保證被移動操作在不經保證被移動操作在不經dst路徑上也執行路徑上也執行srcdst10.4 全局代碼調度全局代碼調度10.4.4 更新數據相關更新數據相關代碼移動會改變操作之間的數據相關關系代碼移動會改變操作之間的數據相關關系 兩個對兩個對x的賦值之一可以移動到最上面的基本塊的賦值之一可以移動到最上面的基本塊，該變換能維持原來程序中的所有相關性，該變換能維持原來程序中的所有相關性 一旦一個對一旦一個對x的賦值被上移，另一個就不能移動的賦值被上移，另一個就不能移動了了 移動使得移動使得x在最上面塊的出口在最上面塊的出口由不活躍變成活躍由不活躍變成活

36、躍 一個變量在某個程序點一個變量在某個程序點活躍，則就不能把對它的投機活躍，則就不能把對它的投機定值移到該點的上面定值移到該點的上面x = 1x = 210.4 全局代碼調度全局代碼調度10.4.5 全局調度的其他問題全局調度的其他問題 程序調度應該使經常執行的路徑運行得快一些，程序調度應該使經常執行的路徑運行得快一些，不經常執行的路徑可能會因調度變得慢一些不經常執行的路徑可能會因調度變得慢一些 編譯器可用來估計執行頻率的技術有若干種編譯器可用來估計執行頻率的技術有若干種(1) 內循環比外循環執行得更頻繁內循環比外循環執行得更頻繁(2) 分支指令往回跳轉比不跳轉要更經常分支指令往回跳轉比不跳轉

37、要更經常(3)看守程序出口或異常處理例程的分支語句很看守程序出口或異常處理例程的分支語句很少被執行少被執行 最好的頻率估計來自動態剖析，程序被靜態插樁最好的頻率估計來自動態剖析，程序被靜態插樁以用來運行時記錄條件分支每次的走向以用來運行時記錄條件分支每次的走向10.4 全局代碼調度全局代碼調度10.4.5 全局調度的其他問題全局調度的其他問題 最簡單的全局調度算法也相當復雜，不介紹最簡單的全局調度算法也相當復雜，不介紹 在一些全局調度算法中，循環迭代的邊界是代碼移在一些全局調度算法中，循環迭代的邊界是代碼移動的一種屏障，需循環展開動的一種屏障，需循環展開for(i = 0; i N; i +)

38、 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 靜態調度器和動態調度器的相互影響靜態調度器和動態調度器的相互影響動態調度器的優點是可以根據運行時的情況建立新動態調度器的優點是可以根據運行時的情況建立新的調度表，無需事先編碼所有可能的調度表的調度表，無需事先編碼所有可能的調度表10.4 全局代碼調度全局代碼調度10.4.6 靜態調度器和動態調度器的相互影響靜態調度器和動態調度器的相互影響 存在動態調度情況下，靜態調

39、度器的作用存在動態調度情況下，靜態調度器的作用 保證盡早地取高延遲的指令，使得動態調度器能保證盡早地取高延遲的指令，使得動態調度器能夠盡早發射它們夠盡早發射它們 盡早安排預取指令，使數據到要用時已經在緩存盡早安排預取指令，使數據到要用時已經在緩存, 或盡早安排可能不命中緩存的操作或盡早安排可能不命中緩存的操作 只需要給數據相關的操作安排正確的次序，無需只需要給數據相關的操作安排正確的次序，無需通過極小化延遲來分離每一對數據相關的操作通過極小化延遲來分離每一對數據相關的操作 給分支預測指令較高優先級，以減少預測錯誤的給分支預測指令較高優先級，以減少預測錯誤的代價代價10.5 軟軟 件件 流流 水

40、水 10.5.1 引言引言軟件流水是一種調度算法，它每次調度一個軟件流水是一種調度算法，它每次調度一個完整的循環，以充分利用穿越迭代的并行性完整的循環，以充分利用穿越迭代的并行性 單次迭代的操作中幾乎沒有什么并行性單次迭代的操作中幾乎沒有什么并行性 軟件流水技術不斷地重疊一些相繼迭代，直到所軟件流水技術不斷地重疊一些相繼迭代，直到所有迭代都填入流水線為止有迭代都填入流水線為止 能產生高效和緊湊的代碼能產生高效和緊湊的代碼以一周期內可以同時發射一個讀取、一個存儲、以一周期內可以同時發射一個讀取、一個存儲、一個算術運算（全流水）和一個分支操作的機器一個算術運算（全流水）和一個分支操作的機器來舉例來

41、舉例10.5 軟軟 件件 流流 水水 每次調度一個迭代的結果見右邊每次調度一個迭代的結果見右邊for (i = 0; i n; i +) / R1, R2, R3 = &A, &B, &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周期，只有循周期，只有循環回跳指令和迭環回跳指令和迭代中最后一條指代中最

42、后一條指令重疊令重疊 10.5 軟軟 件件 流流 水水 循環展開循環展開4次迭代的調度結果見右邊次迭代的調度結果見右邊for (i = 0; i = 5)N2 = 1 + 2 (N 1) / 2);elseN2 = 0;for (i = 0; i N2; i +)/ 該循環被流水化該循環被流水化Di = Ai Bi + c;for (i = N2; i N; i +)/ 不需要優化不需要優化Di = Ai Bi + c;10.5 軟軟 件件 流流 水水 10.5.4 Do-Across循環循環軟件流水也可以用到迭代之間存在數據相關的循軟件流水也可以用到迭代之間存在數據相關的循環，這樣的循環叫做

43、環，這樣的循環叫做do-across循環循環for (i = 0; i n; i +) sum = sum + Ai;Bi = Ai b; 該循環的執行不可能快于每該循環的執行不可能快于每2周期周期1次迭代次迭代 即使有更多的加法器或乘法器，也不可能更快即使有更多的加法器或乘法器，也不可能更快 吞吐能力受到穿越迭代的數據相關鏈的限制吞吐能力受到穿越迭代的數據相關鏈的限制10.5 軟軟 件件 流流 水水 10.5.5 軟件流水的目標和約束軟件流水的目標和約束 目標目標 基本目標是極大化耗時較長的循環的吞吐能力基本目標是極大化耗時較長的循環的吞吐能力 次要目標是保持所產生代碼的規模較小次要目標是保

44、持所產生代碼的規模較小 達到目標的體現達到目標的體現 軟件流水化的循環應該有較小的流水線穩定狀態軟件流水化的循環應該有較小的流水線穩定狀態 實現策略實現策略 讓每次迭代的相對調度都相同，并且這些迭代以讓每次迭代的相對調度都相同，并且這些迭代以同樣的時間間隔逐步啟動同樣的時間間隔逐步啟動10.5 軟軟 件件 流流 水水 10.5.5 軟件流水的目標和約束軟件流水的目標和約束 資源約束資源約束 令機器資源由令機器資源由R = r1, r2, .表示，其中表示，其中ri是第是第i類資類資源可用部件數源可用部件數 若循環的一次迭代需要第若循環的一次迭代需要第i類資源類資源ni個部件個部件 流水化循環的

45、平均啟動間隔至少是流水化循環的平均啟動間隔至少是maxi(ni/ri)周期周期 如果如果maxi(ni/ri)小于小于1，則將源代碼展開幾次是有，則將源代碼展開幾次是有用的用的10.5 軟軟 件件 流流 水水 10.5.5 軟件流水的目標和約束軟件流水的目標和約束 數據相關數據相關 一個操作可能依賴于前一次迭代中同樣操作的結一個操作可能依賴于前一次迭代中同樣操作的結果，不同于到目前為止碰到的數據相關果，不同于到目前為止碰到的數據相關 僅用延遲來標記邊不夠用，需要區別不同迭代中僅用延遲來標記邊不夠用，需要區別不同迭代中同一操作的實例，例如：同一操作的實例，例如：for (i = 2; i n;

46、i +)Ai = Bi + Ai 2寫寫Ai和讀和讀Ai 2的依賴邊上標記的迭代次數差的依賴邊上標記的迭代次數差是是210.6 并行性和數據局部性優化概述并行性和數據局部性優化概述 并行編程模型并行編程模型 任務并行任務并行 數據并行數據并行 流水線并行（前面幾節涉及較多）流水線并行（前面幾節涉及較多） 本節內容圍繞任務并行和數據并行本節內容圍繞任務并行和數據并行 介紹并行計算機系統結構的概況介紹并行計算機系統結構的概況 給出并行化的基本概念，程序循環的變換，還有給出并行化的基本概念，程序循環的變換，還有對并行化有用的概念對并行化有用的概念 類似的考慮怎樣用于優化數據局部性類似的考慮怎樣用于優

47、化數據局部性 以矩陣乘算法的優化為例以矩陣乘算法的優化為例 10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.1 多處理器多處理器 對稱多處理器的體系結構對稱多處理器的體系結構二級二級緩存緩存內存內存總線總線二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器多個高性多個高性能處理器能處理器集成在一集成在一塊芯片上塊芯片上10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.1 多處理器多處理器 對稱多處理器的體系結構對稱多處理器的體系結構二級二級

48、緩存緩存內存內存總線總線二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器多個高性多個高性能處理器能處理器集成在一集成在一塊芯片上塊芯片上 通過共通過共享內存來享內存來進行通信進行通信必須在處理器的緩存中必須在處理器的緩存中找到它操作的大部分數找到它操作的大部分數據，以保證性能據，以保證性能10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.1 多處理器多處理器 分布式內存機器分布式內存機器總線或其它互連總線或其它互連二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存

49、二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器局部局部內存內存局部局部內存內存局部局部內存內存局部局部內存內存在內存分在內存分層中又引層中又引入一層入一層處理器能處理器能迅速訪問迅速訪問自己的局自己的局部內存部內存 10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.1 多處理器多處理器 分布式內存機器分布式內存機器總線或其它互連總線或其它互連二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器

50、處理器處理器處理器處理器局部局部內存內存局部局部內存內存局部局部內存內存局部局部內存內存在內存分在內存分層中又引層中又引入一層入一層處理器能處理器能迅速訪問迅速訪問自己的局自己的局部內存部內存 非均勻內存訪問的機器和消息傳非均勻內存訪問的機器和消息傳遞的機器；為獲得良好的性能遞的機器；為獲得良好的性能軟件都必須有很好局部性軟件都必須有很好局部性 10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.2 應用中的并行性應用中的并行性 并行應用性能衡量的兩種標準并行應用性能衡量的兩種標準 并行覆蓋：整個計算中并行運行部分的百分比并行覆蓋：整個計算中并行運行部分的百分比 并行粒度：

51、處理器上無需和其它處理器同步或通并行粒度：處理器上無需和其它處理器同步或通信的計算量信的計算量循環對并行化來說特別有吸引力，循環可以有許循環對并行化來說特別有吸引力，循環可以有許多次迭代計算，如果這些計算相互獨立，則它們是多次迭代計算，如果這些計算相互獨立，則它們是并行計算的主要來源并行計算的主要來源許多控制結構簡單、數據量大并且耗時長的科學許多控制結構簡單、數據量大并且耗時長的科學和工程應用，很容易以較細粒度被并行化和工程應用，很容易以較細粒度被并行化 10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.3 循環級并行循環級并行耗時的應用一般都使用大數組，導致程序中出現耗

52、時的應用一般都使用大數組，導致程序中出現有許多次迭代的循環，這些迭代經常相互獨立，可有許多次迭代的循環，這些迭代經常相互獨立，可以把這類循環的大量迭代分到各處理器上以把這類循環的大量迭代分到各處理器上10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.3 循環級并行循環級并行for (i = 0; i n; i+) Zi = Xi Yi;Zi = Zi Zi;/ 變換成如下代碼變換成如下代碼b = ceil (n/M); / M個處理器個處理器, p = 0, 1, , M 1 for (i = b p; i min(n, b (p+1); i+) Zi = Xi Yi;Z

53、i = Zi Zi; / 數據并行的例子數據并行的例子10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.3 循環級并行循環級并行 對并行化來說，任務級不像循環級那樣有吸引力對并行化來說，任務級不像循環級那樣有吸引力 對一個程序而言，獨立的任務數是一個常數，它對一個程序而言，獨立的任務數是一個常數，它不像典型的循環那樣，獨立的計算單元隨迭代次不像典型的循環那樣，獨立的計算單元隨迭代次數增加而增加數增加而增加 任務通常不是等規模的，因此很難保證所有的處任務通常不是等規模的，因此很難保證所有的處理器在所有時間都處于忙碌理器在所有時間都處于忙碌10.6 并行性和數據局部性優化概述

54、并行性和數據局部性優化概述10.6.4 數據局部性數據局部性 程序局部性程序局部性 大多數程序的大部分時間在執行一小部分代碼，大多數程序的大部分時間在執行一小部分代碼，并且僅涉及一小部分數據并且僅涉及一小部分數據 時間局部性時間局部性 程序訪問的內存單元在很短的時間內可能再次被程序訪問的內存單元在很短的時間內可能再次被程序訪問程序訪問 空間局部性空間局部性 毗鄰被訪問單元的內存單元在很短的時間內可能毗鄰被訪問單元的內存單元在很短的時間內可能被訪問被訪問10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.4 數據局部性數據局部性 同一個緩存行上的元素一起被使用的情況是空間同一

55、個緩存行上的元素一起被使用的情況是空間局部性的一種重要形式局部性的一種重要形式 這種空間局部性將緩存未命中降到最低，因此使這種空間局部性將緩存未命中降到最低，因此使得程度獲得明顯的加速得程度獲得明顯的加速10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.4 數據局部性數據局部性for (i = 0; i n; i+) / 該程序段對向量機來該程序段對向量機來 Zi = Xi Yi;/ 說是一種優化形式說是一種優化形式 for (i = 0; i n; i+) Zi = Zi Zi;for (i = 0; i n; i+) / 有較好的數據局部性有較好的數據局部性 Zi =

56、 Xi Yi; Zi = Zi Zi;10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.4 數據局部性數據局部性 對行為主的數組對行為主的數組Z，根據空間局部性，顯然更愿，根據空間局部性，顯然更愿意逐行地給該數組元素置零意逐行地給該數組元素置零for (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; 為了獲得最好的性能，應該并行化外循環為了獲得最好的性能，應該并行化外循環 b = ceil (n/M); for (i =

57、b p; i min(n, b (p+1); i+) for (j = 0; j n; j+) Zi, j = 0;10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.4 數據局部性數據局部性 操作在數組上的數值應用的幾個重要特征操作在數組上的數值應用的幾個重要特征 數組代碼經常有許多可以并行化的循環數組代碼經常有許多可以并行化的循環 當循環有并行性時，它們的迭代可按任意次序執當循環有并行性時，它們的迭代可按任意次序執行，因而可重新安排計算次序以徹底改進數據局行，因而可重新安排計算次序以徹底改進數據局部性部性 在創建相互獨立的并行計算大單元時，串行執行在創建相互獨立的并行計算大單元時，串行執行這些單元往往會產生較好的數據局部性這些單元往往會產生較好的數據局部性10.6 并行性和數據局部性優化概述并行性和數據局部性優化概述10.6.5 矩陣乘法算法矩陣乘法算法 該算法是計算密集型的，原則上內存訪問不應該該算法是計算密集型的，