1、第十章第十章 依賴于機(jī)器的優(yōu)化依賴于機(jī)器的優(yōu)化 在指令級并行的機(jī)器上，程序的運行速度依在指令級并行的機(jī)器上，程序的運行速度依賴于下面幾個因素賴于下面幾個因素 程序中潛在的并行程序中潛在的并行 處理器上可用的并行處理器上可用的并行 從串行程序提取并行的能力從串行程序提取并行的能力 在給定的調(diào)度約束下發(fā)現(xiàn)最佳并行調(diào)度的能力在給定的調(diào)度約束下發(fā)現(xiàn)最佳并行調(diào)度的能力 并行的提取和并行執(zhí)行的調(diào)度都可以靜態(tài)地并行的提取和并行執(zhí)行的調(diào)度都可以靜態(tài)地在軟件中或動態(tài)地在硬件中完成在軟件中或動態(tài)地在硬件中完成第十章第十章 依賴于機(jī)器的優(yōu)化依賴于機(jī)器的優(yōu)化 本章內(nèi)容本章內(nèi)容 使用使用指令級并行指令級并行的基礎(chǔ)問題的

2、基礎(chǔ)問題 提取并行的數(shù)據(jù)相關(guān)性分析提取并行的數(shù)據(jù)相關(guān)性分析 代碼調(diào)度的基本概念代碼調(diào)度的基本概念 基本塊調(diào)度的技術(shù)、發(fā)現(xiàn)通用程序中的高度數(shù)據(jù)基本塊調(diào)度的技術(shù)、發(fā)現(xiàn)通用程序中的高度數(shù)據(jù)相關(guān)控制流的方法、調(diào)度數(shù)值程序的軟件流水線相關(guān)控制流的方法、調(diào)度數(shù)值程序的軟件流水線技術(shù)技術(shù) 在在多處理器系統(tǒng)多處理器系統(tǒng)上，使用數(shù)組的計算密集型程序上，使用數(shù)組的計算密集型程序的并行化和數(shù)據(jù)局部性優(yōu)化的概念和方法的并行化和數(shù)據(jù)局部性優(yōu)化的概念和方法10.1 處理器體系結(jié)構(gòu)處理器體系結(jié)構(gòu) 在考慮指令級并行時，通常想象成一個處理在考慮指令級并行時，通常想象成一個處理器在單個時鐘周期內(nèi)發(fā)射幾個操作器在單個時鐘周期內(nèi)發(fā)射

3、幾個操作 事實上，在每周期內(nèi)發(fā)射一個操作是可能的事實上，在每周期內(nèi)發(fā)射一個操作是可能的, 而指令級并行的獲得是通過使用流水線技術(shù)而指令級并行的獲得是通過使用流水線技術(shù) 本節(jié)先解釋流水線，然后討論多指令發(fā)射本節(jié)先解釋流水線，然后討論多指令發(fā)射10.1 處理器體系結(jié)構(gòu)處理器體系結(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í)行操作執(zhí)行操作EX, 訪問內(nèi)存

4、訪問內(nèi)存MEM, 回寫結(jié)果回寫結(jié)果WB5級指令流水線中級指令流水線中的的5條連續(xù)指令條連續(xù)指令 10.1 處理器體系結(jié)構(gòu)處理器體系結(jié)構(gòu)10.1.1 指令流水線和分支延遲指令流水線和分支延遲 分支延遲分支延遲 發(fā)現(xiàn)應(yīng)該執(zhí)行一個分支而不是直接后繼發(fā)現(xiàn)應(yīng)該執(zhí)行一個分支而不是直接后繼 轉(zhuǎn)向一個分支時會引起取分支目的地址指令的延轉(zhuǎn)向一個分支時會引起取分支目的地址指令的延遲并引起指令流水線遲并引起指令流水線“打嗝打嗝” 可以通過使用硬件，根據(jù)分支的執(zhí)行歷史來預(yù)測可以通過使用硬件，根據(jù)分支的執(zhí)行歷史來預(yù)測分支結(jié)果并從預(yù)測的目的地址預(yù)取指令分支結(jié)果并從預(yù)測的目的地址預(yù)取指令 分支延遲不可避免，因為分支預(yù)測會發(fā)

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

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

