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

第十章依賴于機(jī)器的優(yōu)化在指令級(jí)并行的機(jī)器上，程序的運(yùn)行速度依賴于下面幾個(gè)因素

程序中潛在的并行處理器上可用的并行從串行程序提取并行的能力

在給定的調(diào)度約束下發(fā)現(xiàn)最佳并行調(diào)度的能力并行的提取和并行執(zhí)行的調(diào)度都可以靜態(tài)地在軟件中或動(dòng)態(tài)地在硬件中完成第十章依賴于機(jī)器的優(yōu)化在指令級(jí)并行的機(jī)器上，程序的運(yùn)行速第十章依賴于機(jī)器的優(yōu)化本章內(nèi)容使用指令級(jí)并行的基礎(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)化的概念和方法第十章依賴于機(jī)器的優(yōu)化本章內(nèi)容10.1處理器體系結(jié)構(gòu)在考慮指令級(jí)并行時(shí)，通常想象成一個(gè)處理器在單個(gè)時(shí)鐘周期內(nèi)發(fā)射幾個(gè)操作事實(shí)上，在每周期內(nèi)發(fā)射一個(gè)操作是可能的,而指令級(jí)并行的獲得是通過使用流水線技術(shù)本節(jié)先解釋流水線，然后討論多指令發(fā)射10.1處理器體系結(jié)構(gòu)在考慮指令級(jí)并行時(shí)，通常想象成一個(gè)10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲

i i+1 i+2 i+3 i+41. IF2. ID IF3. EX ID IF4. MEM EX ID IF5. WB MEM EX ID IF6. WB MEM EX ID7. WB MEM EX8. WB MEM9. WB取指令I(lǐng)F,譯碼ID,執(zhí)行操作EX,訪問內(nèi)存MEM,回寫結(jié)果WB5級(jí)指令流水線中的5條連續(xù)指令10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲分支延遲發(fā)現(xiàn)應(yīng)該執(zhí)行一個(gè)分支而不是直接后繼轉(zhuǎn)向一個(gè)分支時(shí)會(huì)引起取分支目的地址指令的延遲并引起指令流水線“打嗝”可以通過使用硬件，根據(jù)分支的執(zhí)行歷史來預(yù)測(cè)分支結(jié)果并從預(yù)測(cè)的目的地址預(yù)取指令分支延遲不可避免，因?yàn)榉种ьA(yù)測(cè)會(huì)發(fā)生偏差10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲10.1處理器體系結(jié)構(gòu)10.1.2流水化的執(zhí)行 如果不依賴一條指令結(jié)果的隨后指令在該結(jié)果產(chǎn)生前就被允許執(zhí)行有些指令的執(zhí)行需要幾個(gè)周期，幾個(gè)操作同時(shí)出現(xiàn)在它們的執(zhí)行級(jí)上可能的如果最長(zhǎng)的執(zhí)行流水線是n級(jí)，n個(gè)操作同時(shí)進(jìn)行的可能性是存在的并非所有的指令都能被完全流水化，例如浮點(diǎn)除通用處理器大都動(dòng)態(tài)察覺相繼指令之間的依賴性嵌入式系統(tǒng)把數(shù)據(jù)相關(guān)性的檢查交給軟件10.1處理器體系結(jié)構(gòu)10.1.2流水化的執(zhí)行10.1處理器體系結(jié)構(gòu)10.1.3多指令發(fā)射

每周期發(fā)射幾個(gè)操作，讓更多操作同時(shí)進(jìn)行超長(zhǎng)指令字機(jī)器將若干個(gè)操作編碼在單周期中發(fā)射編譯器需要確定哪些操作可以并行發(fā)射超標(biāo)量機(jī)器超標(biāo)量機(jī)器有按普通順序執(zhí)行語義的正規(guī)指令集硬件自動(dòng)察覺指令之間的相關(guān)性，并且在它們的操作數(shù)可用時(shí)就發(fā)射它們更復(fù)雜的調(diào)度器能夠“亂序”執(zhí)行指令10.1處理器體系結(jié)構(gòu)10.1.3多指令發(fā)射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)度的約束代碼調(diào)度10.2代碼調(diào)度的約束

10.2.1數(shù)據(jù)相關(guān)真相關(guān) 如果對(duì)同一個(gè)單元先寫后讀，那么讀依賴于所寫的值反相關(guān)

如果對(duì)同一個(gè)單元先讀后寫?？梢酝ㄟ^把值存在不同的單元來刪除反相關(guān)輸出相關(guān)

如果對(duì)同一個(gè)單元先后寫兩次。也可刪除數(shù)據(jù)相關(guān)概念可同時(shí)用于內(nèi)存訪問和寄存器訪問10.2代碼調(diào)度的約束10.2.1數(shù)據(jù)相關(guān)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)存訪問中的相10.2代碼調(diào)度的約束

10.2.2發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性發(fā)現(xiàn)數(shù)據(jù)相關(guān)需要不同形式的分析數(shù)組元素間的別名分析 A[i]和A[j]是否互為別名指針別名分析 若p和q相等，則p和q、p->next和q->next、 p->data和q->data等都分別互為別名過程間分析 引用調(diào)用場(chǎng)合：形參和形參之間、形參和全局變量之間因?qū)崊⒍鸹閯e名10.2代碼調(diào)度的約束10.2.2發(fā)現(xiàn)內(nèi)存訪問中的相10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 若瞄準(zhǔn)極小化寄存器的使用個(gè)數(shù)，則只需使用3個(gè)寄存器10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 完成整個(gè)計(jì)算需要7步10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e)

+e+c+ab+d

如果對(duì)每個(gè)中間結(jié)果使用不同寄存器，則完成計(jì)算只需要4步R1=aR6=R1+R2R8=R6+R3R9=R8+R7R2=bR7=R4+R5R3=cR4=dR5=e10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

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

