并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯

并行計(jì)算,第一級(jí),第二級(jí),第三級(jí),第一級(jí),第二級(jí),第三級(jí),國家高性能計(jì)算中心（合肥）,*,*,并行算法實(shí)踐,并行編譯概述,并行編譯器的組成及任務(wù),數(shù)據(jù)依賴關(guān)系,循環(huán)的向量化與并行化,2024/10/22,2,國家高性能計(jì)算中心（合肥）,并行編譯器的組成及任務(wù),源代碼,程序分析,程序優(yōu)化,并行代碼生成,向量機(jī)：,組織向量循環(huán),寄存器分配,流水線調(diào)度,共享存儲(chǔ)多機(jī)系統(tǒng)：,任務(wù)劃分,處理機(jī)調(diào)度,同步,分布存儲(chǔ)多機(jī)系統(tǒng)：,數(shù)據(jù)和計(jì)算分布,通信,同步,數(shù)據(jù)依賴與控制依賴關(guān)系分析,數(shù)據(jù)流分析,包括循環(huán)向量化與并行化在內(nèi)的各種優(yōu)化,并行語義識(shí)別，處理指令級(jí)并行調(diào)度,2024/10/22,3,國家高性能計(jì)算中心（合肥）,數(shù)據(jù)依賴關(guān)系,Def1:,語句,S,和,T,，若存在變量,x,使之滿足下述條件之一，則稱語句,T,依賴于語句,S,，記為,S,T,，否則,S,和,T,之間沒有數(shù)據(jù)依賴關(guān)系：,（,1,）流依賴：,S,f,T,，若,xOUT,（,S,）且,xIN,（,T,）,且,T,使用,S,計(jì)算出的,x,的值；,T,流依賴于,S,；,（,2,）反依賴：,S,a,T,，若,xIN,（,S,）且,xOUT,（,T,）,但,S,使用,x,值先于,T,對(duì),x,的定值；,T,反依賴于,S,；,（,3,）輸出依賴：,S,o,T,，若,xOUT,（,S,）且,xOUT,（,T,）但,S,較之,T,先對(duì),x,進(jìn)行定值；,T,輸出依賴于,S,；,2024/10/22,4,國家高性能計(jì)算中心（合肥）,e.g.,考慮語句序列,：,S:A=B+D,T:C=A*3,U:A=A+C,V:E=A/2,依賴關(guān)系示例,IN:B D,，,OUT,：,A,IN:A,，,OUT,：,C,IN:A C,，,OUT,：,A,IN:A,，,OUT,：,E,S,f,T,S,f,U,S,o,U,T,f,U,T,a,U,U,f,V,2024/10/22,5,國家高性能計(jì)算中心（合肥）,依賴關(guān)系示例,e.g.,循環(huán)語句：,for i=1 to 100 do,S:,Ai,=B i+2+1;,T:,Bi,=Ai-1 1;,end for,S(1):A1=B3 +1,T(1):B1=A0 1,S(2):A2=B4 +1,T(2):B2=A1 1,S(3):A3=B5 +1,T(3):B3=A2 1,.,S(100):A100=B102 +1,T(100):B100=A99 1,f,a,依賴關(guān)系：,S,f,T,S,a,T,2024/10/22,6,國家高性能計(jì)算中心（合肥）,數(shù)據(jù)依賴關(guān)系,Def2,：,語句,S,和,T,在循環(huán),L,中。

如果,S,的實(shí)例,S(i,),和,T,的實(shí)例,T(j,),以及變量,u,S,，變量,v,T,，滿足：,（,1,）,u,和,v,至少有一個(gè)是輸出變量；,（,2,）,u,S(i,),和變量,v,T(j,),表示同一個(gè)存儲(chǔ)單元,M,（,3,）在,L,的順序執(zhí)行中，,S(i,),先于,T(j,),（,4,）在,L,的順序執(zhí)行中，,S(i,),之間,T(j,),沒有其他對(duì),M,的寫操作；則,u,、,v,引起,T,依賴于,S,，即,S T,，稱為,T(j,),依賴于,S(i,),，其中：,流依賴：,u OUT(S),v,IN(T),反依賴：,u IN(S),v,OUT(T),輸出依賴：,u OUT(S),v,OUT(T),T,對(duì),S,的依賴即為滿足上述條件的偶對(duì)（,S(i),T(j,),）的集合2024/10/22,7,國家高性能計(jì)算中心（合肥）,依賴距離和依賴向量,令,=(,1,2,n,),和,=(,1,2,n,),是,n,層循環(huán)內(nèi)的,n,個(gè)整數(shù)下標(biāo)向量，假定,和,存在數(shù)據(jù)相關(guān)性，則,依賴距離向量,（,Dependent Distance Vector,）,D=(D,1,D,2,D,n,),定義為,-,；而,依賴方向向量,（,Dependent Direction Vector,）,d=(d,1,d,2,d,n,),定義為：,或,1,或,0,或,1,2024/10/22,8,國家高性能計(jì)算中心（合肥）,例如，有如下的三層循環(huán)嵌套：,for,i=,l,1,to,u,1,do,for,j=,l,2,to,u,2,do,for,k=,l,3,to,u,3,do,A(i,+1,j,k 1)=,A(i,j,k)+C,endfor,endfor,endfor,則數(shù)組,A,的三維迭代之間的相關(guān)距離向量,D=(i+1 i,j j,k 1 k)=(1,0,-1),和相關(guān)方向向量,=(),。