7、硬件自動察覺指令之間的相關(guān)性，并且在它們的操作數(shù)可用時就發(fā)射它們操作數(shù)可用時就發(fā)射它們 更復(fù)雜的調(diào)度器能夠更復(fù)雜的調(diào)度器能夠“亂序亂序”執(zhí)行指令執(zhí)行指令10.2 代碼調(diào)度的約束代碼調(diào)度的約束 代碼調(diào)度代碼調(diào)度 用在代碼生成器產(chǎn)生的機(jī)器代碼上的優(yōu)化技術(shù)用在代碼生成器產(chǎn)生的機(jī)器代碼上的優(yōu)化技術(shù) 本節(jié)討論代碼調(diào)度的約束本節(jié)討論代碼調(diào)度的約束 控制相關(guān)約束控制相關(guān)約束 在原程序中執(zhí)行的所有操作都在原程序中執(zhí)行的所有操作都必須在優(yōu)化代碼中執(zhí)行必須在優(yōu)化代碼中執(zhí)行 數(shù)據(jù)相關(guān)約束數(shù)據(jù)相關(guān)約束 優(yōu)化程序中的操作產(chǎn)生的結(jié)果優(yōu)化程序中的操作產(chǎn)生的結(jié)果必須同原程序?qū)?yīng)操作的結(jié)果一樣必須同原程序?qū)?yīng)操作的結(jié)果一樣 資

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

9、除 數(shù)據(jù)相關(guān)概念可同時用于內(nèi)存訪問和寄存器數(shù)據(jù)相關(guān)概念可同時用于內(nèi)存訪問和寄存器訪問訪問10.2 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.2 發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性 例例(1) a = 1(2) p = 2(3) x = a 語句語句(1)和和(2)可能構(gòu)成輸出相關(guān)可能構(gòu)成輸出相關(guān) 語句語句(1)和和(3)可能構(gòu)成真相關(guān)可能構(gòu)成真相關(guān) 語句語句(2)和和(3)可能構(gòu)成真相關(guān)可能構(gòu)成真相關(guān) 除非編譯器知道除非編譯器知道p不可能指向不可能指向a，否則，否則3個操作必個操作必須串行執(zhí)行須串行執(zhí)行10.2 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.2 發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性發(fā)現(xiàn)內(nèi)存