10.2.5控制相關(guān)

在非數(shù)值計(jì)算中，基本塊非常小，其中的操作通常高度相關(guān)，幾乎不能并行調(diào)查跨基本塊的并行是至關(guān)重要的若一條指令很可能被執(zhí)行且有空閑的資源可“免費(fèi)”用于完成該指令的操作，則可以投機(jī)地執(zhí)行該指令；若投機(jī)成功，則程序運(yùn)行得快一些例 if(a>t) b=aa依賴于比較a>t的結(jié)果

b=aa; 若aa不會(huì)產(chǎn)生副作用，則 d=a+c; aa可以投機(jī)地執(zhí)行10.2代碼調(diào)度的約束10.2.5控制相關(guān)10.2代碼調(diào)度的約束

10.2.6投機(jī)執(zhí)行的支持內(nèi)存讀取是一類使用頻繁，且能從投機(jī)執(zhí)行大大獲益的指令但在if(p!=null) q=p 中，投機(jī)地對(duì)p脫引用將引起該程序因p等于null而錯(cuò)誤地停止許多高性能處理器提供專門的特性來支持投機(jī)地內(nèi)存訪問10.2代碼調(diào)度的約束10.2.6投機(jī)執(zhí)行的支持10.2代碼調(diào)度的約束

10.2.6投機(jī)執(zhí)行的支持預(yù)取指令 在數(shù)據(jù)使用前將其從內(nèi)存取到緩存,若該單元無效或訪問它會(huì)引起缺頁，則忽略

抑制位 允許投機(jī)地從內(nèi)存將數(shù)據(jù)讀取到寄存器堆，若出現(xiàn)非法內(nèi)存訪問或缺頁，則設(shè)置目標(biāo)寄存器的抑制位判定指令 在判定條件為真時(shí)才執(zhí)行的指令 例if(a==0) 翻譯成ADDR3,R4,R5 b=c+d; CMOVZR2,R3,R1 假定a、b、c和d分別被分配了R1、R2、R4和R5

可用來將相鄰基本塊組合成一個(gè)更大基本塊10.2代碼調(diào)度的約束10.2.6投機(jī)執(zhí)行的支持10.2代碼調(diào)度的約束

10.2.7一個(gè)基本的機(jī)器模型機(jī)器模型M=(R,T)T：操作類型集，如讀取、存儲(chǔ)和算術(shù)運(yùn)算等R=[r1,r2,…]：硬件資源向量集，如內(nèi)存訪問部件、算術(shù)運(yùn)算部件和浮點(diǎn)功能部件 ri代表第i類資源中可用的部件數(shù)每個(gè)操作有一組輸入操作數(shù)、一組輸出操作數(shù)和一個(gè)資源需求和每個(gè)輸入操作數(shù)相關(guān)的是一個(gè)輸入延遲和每個(gè)輸出操作數(shù)相關(guān)的是一個(gè)輸出延遲10.2代碼調(diào)度的約束10.2.7一個(gè)基本的機(jī)器模型10.2代碼調(diào)度的約束

10.2.7一個(gè)基本的機(jī)器模型機(jī)器模型M=(R,T)對(duì)每種操作類型t，資源使用由一張二維資源預(yù)留表RTt來建模條目RTt[i,j]是t類型的一個(gè)操作在它被發(fā)射i時(shí)鐘周期后，使用第j種資源的部件數(shù)對(duì)任何t、i和j，RTt[i,j]必須小于或等于R[j]10.2代碼調(diào)度的約束10.2.7一個(gè)基本的機(jī)器模型10.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和邊集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)度10.3.1數(shù)據(jù)依賴10.3基本塊調(diào)度數(shù)據(jù)依賴圖資源預(yù)留表alumenLDR2,0(R1)ST4(R1),R2LDR3,8(R1)ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3222111111i1i2i3i4i5i6i7灰色表示1

白色表示0操作是全流水的，只需顯示在第1行使用的資源

10.3基本塊調(diào)度數(shù)據(jù)依賴圖資源預(yù)留表a10.3基本塊調(diào)度10.3.2基本塊的表調(diào)度關(guān)鍵路徑包括最后5個(gè)結(jié)點(diǎn)，故第3條指令先調(diào)度再調(diào)度第1條指令，因?yàn)榈?條指令還需等1周期第4周期調(diào)度2條資源預(yù)留表alumen調(diào)度表LDR3,8(R1)

ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3ST4(R1),R2

LDR2,0(R1)

10.3基本塊調(diào)度10.3.2基本塊的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.3基本塊調(diào)度10.3.2基本塊的10.4全局代碼調(diào)度對(duì)于有適度指令級(jí)并行的機(jī)器，僅對(duì)每個(gè)基本塊進(jìn)行緊湊調(diào)度會(huì)引起許多資源空閑全局調(diào)度：為了更好地利用機(jī)器資源，需要考慮把指令從一個(gè)基本塊移到另一個(gè)基本塊的代碼生成策略 必須保證原來程序中所有指令在優(yōu)化程序中都被執(zhí)行當(dāng)優(yōu)化程序可以投機(jī)地執(zhí)行額外指令時(shí)，這些指令肯定不能有任何多余的副作用10.4全局代碼調(diào)度對(duì)于有適度指令級(jí)并行的機(jī)器，僅對(duì)每個(gè)10.4全局代碼調(diào)度10.4.1簡(jiǎn)單的代碼移動(dòng)先用例子展示操作在基本塊之間移動(dòng)涉及的問題