相關(guān)方向向量對(duì)計(jì)算循環(huán)體間相關(guān)性十分有用，其相關(guān)性是通過相關(guān)方向向量不是”,=”,號(hào)的外層循環(huán)傳遞的；相關(guān)距離向量指明在,同一存儲(chǔ)單元的兩次訪問之間循環(huán)迭代的實(shí)際距離,它們對(duì)開發(fā)并行性或優(yōu)化存儲(chǔ)器層次結(jié)構(gòu)時(shí)起到指引作用2024/10/22,9,國家高性能計(jì)算中心（合肥）,語句依賴圖和迭代依賴圖,語句依賴圖依賴關(guān)系,的有向圖將語句，如,S,和,T,，看成結(jié)點(diǎn)，若有,S,T,，則：,間接依賴關(guān)系 ，即依賴關(guān)系的傳遞閉包若,S T,，則在語句依賴圖中存在,S,到,T,的一條路徑迭代依賴圖即（循環(huán)）迭代之間的依賴關(guān)系在循環(huán),L,中，若語句,T,依賴于語句,S,，即,S,T,令,S(I),和,T(J),是滿足依賴關(guān)系的偶對(duì)，,S(I),T(J),，此時(shí)應(yīng)該有,I,J,在,IJ,時(shí)，稱迭代,H(J),依賴于迭代,H(I),，記為,H(I),H(J),S,T,2024/10/22,10,國家高性能計(jì)算中心（合肥）,語句依賴圖示例,有如下循環(huán)語句：,for i=4 to 200 do,S:,A(i,),=,B(i,),+,c(i,),T:,B(i+2),=,A(i-1),+,A(i-3),+C(i-1),U:,A(i+1),=,B(2*i+3),+1,endfor,各語句間依賴關(guān)系如何呢？,2024/10/22,11,國家高性能計(jì)算中心（合肥）,語句,T,流依賴于語句,S,，即,S,f,T,，滿足依賴關(guān)系的偶對(duì)集合為：,|i=j-1;5,j,200 ,|i=j-3;7,j,200,語句,S,流依賴于語句,T,，即,T,f,S,，滿足依賴關(guān)系的偶對(duì)集合為：,|i=j-2;6,j,200,語句,S,輸出依賴于語句,U,，即,U,o,S,，滿足依賴關(guān)系的偶對(duì)集合為：,|i=j-1;5,j,200,語句,T,反依賴于語句,U,，即,U,a,T,，滿足依賴關(guān)系的偶對(duì)集合為：,|j=2*i+1;4,i99,語句,T,是否流依賴于語句,U,呢？,2024/10/22,12,國家高性能計(jì)算中心（合肥）,for i=4 to 200 do,S:,A(i,),=,B(i,),+,c(i,),T:,B(i+2),=,A(i-1),+,A(i-3),+C(i-1),U:,A(i+1),=,B(2*i+3),+1,endfor,語句依賴圖示例,S,T,U,f,f,o,a,2024/10/22,13,國家高性能計(jì)算中心（合肥）,迭代依賴圖示例（,1,）,有如下二重循環(huán)：,for i=0 to 5 do,for j=0 to 4 do,S:,A(i+1,j+1),=,A(i,j,),+B(,i,j,),endfor,endfor,顯然，,S,f,S,。