10、訪問中的相關(guān)性 發(fā)現(xiàn)數(shù)據(jù)相關(guān)需要不同形式的分析發(fā)現(xiàn)數(shù)據(jù)相關(guān)需要不同形式的分析 數(shù)組元素間的別名分析數(shù)組元素間的別名分析Ai和和Aj是否互為別名是否互為別名 指針別名分析指針別名分析若若p和和q相等，則相等，則 p和和 q、p-next和和q-next、p-data和和q-data等都分別互為別名等都分別互為別名 過程間分析過程間分析引用調(diào)用場合：形參和形參之間、形參和全局變引用調(diào)用場合：形參和形參之間、形參和全局變量之間因?qū)崊⒍鸹閯e名量之間因?qū)崊⒍鸹閯e名10.2 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷寄存器使用和并行執(zhí)行之間的折衷例：例：(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若瞄準(zhǔn)極小化寄存器若瞄準(zhǔn)極小化寄存器的使用個數(shù)，則只需的使用個數(shù)，則只需使用使用3個寄存器個寄存器 10.2 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷寄存器使用和并行執(zhí)行之間的折衷例：例：(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 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.3 寄存器使用和并行執(zhí)行之間的折衷寄存器使用和并行執(zhí)行之間的折衷例：例：(a + b) + c + (d + e)+e+c+ab+d如果對每個中間結(jié)果如果對每個中間結(jié)果使用不同寄存器，則使用不同寄存器，則完成計算只需要完成計算只需要4步步R1 = aR6 = R1+R2R8 = R6+R3R9 = R8+R7R2 = bR7 = R4+R5R3 = cR4 = d R5 = e10.2 代碼

13、調(diào)度的約束代碼調(diào)度的約束 10.2.4 寄存器分配和代碼調(diào)度的次序安排寄存器分配和代碼調(diào)度的次序安排 先寄存器分配先寄存器分配 結(jié)果代碼中會有很多存儲相關(guān)結(jié)果代碼中會有很多存儲相關(guān) 非數(shù)值應(yīng)用本質(zhì)上沒有多少并行，采用這種方式非數(shù)值應(yīng)用本質(zhì)上沒有多少并行，采用這種方式 先代碼調(diào)度先代碼調(diào)度 導(dǎo)致寄存器溢出，抵消指令級并行的優(yōu)點導(dǎo)致寄存器溢出，抵消指令級并行的優(yōu)點 適用于有許多大表達(dá)式的數(shù)值應(yīng)用適用于有許多大表達(dá)式的數(shù)值應(yīng)用 在假定偽寄存器就是物理寄存器情況下，先調(diào)度在假定偽寄存器就是物理寄存器情況下，先調(diào)度指令，然后寄存器分配，把處理寄存器溢出的代指令，然后寄存器分配，把處理寄存器溢出的代碼附加

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

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

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

17、 c + d; CMOVZ R2, R3, R1假定假定a、b、c和和d分別被分配了分別被分配了R1、R2、R4和和R5可用來將相鄰基本塊組合成一個更大基本塊可用來將相鄰基本塊組合成一個更大基本塊10.2 代碼調(diào)度的約束代碼調(diào)度的約束 10.2.7 一個基本的機(jī)器模型一個基本的機(jī)器模型 機(jī)器模型機(jī)器模型M = (R, T) T：操作類型集，如讀取、存儲和算術(shù)運算等：操作類型集，如讀取、存儲和算術(shù)運算等 R = r1, r2, ：硬件資源向量集，如內(nèi)存訪問部：硬件資源向量集，如內(nèi)存訪問部件、算術(shù)運算部件和浮點功能部件件、算術(shù)運算部件和浮點功能部件ri代表第代表第i類資源中可用的部件數(shù)類資源中可用

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

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

20、型的資源預(yù)留表的操作類型的資源預(yù)留表 每條邊每條邊e都標(biāo)示有延遲都標(biāo)示有延遲de，表示，表示e的目的結(jié)點必須的目的結(jié)點必須在它源結(jié)點發(fā)射在它源結(jié)點發(fā)射de個時鐘周期之后才可以發(fā)射個時鐘周期之后才可以發(fā)射10.3 基基 本本 塊塊 調(diào)調(diào) 度度數(shù)據(jù)依賴圖數(shù)據(jù)依賴圖資源預(yù)留表資源預(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操作是全流水操作是全流水的，只需顯示的

21、，只需顯示在第在第1行使用行使用的資源的資源 10.3 基基 本本 塊塊 調(diào)調(diào) 度度10.3.2 基本塊的表調(diào)度基本塊的表調(diào)度 關(guān)鍵路徑包括最后關(guān)鍵路徑包括最后5個結(jié)點，故第個結(jié)點，故第3條指令先調(diào)度條指令先調(diào)度 再調(diào)度第再調(diào)度第1條指令，因為第條指令，因為第4條指令還需等條指令還需等1周期周期 第第4周期調(diào)度周期調(diào)度2條條資源預(yù)留表資源預(yù)留表alu men調(diào)度表調(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)調(diào) 度度10.

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

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

24、的問題先用例子展示操作在基本塊之間移動涉及的問題 L:if (a = 0) goto Lc = be = d + d(a) 源代碼源代碼(b) 局部調(diào)度的機(jī)器代碼局部調(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)度全局代碼調(diào)度 假定假定a, b, c, d和和e的地址不同，分別保存在的地址不同，分別保存在R1到到R5 由于數(shù)據(jù)相關(guān)，塊內(nèi)的指令必須串行執(zhí)行，且插由于數(shù)據(jù)相關(guān)，塊內(nèi)的指令必須串行執(zhí)行，且

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

26、 be = d + d(a) 源代碼源代碼(b) 局部調(diào)度的機(jī)器代碼局部調(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)度全局代碼調(diào)度 B3肯定要執(zhí)行，因而可以和肯定要執(zhí)行，因而可以和B1并行執(zhí)行并行執(zhí)行 B2的讀取操作在執(zhí)行的讀取操作在執(zhí)行B1時投機(jī)地完成時投機(jī)地完成 B2的存儲操作放到的存儲操作放到B3的的一份拷貝中一份拷貝中L:if (a = 0) goto Lc = be = d + d(a)

27、 源代碼源代碼(b) 局部調(diào)度的機(jī)器代碼局部調(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)度全局代碼調(diào)度L:全局調(diào)度前后的流圖全局調(diào)度前后的流圖if (a = 0) goto Lc = be = d + d(a) 源代碼源代碼ST 0(R5), R8(b) 局部調(diào)度的機(jī)器代碼局部調(diào)度的機(jī)器代碼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) 全局調(diào)度的機(jī)器代碼全局調(diào)度的機(jī)器代碼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 全局代碼調(diào)度全局代碼調(diào)度 基本塊之間的基本塊之間的支配關(guān)系支配關(guān)系指令在基本塊之間的移動因支配關(guān)系不同而不同指令在基本塊之間的移動因支配關(guān)系不同而不同 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 全局代碼調(diào)度全局代碼調(diào)度10.4.2 向上的代碼移動向上的代碼移動從塊從塊src向上移動到塊向上移動到塊dst，假定移動未違反數(shù)據(jù)相，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過關(guān)，并使得通過dst到到src的路徑運行得較快的路徑運行得較快 若若dst和和src等價，則被移動操作應(yīng)該被執(zhí)行時，它等價，則

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

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

32、.4 全局代碼調(diào)度全局代碼調(diào)度10.4.3 向下的代碼移動向下的代碼移動從塊從塊src向下移動到塊向下移動到塊dst，假定移動未違反數(shù)據(jù)相，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過關(guān)，并使得通過dst到到src的路徑運行得較快的路徑運行得較快 若若dst和和src等價，則被移動操作應(yīng)該被執(zhí)行時，它等價，則被移動操作應(yīng)該被執(zhí)行時，它正好僅被執(zhí)行一次正好僅被執(zhí)行一次srcdst10.4 全局代碼調(diào)度全局代碼調(diào)度10.4.3 向下的代碼移動向下的代碼移動從塊從塊src向下移動到塊向下移動到塊dst，假定移動未違反數(shù)據(jù)相，假定移動未違反數(shù)據(jù)相關(guān)，并使得通過關(guān)，并使得通過dst到到src的路徑運行得較快的路徑

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

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

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

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

37、要更經(jīng)常(3)看守程序出口或異常處理例程的分支語句很看守程序出口或異常處理例程的分支語句很少被執(zhí)行少被執(zhí)行 最好的頻率估計來自動態(tài)剖析，程序被靜態(tài)插樁最好的頻率估計來自動態(tài)剖析，程序被靜態(tài)插樁以用來運行時記錄條件分支每次的走向以用來運行時記錄條件分支每次的走向10.4 全局代碼調(diào)度全局代碼調(diào)度10.4.5 全局調(diào)度的其他問題全局調(diào)度的其他問題 最簡單的全局調(diào)度算法也相當(dāng)復(fù)雜，不介紹最簡單的全局調(diào)度算法也相當(dāng)復(fù)雜，不介紹 在一些全局調(diào)度算法中，循環(huán)迭代的邊界是代碼移在一些全局調(diào)度算法中，循環(huán)迭代的邊界是代碼移動的一種屏障，需循環(huán)展開動的一種屏障，需循環(huán)展開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 全局代碼調(diào)度全局代碼調(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)度器的優(yōu)點是可以根據(jù)運行時的情況建立新動態(tài)調(diào)度器的優(yōu)點是可以根據(jù)運行時的情況建立新的調(diào)度表，無需事先編碼所有可能的調(diào)度表的調(diào)度表，無需事先編碼所有可能的調(diào)度表10.4 全局代碼調(diào)度全局代碼調(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)度情況下，靜態(tài)調(diào)

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

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

41、舉例10.5 軟軟 件件 流流 水水 每次調(diào)度一個迭代的結(jié)果見右邊每次調(diào)度一個迭代的結(jié)果見右邊f(xié)or (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周期，只有循周期，只有循環(huán)回跳指令和迭環(huán)回跳指令和迭代中最后一條指代中最

42、后一條指令重疊令重疊 10.5 軟軟 件件 流流 水水 循環(huán)展開循環(huán)展開4次迭代的調(diào)度結(jié)果見右邊次迭代的調(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)被流水化該循環(huán)被流水化Di = Ai Bi + c;for (i = N2; i N; i +)/ 不需要優(yōu)化不需要優(yōu)化Di = Ai Bi + c;10.5 軟軟 件件 流流 水水 10.5.4 Do-Across循環(huán)循環(huán)軟件流水也可以用到迭代之間存在數(shù)據(jù)相關(guān)的循軟件流水也可以用到迭代之間存在數(shù)據(jù)相關(guān)的循環(huán)，這樣的循環(huán)叫做

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

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

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

46、i +)Ai = Bi + Ai 2寫寫Ai和讀和讀Ai 2的依賴邊上標(biāo)記的迭代次數(shù)差的依賴邊上標(biāo)記的迭代次數(shù)差是是210.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述 并行編程模型并行編程模型 任務(wù)并行任務(wù)并行 數(shù)據(jù)并行數(shù)據(jù)并行 流水線并行（前面幾節(jié)涉及較多）流水線并行（前面幾節(jié)涉及較多） 本節(jié)內(nèi)容圍繞任務(wù)并行和數(shù)據(jù)并行本節(jié)內(nèi)容圍繞任務(wù)并行和數(shù)據(jù)并行 介紹并行計算機(jī)系統(tǒng)結(jié)構(gòu)的概況介紹并行計算機(jī)系統(tǒng)結(jié)構(gòu)的概況 給出并行化的基本概念，程序循環(huán)的變換，還有給出并行化的基本概念，程序循環(huán)的變換，還有對并行化有用的概念對并行化有用的概念 類似的考慮怎樣用于優(yōu)化數(shù)據(jù)局部性類似的考慮怎樣用于優(yōu)

47、化數(shù)據(jù)局部性 以矩陣乘算法的優(yōu)化為例以矩陣乘算法的優(yōu)化為例 10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1 多處理器多處理器 對稱多處理器的體系結(jié)構(gòu)對稱多處理器的體系結(jié)構(gòu)二級二級緩存緩存內(nèi)存內(nèi)存總線總線二級二級緩存緩存二級二級緩存緩存二級二級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存一級一級緩存緩存處理器處理器處理器處理器處理器處理器處理器處理器多個高性多個高性能處理器能處理器集成在一集成在一塊芯片上塊芯片上10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1 多處理器多處理器 對稱多處理器的體系結(jié)構(gòu)對稱多處理器的體系結(jié)構(gòu)二級二級

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

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

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

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

52、時的應(yīng)用一般都使用大數(shù)組，導(dǎo)致程序中出現(xiàn)有許多次迭代的循環(huán)，這些迭代經(jīng)常相互獨立，可有許多次迭代的循環(huán)，這些迭代經(jīng)常相互獨立，可以把這類循環(huán)的大量迭代分到各處理器上以把這類循環(huán)的大量迭代分到各處理器上10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3 循環(huán)級并行循環(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 = b p; i min(n, b (p+1); i+) Zi = Xi Yi;Z

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

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

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

56、 Xi Yi; Zi = Zi Zi;10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性數(shù)據(jù)局部性 對行為主的數(shù)組對行為主的數(shù)組Z，根據(jù)空間局部性，顯然更愿，根據(jù)空間局部性，顯然更愿意逐行地給該數(shù)組元素置零意逐行地給該數(shù)組元素置零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; 為了獲得最好的性能，應(yīng)該并行化外循環(huán)為了獲得最好的性能，應(yīng)該并行化外循環(huán) 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 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4 數(shù)據(jù)局部性數(shù)據(jù)局部性 操作在數(shù)組上的數(shù)值應(yīng)用的幾個重要特征操作在數(shù)組上的數(shù)值應(yīng)用的幾個重要特征 數(shù)組代碼經(jīng)常有許多可以并行化的循環(huán)數(shù)組代碼經(jīng)常有許多可以并行化的循環(huán) 當(dāng)循環(huán)有并行性時，它們的迭代可按任意次序執(zhí)當(dāng)循環(huán)有并行性時，它們的迭代可按任意次序執(zhí)行，因而可重新安排計算次序以徹底改進(jìn)數(shù)據(jù)局行，因而可重新安排計算次序以徹底改進(jìn)數(shù)據(jù)局部性部性 在創(chuàng)建相互獨立的并行計算大單元時，串行執(zhí)行在創(chuàng)建相互獨立的并行計算大單元時，串行執(zhí)行這些單元往往會產(chǎn)生較好的數(shù)據(jù)局部性這些單元往往會產(chǎn)生較好的數(shù)據(jù)局部性10.6 并行性和數(shù)據(jù)局部性優(yōu)化概述并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5 矩陣乘法算法矩陣乘法算法 該算法是計算密集型的，原則上內(nèi)存訪問不應(yīng)該該算法是計算密集型的，