L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度10.4.1簡(jiǎn)單的代碼移動(dòng)L:if10.4全局代碼調(diào)度假定a,b,c,d和e的地址不同，分別保存在R1到R5由于數(shù)據(jù)相關(guān)，塊內(nèi)的指令必須串行執(zhí)行，且插入NOPL:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度假定a,b,c,d和e的地址不10.4全局代碼調(diào)度假定機(jī)器在一個(gè)時(shí)鐘周期執(zhí)行任意的兩個(gè)操作讀取操作有2周期的延遲，其他指令1周期的延遲L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度假定機(jī)器在一個(gè)時(shí)鐘周期執(zhí)行任意的兩個(gè)10.4全局代碼調(diào)度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)行B2的讀取操作在執(zhí)行B1時(shí)投機(jī)地完成B2的存儲(chǔ)操作放到B3的 一份拷貝中L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)10.4全局代碼調(diào)度L:全局調(diào)度前后的流圖if(a==0)gotoLc=be=d+d(a)源代碼ST0(R5),R8(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1), LDR8,0(R4)LDR7,0(R2)ADDR8,R8,R8,BEQZR6,LST0(R5),R8, ST0(R3),R7L:(c)全局調(diào)度的機(jī)器代碼B1B3B3LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度L:全局調(diào)度前后的流圖if(a=10.4全局代碼調(diào)度基本塊之間的支配關(guān)系指令在基本塊之間的移動(dòng)因支配關(guān)系不同而不同B1和B3控制等價(jià)：B1支配B3， B3后支配B1B1支配B2， 但是B2并非后支配B1B2不支配B3， 但是B3后支配B2LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

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

dstsrc10.4全局代碼調(diào)度10.4.2向上的代碼移動(dòng)dsts10.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng) 從塊src向下移動(dòng)到塊dst，假定移動(dòng)未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次srcdst10.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng)srcd10.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng) 從塊src向下移動(dòng)到塊dst，假定移動(dòng)未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次src未后支配dst,向下移動(dòng)的代碼經(jīng)常是存儲(chǔ)操作,復(fù)制從src到dst路徑上的各塊，并把 被移動(dòng)操作僅放置在dst的新拷貝中srcdst10.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng)srcd10.4全局代碼調(diào)度9.5節(jié)的例子可作為參考B1B2B3B4a=b+cB5B6B7d=b+cB1B2B3B4t=b+ca=tB4B5d=td=b+cB6B6B710.4全局代碼調(diào)度9.5節(jié)的例子可作為參考B1B2B310.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng) 從塊src向下移動(dòng)到塊dst，假定移動(dòng)未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次src未后支配dst,向下移動(dòng)的代碼經(jīng)常是存儲(chǔ)操作,復(fù)制從src到dst路徑上的各塊，并把 被移動(dòng)操作僅放置在dst的新拷貝中dst沒有后支配src，插入補(bǔ)償代碼以保證被移動(dòng)操作在不經(jīng)dst路徑上也執(zhí)行srcdst10.4全局代碼調(diào)度10.4.3向下的代碼移動(dòng)srcd10.4全局代碼調(diào)度10.4.4更新數(shù)據(jù)相關(guān) 代碼移動(dòng)會(huì)改變操作之間的數(shù)據(jù)相關(guān)關(guān)系兩個(gè)對(duì)x的賦值之一可以移動(dòng)到最上面的基本塊，該變換能維持原來程序中的所有相關(guān)性一旦一個(gè)對(duì)x的賦值被上移，另一個(gè)就不能移動(dòng)了移動(dòng)使得x在最上面塊的出口 由不活躍變成活躍一個(gè)變量在某個(gè)程序點(diǎn) 活躍，則就不能把對(duì)它的投機(jī) 定值移到該點(diǎn)的上面x=1x=210.4全局代碼調(diào)度10.4.4更新數(shù)據(jù)相關(guān)x=110.4全局代碼調(diào)度10.4.5全局調(diào)度的其他問題

程序調(diào)度應(yīng)該使經(jīng)常執(zhí)行的路徑運(yùn)行得快一些， 不經(jīng)常執(zhí)行的路徑可能會(huì)因調(diào)度變得慢一些編譯器可用來估計(jì)執(zhí)行頻率的技術(shù)有若干種

(1)內(nèi)循環(huán)比外循環(huán)執(zhí)行得更頻繁