滿足依賴關(guān)系的偶對(duì)集合：,|j1=i1+1,j2=i2+1,0,i1,4,0,i2,3,/,依賴方向向量和距離向量各是什么？,2024/10/22,14,國家高性能計(jì)算中心（合肥）,迭代依賴圖（,1,）,2024/10/22,15,國家高性能計(jì)算中心（合肥）,迭代依賴圖示例（,2,）,有如下二重循環(huán)：,L1:for i1=0 to 4 do,L2:for i2=0 to 4 do,S:,A(i1+1,i2),=,B(i1,i2),+C(i1,i2),T:,B(i1,i2+1),=,A(i1,i2+1),+1,U:D(i1,i2)=,B(i1,i2+1),2,endfor,endfor,2024/10/22,16,國家高性能計(jì)算中心（合肥）,語句,T,流依賴于語句,S,，即,S,f,T,，滿足依賴關(guān)系的偶對(duì)：,S(i1,i2),T(j1,j2)|j1=i1+1,j2=i2-1,0,i1,3,1,i2,4,，距離向量為,(1,-1),，方向向量為,(1,-1),此依賴關(guān)系由循環(huán),L1,攜帶；,語句,S,流依賴于語句,T,，即,T,f,S,，滿足依賴關(guān)系的偶對(duì)：,T(i1,i2),S(j1,j2)|j1=i1,j2=i2+1,0,i1,4,0,i2,3,，距離向量為,(0,1),，方向向量為,(0,1),。

此依賴關(guān)系由循環(huán),L2,攜帶；,語句,U,流依賴于語句,T,，即,T,f,U,，滿足依賴關(guān)系的偶對(duì)：,T(i1,i2),U(j1,j2)|j1=i1,j2=i2,0,i1,4,0,i2,4,，距離向量為,(0,0),，方向向量為,(0,0),此依賴關(guān)系與循環(huán)無關(guān)2024/10/22,17,國家高性能計(jì)算中心（合肥）,S,T,U,f,f,f,語句依賴圖,迭代依賴圖,2024/10/22,18,國家高性能計(jì)算中心（合肥）,考慮如下循環(huán)的迭代依賴圖：,for I=1 to 4 do,for J=1 to 4 do,S:A(I,J)=A(I-1,J)+A(I,J-1),endfor,endfor,2024/10/22,19,國家高性能計(jì)算中心（合肥）,依賴關(guān)系方程,假定循環(huán)中數(shù)組下標(biāo)是循環(huán)索引變量的線性表達(dá)式,循環(huán)的一般表示：,(X,是,n,維數(shù)組，,f,和,g,是循環(huán)索引變量,I=(I,1,I,2,I,m,),的線性函數(shù),),L,1,:for I,1,=p,1,to q,1,do,L,2,:for I,2,=p,2,to q,2,do,.,L,m,:for,I,m,=p,m,to,q,m,.,S:,X(f,1,(I),f,2,(I),f,n,(I,),=.,T:.=.,X(g,1,(I),g,2,(I),g,n,(I,),.,.,endfor,.,endfor,endfor,2024/10/22,20,國家高性能計(jì)算中心（合肥）,依賴關(guān)系方程,(,丟番圖方程）,上述循環(huán),L,中語句,S,和,T,，令,u=,X(f,1,(I),f,2,(I),f,n,(I,),是,S,的變量，而,v=,X(g,1,(I),g,2,(I),g,n,(I,),，,u,或,v,至少一個(gè)是相應(yīng)語句的輸出變量。

若,u,、,v,導(dǎo)致,S,和,T,之間的依賴關(guān)系，則以下方程組,f,1,(I),g,1,(J)=0,f,2,(I),g,2,(J)=0,.,f,n,(I,),g,n,(J,)=0,有滿足下述約束條件的整數(shù)解（,i,j,），,i=(i,1,i,2,i,m,),j=(j,1,j,2,j,m,):,p,r,i,r,q,r,p,r,j,r,q,r,；且該解滿足下述特定情況下的附加條件：,（,1,）若,S,T,且,S,T,則,i,j,（,2,）若,S,T,且,S,S,則,i,j,（,3,）若,S,j,2024/10/22,21,國家高性能計(jì)算中心（合肥）,如果依賴方程（丟番圖方程）有滿足上述條件的整數(shù)解（,i,，,j,），那么,（,1,）若,i,j,則,T,S,（,3,）若,i,j,且,S,T,，則,S,T,其中,表示,間接依賴關(guān)系,2024/10/22,22,國家高性能計(jì)算中心（合肥）,考慮如下程序段：,L1:for I=1 to 50 do,.,S:X(2*I)=.,.,T:.=.X(3*I+1).,.,endfor,這里：,f,1,(I)=2*I,；,g,1,(J)=3*J+1,依賴方程為：,f,1,(I)-g,1,(J)=0,2*I 3*J=1,而依賴約束為：,1,I,50,，,1,J,50,。

該方程的解（,I,J),對(duì)應(yīng)的數(shù)組變量會(huì)導(dǎo)致,S,和,T,之間的依賴2024/10/22,23,國家高性能計(jì)算中心（合肥）,循環(huán)向量化,循環(huán)向量化,將僅含有數(shù)組賦值語句的循環(huán),L,轉(zhuǎn)換成等價(jià)。