(2)分支指令往回跳轉(zhuǎn)比不跳轉(zhuǎn)要更經(jīng)常 (3)看守程序出口或異常處理例程的分支語句很少被執(zhí)行最好的頻率估計(jì)來自動(dòng)態(tài)剖析，程序被靜態(tài)插樁以用來運(yùn)行時(shí)記錄條件分支每次的走向10.4全局代碼調(diào)度10.4.5全局調(diào)度的其他問題10.4全局代碼調(diào)度10.4.5全局調(diào)度的其他問題最簡(jiǎn)單的全局調(diào)度算法也相當(dāng)復(fù)雜，不介紹在一些全局調(diào)度算法中，循環(huán)迭代的邊界是代碼移動(dòng)的一種屏障，需循環(huán)展開for(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.5全局調(diào)度的其他問題10.4全局代碼調(diào)度10.4.6靜態(tài)調(diào)度器和動(dòng)態(tài)調(diào)度器的相互影響動(dòng)態(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)度器和動(dòng)態(tài)調(diào)度器10.4全局代碼調(diào)度10.4.6靜態(tài)調(diào)度器和動(dòng)態(tài)調(diào)度器的相互影響存在動(dòng)態(tài)調(diào)度情況下，靜態(tài)調(diào)度器的作用保證盡早地取高延遲的指令，使得動(dòng)態(tài)調(diào)度器能夠盡早發(fā)射它們盡早安排預(yù)取指令，使數(shù)據(jù)到要用時(shí)已經(jīng)在緩存,或盡早安排可能不命中緩存的操作只需要給數(shù)據(jù)相關(guān)的操作安排正確的次序，無需通過極小化延遲來分離每一對(duì)數(shù)據(jù)相關(guān)的操作給分支預(yù)測(cè)指令較高優(yōu)先級(jí)，以減少預(yù)測(cè)錯(cuò)誤的代價(jià)10.4全局代碼調(diào)度10.4.6靜態(tài)調(diào)度器和動(dòng)態(tài)調(diào)度器10.5軟件流水

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

每次調(diào)度一個(gè)迭代的結(jié)果見右邊f(xié)or(i=0;i<n;i++) //R1,R2,R3=&A,&B,&D

D[i]=A[i]B[i]+c;

//R4 =c //R10 =n1 L:LDR5,0(R1++) LDR6,0(R2++) MULR7,R5,R6 NOP ADDR8,R7,R4 NOP ST0(R3++),R8,BLR10,L該計(jì)算大部分是串行的，它需要7周期，只有循環(huán)回跳指令和迭代中最后一條指令重疊10.5軟件流水每次調(diào)度一個(gè)迭代的結(jié)果見右10.5軟件流水

循環(huán)展開4次迭代的調(diào)度結(jié)果見右邊f(xié)or(i=0;i<n;i++) L: LD

D[i]=A[i]B[i]+c;

LD

LD MUL LD MUL LD ADD LD ADD LD ST MUL LD ST MUL ADD ADD ST ST BL(L)

展開后每次迭代的執(zhí)行用13周期，或者說原來的每次迭代僅需要3.25周期忽略了寄存器分配的細(xì)節(jié)10.5軟件流水循環(huán)展開4次迭代的調(diào)度結(jié)果10.5軟件流水

周期

j=1 j=2 j=3 j=4 j=5

(1) LD (2) LD (3) MUL LD (4) LD (5) MUL LD (6) ADD LD (7) MUL LD (8) ST ADD LD (9) MUL LD (10) ST ADD LD (11) MUL (12) ST ADD (13) (14) ST ADD (15) (16) ST 不考慮寄存器分配10.5.2循環(huán)的軟件流水右邊是展開5次的迭代調(diào)度滿足所有的資源和數(shù)據(jù)相關(guān)約束第7和8周期執(zhí)行的操作同第9和10周期執(zhí)行的是一樣的10.5軟件流水 周期 j=1 10.5軟件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考慮寄存器分配10.5.2循環(huán)的軟件流水右邊是經(jīng)軟件流水化的代碼每行對(duì)應(yīng)到一條機(jī)器指令第7和第8兩行構(gòu)成一個(gè)2時(shí)鐘的循環(huán)，重復(fù)執(zhí)行n3次10.5軟件流水 (1) LD不考慮10.5軟件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考慮寄存器分配10.5.2循環(huán)的軟件流水右邊是經(jīng)軟件流水化的代碼當(dāng)一個(gè)老的迭代在該流水線上撤出，一個(gè)新的迭代填入當(dāng)所有迭代都填完，該流水線排空10.5軟件流水 (1) LD不考慮10.5軟件流水

(1) LD (2) LD (3) MULLD (4) LD (5) MUL LD (6) ADD LD (7)L: MULLD (8) ST ADD LD BL(L) (9) MUL (10) ST ADD (11) (12) ST ADD (13) (14) ST 不考慮寄存器分配10.5.2循環(huán)的軟件流水右邊是經(jīng)軟件流水化的代碼第1到6行的指令序列叫序曲第7和8行叫做穩(wěn)定狀態(tài)第9到14行指令序列叫做尾聲

10.5軟件流水 (1) LD不考慮10.5軟件流水

周期

j=1 j=2 j=3 j=4 j=5

(1) LD (2) LD (3) MUL LD (4) LD (5) MUL LD (6) ADD LD (7) MUL LD (8) ST ADD LD (9) MUL LD (10) ST ADD LD (11) MUL (12) ST ADD (13) (14) ST ADD (15) (16) ST 10.5.3寄存器分配和代碼生成第1次迭代乘運(yùn)算的結(jié)果在第3周期產(chǎn)生，在第6周期使用第2次迭代結(jié)果在第5周期產(chǎn)生，第8周期用結(jié)果必須保存在不同寄存器10.5軟件流水 周期 j=1 10.5軟件流水

10.5.3寄存器分配和代碼生成 奇數(shù)次迭代和偶數(shù)次迭代的代碼不完全一樣，所以進(jìn)入穩(wěn)定狀態(tài)后的循環(huán)由2周期加倍成4周期用源代碼解釋，相當(dāng)于下面的循環(huán)if(N>=5) N2=1+2((N1)/2);else N2=0;for(i=0;i<N2;i++) //該循環(huán)被流水化 D[i]=A[i]B[i]+c;for(i=N2;i<N;i++) //不需要優(yōu)化 D[i]=A[i]B[i]+c;10.5軟件流水10.5.3寄存器分配和10.5軟件流水

10.5.4Do-Across循環(huán) 軟件流水也可以用到迭代之間存在數(shù)據(jù)相關(guān)的循環(huán)，這樣的循環(huán)叫做do-across循環(huán)

for(i=0;i<n;i++){ sum=sum+A[i]; B[i]=A[i]b; }該循環(huán)的執(zhí)行不可能快于每2周期1次迭代即使有更多的加法器或乘法器，也不可能更快吞吐能力受到穿越迭代的數(shù)據(jù)相關(guān)鏈的限制10.5軟件流水10.5.4Do-Acr10.5軟件流水

10.5.5軟件流水的目標(biāo)和約束目標(biāo)基本目標(biāo)是極大化耗時(shí)較長(zhǎng)的循環(huán)的吞吐能力次要目標(biāo)是保持所產(chǎn)生代碼的規(guī)模較小達(dá)到目標(biāo)的體現(xiàn)軟件流水化的循環(huán)應(yīng)該有較小的流水線穩(wěn)定狀態(tài)實(shí)現(xiàn)策略讓每次迭代的相對(duì)調(diào)度都相同，并且這些迭代以同樣的時(shí)間間隔逐步啟動(dòng)10.5軟件流水10.5.5軟件流水的目10.5軟件流水

10.5.5軟件流水的目標(biāo)和約束資源約束令機(jī)器資源由R=[r1,r2,...]表示，其中ri是第i類資源可用部件數(shù)若循環(huán)的一次迭代需要第i類資源ni個(gè)部件流水化循環(huán)的平均啟動(dòng)間隔至少是maxi(ni/ri)周期如果maxi(ni/ri)小于1，則將源代碼展開幾次是有用的10.5軟件流水10.5.5軟件流水的目10.5軟件流水

10.5.5軟件流水的目標(biāo)和約束數(shù)據(jù)相關(guān)一個(gè)操作可能依賴于前一次迭代中同樣操作的結(jié)果，不同于到目前為止碰到的數(shù)據(jù)相關(guān)僅用延遲來標(biāo)記邊不夠用，需要區(qū)別不同迭代中同一操作的實(shí)例，例如：

for(i=2;i<n;i++) A[i]=B[i]+A[i2] 寫A[i]和讀A[i2]的依賴邊上標(biāo)記的迭代次數(shù)差是210.5軟件流水10.5.5軟件流水的目10.6并行性和數(shù)據(jù)局部性優(yōu)化概述并行編程模型任務(wù)并行數(shù)據(jù)并行流水線并行（前面幾節(jié)涉及較多）本節(jié)內(nèi)容圍繞任務(wù)并行和數(shù)據(jù)并行介紹并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的概況給出并行化的基本概念，程序循環(huán)的變換，還有對(duì)并行化有用的概念類似的考慮怎樣用于優(yōu)化數(shù)據(jù)局部性以矩陣乘算法的優(yōu)化為例

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

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

非均勻內(nèi)存訪問的機(jī)器和消息傳遞的機(jī)器；為獲得良好的性能軟件都必須有很好局部性10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.1多處理器10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.2應(yīng)用中的并行性并行應(yīng)用性能衡量的兩種標(biāo)準(zhǔn)并行覆蓋：整個(gè)計(jì)算中并行運(yùn)行部分的百分比并行粒度：處理器上無需和其它處理器同步或通信的計(jì)算量 循環(huán)對(duì)并行化來說特別有吸引力，循環(huán)可以有許多次迭代計(jì)算，如果這些計(jì)算相互獨(dú)立，則它們是并行計(jì)算的主要來源 許多控制結(jié)構(gòu)簡(jiǎn)單、數(shù)據(jù)量大并且耗時(shí)長(zhǎng)的科學(xué)和工程應(yīng)用，很容易以較細(xì)粒度被并行化

10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.2應(yīng)用中的10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3循環(huán)級(jí)并行 耗時(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)級(jí)并10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3循環(huán)級(jí)并行

for(i=0;i<n;i++){ Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; } //

變換成如下代碼

b=ceil(n/M);//M個(gè)處理器,p=0,1,…,M

1

for(i=bp;i<min(n,b(p+1));i++){ Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; }//數(shù)據(jù)并行的例子10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3循環(huán)級(jí)并10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3循環(huán)級(jí)并行對(duì)并行化來說，任務(wù)級(jí)不像循環(huán)級(jí)那樣有吸引力對(duì)一個(gè)程序而言，獨(dú)立的任務(wù)數(shù)是一個(gè)常數(shù)，它不像典型的循環(huán)那樣，獨(dú)立的計(jì)算單元隨迭代次數(shù)增加而增加任務(wù)通常不是等規(guī)模的，因此很難保證所有的處理器在所有時(shí)間都處于忙碌10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.3循環(huán)級(jí)并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ù)局部10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部性同一個(gè)緩存行上的元素一起被使用的情況是空間局部性的一種重要形式這種空間局部性將緩存未命中降到最低，因此使得程度獲得明顯的加速10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部性

for(i=0;i<n;i++){ //該程序段對(duì)向量機(jī)來 Z[i]=X[i]Y[i]; //說是一種優(yōu)化形式

} for(i=0;i<n;i++){ Z[i]=Z[i]Z[i]; } for(i=0;i<n;i++){ //有較好的數(shù)據(jù)局部性

Z[i]=X[i]Y[i]; Z[i]=Z[i]Z[i]; }10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部性對(duì)行為主的數(shù)組Z，根據(jù)空間局部性，顯然更愿意逐行地給該數(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++)

Z[i,j]=0; Z[i,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++)

Z[i,j]=0;10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(shù)據(jù)局部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í)行這些單元往往會(huì)產(chǎn)生較好的數(shù)據(jù)局部性10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.4數(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è)緩存行上假定緩存足以放下X所 有的緩存行，讀入X出 現(xiàn)n2/c次緩存未命中for(i=0;i<n;i++) for(j=0;j<n;j++){ Z[i,j]=0.0; for(k=0;k<n;k++) Z[i,j]=Z[i,j]+X[i,k]Y[k,j];

}10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5矩陣乘法10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5矩陣乘法算法先考慮在單處理器上順序執(zhí)行j=01…n

1i=0XY完成Z一行元素的計(jì)算，取Y出現(xiàn)的緩存未命中次數(shù)在n2/c和n2之間完成整個(gè)Z，Y未命中次數(shù)在n2/c和n3之間10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5矩陣乘法10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5矩陣乘法算法再考慮在p個(gè)處理器上并行計(jì)算把Z不同行的計(jì)算指派到不同處理器，每個(gè)處理器計(jì)算Z的連續(xù)n/p行每個(gè)處理器訪問矩陣X和Z的n/p行以及整個(gè)Y，用n3/p次乘加運(yùn)算來完成對(duì)Z的n2/p個(gè)元素的計(jì)算雖然計(jì)算時(shí)間與p成比例減少，但通信代價(jià)卻與p成比例增加，因?yàn)榻桓督op個(gè)處理器之緩存的總緩存行是n2/c+pn2/cp逼近n時(shí)，計(jì)算時(shí)間為O(n2)，通信代價(jià)為O(n3)

10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.5矩陣乘法10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法算法的優(yōu)化

復(fù)用在緩存的數(shù)據(jù)才代表數(shù)據(jù)局部性好復(fù)用應(yīng)該很快發(fā)生，數(shù)據(jù)才可能還在緩存在上述算法中，n2個(gè)乘加操作隔開了矩陣Y中同一個(gè)數(shù)據(jù)的復(fù)用，n個(gè)乘加操作隔開了Y中同一個(gè)緩存行的復(fù)用分塊是重排循環(huán)中迭代次序的一種方法，它能夠極大地改進(jìn)程序的局部性10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法算法的優(yōu)化

從第4到7行的程序計(jì)算左上角為X[ii,kk]和Y[kk,jj]的兩塊對(duì)左上角為Z[ii,jj]的塊的貢獻(xiàn)for(ii=0;ii<n;ii=ii+b)for(jj=0;jj<n;jj=jj+b)

for(kk=0;kk<n;kk=kk+b) for(i=ii;i<ii+b;i++) for(j=jj;j<jj+b;j++) for(k=kk;k<kk+b;k++) Z[i,j]=Z[i,j]+ X[i,k]Y[k,j];bn10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法算法的優(yōu)化

適當(dāng)選擇b，使3個(gè)矩陣都有一個(gè)塊可以裝到緩存把X或Y一塊取到緩存，會(huì)出現(xiàn)b2/c次緩存未命中對(duì)于X和Y的一對(duì)塊，第4到7行的程序完成b3次乘加計(jì)算由于整個(gè)矩陣乘法需要n3次乘加計(jì)算，則取一對(duì)塊到緩存的總次數(shù)是n3/b3對(duì)于X和Y的一對(duì)塊會(huì)有2b2/c次緩存未命中，因此緩存未命中的總次數(shù)是2n3/bc和10.6.5節(jié)的O(n3/c)，甚至O(n3)次緩存未命中相比，在b較大時(shí)，2n3/bc能體現(xiàn)出分開方法的好處10.6并行性和數(shù)據(jù)局部性優(yōu)化概述10.6.6矩陣乘法習(xí)題第一次：10.1,10.3第二次：10.5,10.6習(xí)題第一次：10.1,10.3第十章依賴于機(jī)器的優(yōu)化在指令級(jí)并行的機(jī)器上，程序的運(yùn)行速度依賴于下面幾個(gè)因素

程序中潛在的并行處理器上可用的并行從串行程序提取并行的能力

在給定的調(diào)度約束下發(fā)現(xiàn)最佳并行調(diào)度的能力并行的提取和并行執(zhí)行的調(diào)度都可以靜態(tài)地在軟件中或動(dòng)態(tài)地在硬件中完成第十章依賴于機(jī)器的優(yōu)化在指令級(jí)并行的機(jī)器上，程序的運(yùn)行速第十章依賴于機(jī)器的優(yōu)化本章內(nèi)容使用指令級(jí)并行的基礎(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)化的概念和方法第十章依賴于機(jī)器的優(yōu)化本章內(nèi)容10.1處理器體系結(jié)構(gòu)在考慮指令級(jí)并行時(shí)，通常想象成一個(gè)處理器在單個(gè)時(shí)鐘周期內(nèi)發(fā)射幾個(gè)操作事實(shí)上，在每周期內(nèi)發(fā)射一個(gè)操作是可能的,而指令級(jí)并行的獲得是通過使用流水線技術(shù)本節(jié)先解釋流水線，然后討論多指令發(fā)射10.1處理器體系結(jié)構(gòu)在考慮指令級(jí)并行時(shí)，通常想象成一個(gè)10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲

i i+1 i+2 i+3 i+41. IF2. ID IF3. EX ID IF4. MEM EX ID IF5. WB MEM EX ID IF6. WB MEM EX ID7. WB MEM EX8. WB MEM9. WB取指令I(lǐng)F,譯碼ID,執(zhí)行操作EX,訪問內(nèi)存MEM,回寫結(jié)果WB5級(jí)指令流水線中的5條連續(xù)指令10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲分支延遲發(fā)現(xiàn)應(yīng)該執(zhí)行一個(gè)分支而不是直接后繼轉(zhuǎn)向一個(gè)分支時(shí)會(huì)引起取分支目的地址指令的延遲并引起指令流水線“打嗝”可以通過使用硬件，根據(jù)分支的執(zhí)行歷史來預(yù)測(cè)分支結(jié)果并從預(yù)測(cè)的目的地址預(yù)取指令分支延遲不可避免，因?yàn)榉种ьA(yù)測(cè)會(huì)發(fā)生偏差10.1處理器體系結(jié)構(gòu)10.1.1指令流水線和分支延遲10.1處理器體系結(jié)構(gòu)10.1.2流水化的執(zhí)行 如果不依賴一條指令結(jié)果的隨后指令在該結(jié)果產(chǎn)生前就被允許執(zhí)行有些指令的執(zhí)行需要幾個(gè)周期，幾個(gè)操作同時(shí)出現(xiàn)在它們的執(zhí)行級(jí)上可能的如果最長(zhǎng)的執(zhí)行流水線是n級(jí)，n個(gè)操作同時(shí)進(jìn)行的可能性是存在的并非所有的指令都能被完全流水化，例如浮點(diǎn)除通用處理器大都動(dòng)態(tài)察覺相繼指令之間的依賴性嵌入式系統(tǒng)把數(shù)據(jù)相關(guān)性的檢查交給軟件10.1處理器體系結(jié)構(gòu)10.1.2流水化的執(zhí)行10.1處理器體系結(jié)構(gòu)10.1.3多指令發(fā)射

每周期發(fā)射幾個(gè)操作，讓更多操作同時(shí)進(jìn)行超長(zhǎng)指令字機(jī)器將若干個(gè)操作編碼在單周期中發(fā)射編譯器需要確定哪些操作可以并行發(fā)射超標(biāo)量機(jī)器超標(biāo)量機(jī)器有按普通順序執(zhí)行語義的正規(guī)指令集硬件自動(dòng)察覺指令之間的相關(guān)性，并且在它們的操作數(shù)可用時(shí)就發(fā)射它們更復(fù)雜的調(diào)度器能夠“亂序”執(zhí)行指令10.1處理器體系結(jié)構(gòu)10.1.3多指令發(fā)射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)度的約束代碼調(diào)度10.2代碼調(diào)度的約束

10.2.1數(shù)據(jù)相關(guān)真相關(guān) 如果對(duì)同一個(gè)單元先寫后讀，那么讀依賴于所寫的值反相關(guān)

如果對(duì)同一個(gè)單元先讀后寫?？梢酝ㄟ^把值存在不同的單元來刪除反相關(guān)輸出相關(guān)

如果對(duì)同一個(gè)單元先后寫兩次。也可刪除數(shù)據(jù)相關(guān)概念可同時(shí)用于內(nèi)存訪問和寄存器訪問10.2代碼調(diào)度的約束10.2.1數(shù)據(jù)相關(guān)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)存訪問中的相10.2代碼調(diào)度的約束

10.2.2發(fā)現(xiàn)內(nèi)存訪問中的相關(guān)性發(fā)現(xiàn)數(shù)據(jù)相關(guān)需要不同形式的分析數(shù)組元素間的別名分析 A[i]和A[j]是否互為別名指針別名分析 若p和q相等，則p和q、p->next和q->next、 p->data和q->data等都分別互為別名過程間分析 引用調(diào)用場(chǎng)合：形參和形參之間、形參和全局變量之間因?qū)崊⒍鸹閯e名10.2代碼調(diào)度的約束10.2.2發(fā)現(xiàn)內(nèi)存訪問中的相10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 若瞄準(zhǔn)極小化寄存器的使用個(gè)數(shù)，則只需使用3個(gè)寄存器10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e) LDR1,a LDR2,b ADDR1,R1,R2 LDR2,c

ADDR1,R1,R2

LDR2,d

LDR3,e ADDR2,R2,R3 ADDR1,R1,R2+e+c+ab+d 完成整個(gè)計(jì)算需要7步10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

10.2.3寄存器使用和并行執(zhí)行之間的折衷例：(a+b)+c+(d+e)

+e+c+ab+d

如果對(duì)每個(gè)中間結(jié)果使用不同寄存器，則完成計(jì)算只需要4步R1=aR6=R1+R2R8=R6+R3R9=R8+R7R2=bR7=R4+R5R3=cR4=dR5=e10.2代碼調(diào)度的約束10.2.3寄存器使用和并行執(zhí)10.2代碼調(diào)度的約束

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

10.2.5控制相關(guān)

在非數(shù)值計(jì)算中，基本塊非常小，其中的操作通常高度相關(guān)，幾乎不能并行調(diào)查跨基本塊的并行是至關(guān)重要的若一條指令很可能被執(zhí)行且有空閑的資源可“免費(fèi)”用于完成該指令的操作，則可以投機(jī)地執(zhí)行該指令；若投機(jī)成功，則程序運(yùn)行得快一些例 if(a>t) b=aa依賴于比較a>t的結(jié)果

b=aa; 若aa不會(huì)產(chǎn)生副作用，則 d=a+c; aa可以投機(jī)地執(zhí)行10.2代碼調(diào)度的約束10.2.5控制相關(guān)10.2代碼調(diào)度的約束

10.2.6投機(jī)執(zhí)行的支持內(nèi)存讀取是一類使用頻繁，且能從投機(jī)執(zhí)行大大獲益的指令但在if(p!=null) q=p 中，投機(jī)地對(duì)p脫引用將引起該程序因p等于null而錯(cuò)誤地停止許多高性能處理器提供專門的特性來支持投機(jī)地內(nèi)存訪問10.2代碼調(diào)度的約束10.2.6投機(jī)執(zhí)行的支持10.2代碼調(diào)度的約束

10.2.6投機(jī)執(zhí)行的支持預(yù)取指令 在數(shù)據(jù)使用前將其從內(nèi)存取到緩存,若該單元無效或訪問它會(huì)引起缺頁，則忽略

抑制位 允許投機(jī)地從內(nèi)存將數(shù)據(jù)讀取到寄存器堆，若出現(xiàn)非法內(nèi)存訪問或缺頁，則設(shè)置目標(biāo)寄存器的抑制位判定指令 在判定條件為真時(shí)才執(zhí)行的指令 例if(a==0) 翻譯成ADDR3,R4,R5 b=c+d; CMOVZR2,R3,R1 假定a、b、c和d分別被分配了R1、R2、R4和R5

可用來將相鄰基本塊組合成一個(gè)更大基本塊10.2代碼調(diào)度的約束10.2.6投機(jī)執(zhí)行的支持10.2代碼調(diào)度的約束

10.2.7一個(gè)基本的機(jī)器模型機(jī)器模型M=(R,T)T：操作類型集，如讀取、存儲(chǔ)和算術(shù)運(yùn)算等R=[r1,r2,…]：硬件資源向量集，如內(nèi)存訪問部件、算術(shù)運(yùn)算部件和浮點(diǎn)功能部件 ri代表第i類資源中可用的部件數(shù)每個(gè)操作有一組輸入操作數(shù)、一組輸出操作數(shù)和一個(gè)資源需求和每個(gè)輸入操作數(shù)相關(guān)的是一個(gè)輸入延遲和每個(gè)輸出操作數(shù)相關(guān)的是一個(gè)輸出延遲10.2代碼調(diào)度的約束10.2.7一個(gè)基本的機(jī)器模型10.2代碼調(diào)度的約束

10.2.7一個(gè)基本的機(jī)器模型機(jī)器模型M=(R,T)對(duì)每種操作類型t，資源使用由一張二維資源預(yù)留表RTt來建模條目RTt[i,j]是t類型的一個(gè)操作在它被發(fā)射i時(shí)鐘周期后，使用第j種資源的部件數(shù)對(duì)任何t、i和j，RTt[i,j]必須小于或等于R[j]10.2代碼調(diào)度的約束10.2.7一個(gè)基本的機(jī)器模型10.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和邊集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)度10.3.1數(shù)據(jù)依賴10.3基本塊調(diào)度數(shù)據(jù)依賴圖資源預(yù)留表alumenLDR2,0(R1)ST4(R1),R2LDR3,8(R1)ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3222111111i1i2i3i4i5i6i7灰色表示1

白色表示0操作是全流水的，只需顯示在第1行使用的資源

10.3基本塊調(diào)度數(shù)據(jù)依賴圖資源預(yù)留表a10.3基本塊調(diào)度10.3.2基本塊的表調(diào)度關(guān)鍵路徑包括最后5個(gè)結(jié)點(diǎn)，故第3條指令先調(diào)度再調(diào)度第1條指令，因?yàn)榈?條指令還需等1周期第4周期調(diào)度2條資源預(yù)留表alumen調(diào)度表LDR3,8(R1)

ADDR3,R3,R2ADDR3,R3,R4ST0(R7),R7ST12(R1),R3ST4(R1),R2

LDR2,0(R1)

10.3基本塊調(diào)度10.3.2基本塊的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.3基本塊調(diào)度10.3.2基本塊的10.4全局代碼調(diào)度對(duì)于有適度指令級(jí)并行的機(jī)器，僅對(duì)每個(gè)基本塊進(jìn)行緊湊調(diào)度會(huì)引起許多資源空閑全局調(diào)度：為了更好地利用機(jī)器資源，需要考慮把指令從一個(gè)基本塊移到另一個(gè)基本塊的代碼生成策略 必須保證原來程序中所有指令在優(yōu)化程序中都被執(zhí)行當(dāng)優(yōu)化程序可以投機(jī)地執(zhí)行額外指令時(shí)，這些指令肯定不能有任何多余的副作用10.4全局代碼調(diào)度對(duì)于有適度指令級(jí)并行的機(jī)器，僅對(duì)每個(gè)10.4全局代碼調(diào)度10.4.1簡(jiǎn)單的代碼移動(dòng)先用例子展示操作在基本塊之間移動(dòng)涉及的問題

L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度10.4.1簡(jiǎn)單的代碼移動(dòng)L:if10.4全局代碼調(diào)度假定a,b,c,d和e的地址不同，分別保存在R1到R5由于數(shù)據(jù)相關(guān)，塊內(nèi)的指令必須串行執(zhí)行，且插入NOPL:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度假定a,b,c,d和e的地址不10.4全局代碼調(diào)度假定機(jī)器在一個(gè)時(shí)鐘周期執(zhí)行任意的兩個(gè)操作讀取操作有2周期的延遲，其他指令1周期的延遲L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度假定機(jī)器在一個(gè)時(shí)鐘周期執(zhí)行任意的兩個(gè)10.4全局代碼調(diào)度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)行B2的讀取操作在執(zhí)行B1時(shí)投機(jī)地完成B2的存儲(chǔ)操作放到B3的 一份拷貝中L:if(a==0)gotoLc=be=d+d(a)源代碼(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度B3肯定要執(zhí)行，因而可以和B1并行執(zhí)10.4全局代碼調(diào)度L:全局調(diào)度前后的流圖if(a==0)gotoLc=be=d+d(a)源代碼ST0(R5),R8(b)局部調(diào)度的機(jī)器代碼LDR6,0(R1), LDR8,0(R4)LDR7,0(R2)ADDR8,R8,R8,BEQZR6,LST0(R5),R8, ST0(R3),R7L:(c)全局調(diào)度的機(jī)器代碼B1B3B3LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度L:全局調(diào)度前后的流圖if(a=10.4全局代碼調(diào)度基本塊之間的支配關(guān)系指令在基本塊之間的移動(dòng)因支配關(guān)系不同而不同B1和B3控制等價(jià)：B1支配B3， B3后支配B1B1支配B2， 但是B2并非后支配B1B2不支配B3， 但是B3后支配B2LDR6,0(R1)NOPBEQZR6,LLDR7,0(R2)NOPST0(R3),R7

LDR8,0(R4)NOPADDR8,R8,R8ST0(R5),R8B2B1B3L:10.4全局代碼調(diào)度基本塊之間的支配關(guān)系LDR6,010.4全局代碼調(diào)度10.4.2向上的代碼移動(dòng) 從塊src向上移動(dòng)到塊dst，假定移動(dòng)未違反數(shù)據(jù)相關(guān)，并使得通過dst到src的路徑運(yùn)行得較快若dst和src等價(jià)，則被移動(dòng)操作應(yīng)該被執(zhí)行時(shí)，它正好僅被執(zhí)行一次dstsrc10.4全局代碼調(diào)度10.4.2向上的代碼移動(dòng)dsts10.4全局代