1、并行編譯簡介,國家高性能計算中心（合肥）,2,2020/8/5,并行編譯簡介,并行編譯器的組成及任務 數據依賴關系 循環(huán)的向量化與并行化,國家高性能計算中心（合肥）,3,2020/8/5,并行編譯器的組成及任務,源代碼,程序分析,程序優(yōu)化,并行代碼生成,向量機： 組織向量循環(huán) 寄存器分配 流水線調度,共享存儲多機系統(tǒng)： 任務劃分 處理機調度 同步,分布存儲多機系統(tǒng)： 數據和計算分布 通信 同步,數據依賴與控制依賴關系分析 數據流分析,包括循環(huán)向量化與并行化在內的各種優(yōu)化,并行語義識別，處理指令級并行調度,國家高性能計算中心（合肥）,4,2020/8/5,數據依賴關系,Def1: 語句S和T，若

2、存在變量x使之滿足下述條件之一，則稱語句T依賴于語句S，記為S T，否則S和T之間沒有數據依賴關系： （1）流依賴 ： S f T，若xOUT（S）且 xIN（T） 且T使用S計算出的x的值；T流依賴于S； （2）反依賴 ： S a T，若xIN（S）且 xOUT（T） 但S使用x值先于T對x的定值；T反依賴于S； （3）輸出依賴 ： S o T，若xOUT（S）且 xOUT（T）但S較之T先對x進行定值； T輸出依賴于S；,國家高性能計算中心（合肥）,5,2020/8/5,e.g. 考慮語句序列： S : A = B + D T : C = A * 3 U : A = A + C V : E

3、 = A / 2,依賴關系示例,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,國家高性能計算中心（合肥）,6,2020/8/5,依賴關系示例,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 =

4、B5 + 1 T(3) : B3 = A2 1 . . . S(100) : A100 = B102 + 1 T(100) : B100 = A99 1,f,a,依賴關系： S f T S a T,國家高性能計算中心（合肥）,7,2020/8/5,數據依賴關系,Def2：語句S和T在循環(huán)L中。如果S的實例S(i)和T的實例T(j)以及變量uS，變量v T，滿足： （1）u和v至少有一個是輸出變量； （2）uS(i)和變量v T(j)表示同一個存儲單元M （3）在L的順序執(zhí)行中，S(i)先于T(j) （4）在L的順序執(zhí)行中， S(i)之間T(j)沒有其他對M的寫操作；則u、v引起T依賴于S，即S

5、 T，稱為T(j)依賴于S(i)，其中： 流依賴： u OUT(S) , v IN(T) 反依賴： u IN(S) , v OUT(T) 輸出依賴：u OUT(S) , v OUT(T) T 對S的依賴即為滿足上述條件的偶對（S(i),T(j)）的集合。,國家高性能計算中心（合肥）,8,2020/8/5,依賴距離和依賴向量,令=(1,2,n) 和=(1,2,n)是n層循環(huán)內的n個整數下標向量，假定和存在數據相關性，則依賴距離向量（Dependent Distance Vector）D = (D1,D2,Dn)定義為-；而依賴方向向量（Dependent Direction Vector）d =

6、 (d1,d2,dn)定義為：,或 1,或 0,或 1,國家高性能計算中心（合肥）,9,2020/8/5,例如，有如下的三層循環(huán)嵌套： for i = l1 to u1 do for j = l2 to u2 do for k = l3 to u3 do A(i + 1, j, k 1) = A(i, j, k) + C endfor endfor endfor 則數組A的三維迭代之間的相關距離向量D = (i + 1 i, j j, k 1 k ) = (1, 0, -1)和相關方向向量= ()。 相關方向向量對計算循環(huán)體間相關性十分有用，其相關性是通過相關方向向量不是”=”號的外層循環(huán)傳遞

7、的；相關距離向量指明在同一存儲單元的兩次訪問之間循環(huán)迭代的實際距離。它們對開發(fā)并行性或優(yōu)化存儲器層次結構時起到指引作用。,國家高性能計算中心（合肥）,10,2020/8/5,語句依賴圖和迭代依賴圖,語句依賴圖依賴關系的有向圖。將語句，如S和T，看成結點，若有S T，則： 間接依賴關系 ，即依賴關系的傳遞閉包。 若S T，則在語句依賴圖中存在S到T的一條路徑。 迭代依賴圖即（循環(huán)）迭代之間的依賴關系。在循環(huán)L中，若語句T依賴于語句S，即S T。令S(I)和T(J)是滿足依賴關系的偶對，S(I) T(J)，此時應該有IJ。在IJ時，稱迭代H(J)依賴于迭代H(I)，記為H(I) H(J)。,S,T

8、,國家高性能計算中心（合肥）,11,2020/8/5,語句依賴圖示例,有如下循環(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 各語句間依賴關系如何呢？,國家高性能計算中心（合肥）,12,2020/8/5,語句T流依賴于語句S，即S f T，滿足依賴關系的偶對集合為： | i = j -1 ; 5j200 | i = j -3 ; 7j200 語句S流依賴于語句T，即T f S，滿足依賴關系的偶對集合為： | i = j

9、 -2 ; 6j200 語句S輸出依賴于語句U，即 U o S ，滿足依賴關系的偶對集合為： | i = j -1 ; 5j200 語句T反依賴于語句U，即U a T ，滿足依賴關系的偶對集合為： | j = 2*i + 1 ; 4i99 語句T是否流依賴于語句U呢？,國家高性能計算中心（合肥）,13,2020/8/5,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,國家高性能計算中心

10、（合肥）,14,2020/8/5,迭代依賴圖示例（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 。滿足依賴關系的偶對集合： | j1 = i1 + 1 , j2 = i2 + 1, 0i14, 0i23 / 依賴方向向量和距離向量各是什么？,國家高性能計算中心（合肥）,15,2020/8/5,迭代依賴圖（1）,國家高性能計算中心（合肥）,16,2020/8/5,迭代依賴圖示例（2）,有如下二重循環(huán)： L1 :for i1 = 0 t

11、o 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,國家高性能計算中心（合肥）,17,2020/8/5,語句T流依賴于語句S，即S f T，滿足依賴關系的偶對： S(i1,i2), T(j1,j2) | j1 = i1+1, j2=i2-1, 0i13, 1i24 ，距離向量為(1,-1)，方向向量為(1, -1)。此依賴關系由循環(huán)L1攜帶； 語句S流

12、依賴于語句T，即T f S，滿足依賴關系的偶對： T(i1,i2), S(j1,j2) | j1 = i1, j2=i2+1, 0i14, 0i23 ，距離向量為(0,1)，方向向量為(0, 1)。此依賴關系由循環(huán)L2攜帶； 語句U流依賴于語句T，即T f U，滿足依賴關系的偶對： T(i1,i2), U(j1,j2) | j1 = i1, j2=i2, 0i14, 0i24 ，距離向量為(0,0)，方向向量為(0,0)。此依賴關系與循環(huán)無關。,國家高性能計算中心（合肥）,18,2020/8/5,迭代依賴圖,國家高性能計算中心（合肥）,19,2020/8/5,考慮如下循環(huán)的迭代依賴圖： for

13、 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,國家高性能計算中心（合肥）,20,2020/8/5,依賴關系方程,假定循環(huán)中數組下標是循環(huán)索引變量的線性表達式 循環(huán)的一般表示：(X是n維數組，f和g是循環(huán)索引變量I=(I1,I2,Im) 的線性函數 ) L1:for I1 = p1 to q1 do L2: for I2 = p2 to q2 do . . . Lm: for Im = pm to qm . . . S : X(f1(I), f2(I), , fn(I) = .

14、. . T : . . . = . . . X(g1(I), g2(I), , gn(I) . . . . . . endfor . . . endfor endfor,國家高性能計算中心（合肥）,21,2020/8/5,依賴關系方程(丟番圖方程）,上述循環(huán)L中語句S和T，令u= X(f1(I), f2(I), , fn(I) 是S的變量，而v= X(g1(I), g2(I), , gn(I) ，u或v至少一個是相應語句的輸出變量。若u、v導致S和T之間的依賴關系，則以下方程組 f1(I) g1(J) = 0 f2(I) g2(J) = 0 . . . fn(I) gn(J) = 0 有滿足下

15、述約束條件的整數解（i, j），i=(i1,i2,im) , j=(j1,j2,jm) : prirqr prjrqr ；且該解滿足下述特定情況下的附加條件： （1） 若S j,國家高性能計算中心（合肥）,22,2020/8/5,如果依賴方程（丟番圖方程）有滿足上述條件的整數解（i，j），那么 （1） 若 i j , 則T S （3）若 i j , 且 ST ，則S T 其中 表示間接依賴關系。,國家高性能計算中心（合肥）,23,2020/8/5,考慮如下程序段： L1 : for I = 1 to 50 do . . . S : X(2*I) = . . . . . . T : . . .

16、= . . . X(3*I + 1 ) . . . . . . endfor 這里： f1(I) = 2 * I ； g1(J) = 3 * J + 1 。依賴方程為： f1(I) - g1(J) = 0 2*I 3*J = 1 , 而依賴約束為： 1I50 ，1J50。該方程的解（I,J)對應的數組變量會導致S和T之間的依賴。,國家高性能計算中心（合肥）,24,2020/8/5,循環(huán)向量化,循環(huán)向量化 將僅含有數組賦值語句的循環(huán)L轉換成等價的向量語句 如：循環(huán) for I = 1 to N do S: A(I) = D(I) * E T: C(I) = A(I) + B(I) endfor

17、可以改寫為等價的向量語句： S:A(1:N) = D(1:N) * E T:C(1:N) = A(1:N) + B(1:N),國家高性能計算中心（合肥）,25,2020/8/5,可向量化循環(huán) 如果將循環(huán)內的數組賦值改為相應的向量語句后，按原來語句次序執(zhí)行所得結果與原來串行執(zhí)行一樣，那么. . . 但以下循環(huán)不可向量化： for I = 1 to N do S: A(I) = A(I-1) + 1; /不能寫成A(1:N) = A(0:N-1) + 1 endfor 而以下循環(huán)卻可以向量化： for I = 1 to N do S1: A(I) = A(I+1) + 1; /可以寫成A(1:N)

18、 = A(2:N1) + 1 endfor 為什么？,國家高性能計算中心（合肥）,26,2020/8/5,可向量化循環(huán)的充要條件 對于循環(huán)L=(L1,L2,. . ., Lm)其最內層循環(huán)Lm可向量化當且僅當：Lm中任意兩個語句S和T， （1） 當ST時，不存在方向向量為(0,0,1)的S對T的依賴關系，T S；（三種依賴關系中任何一種） （2） 當ST時，不存在方向向量為(0,0,1)的S對T的流依賴關系，T f S； 換言之，最內層循環(huán)中如果不存在與語句詞法順序相反的依賴關系（即反向依賴），則最內層循環(huán)可向量化。 再次考察： for I = 1 to N do S: A(I) = A(I-

19、1) + 1; /不能寫成A(1:N) = A(0:N-1) + 1 endfor /此循環(huán)中存在 S f S，且方向為(1),距離為(1),國家高性能計算中心（合肥）,27,2020/8/5,考查以下循環(huán)可向量化的情況。 （1）for I = 2 to N 1 do for J = 2 to N 1 do S : A(I, J) = B( I-1, J ) + C T : B(I, J) = A(I, J+1) * 2 endfor endfor 如果向量化內層的J循環(huán)，則形成： for I = 2 to N 1 do S： A(I, 2:N-1) = B(I-1,2:N-1) + C T:

20、 B(I, 2:N-1) = A(I, 3:N) * 2 endfor 但此向量化運算的結果不對！為什么？,（a）存在依賴T f S, 方向為（1，0） （b）存在依賴T a S, 方向為（0, 1）,國家高性能計算中心（合肥）,28,2020/8/5,考查以下循環(huán)可向量化的情況。 （1）for I = 2 to N 1 do for J = 2 to N 1 do S : A(I, J) = B( I-1, J ) + C T : B(I, J) = A(I, J+1) * 2 endfor endfor 如果向量化內層的J循環(huán)，則形成： for I = 2 to N 1 do S： A(I

21、, 2:N-1) = B(I-1,2:N-1) + C T: B(I, 2:N-1) = A(I, 3:N) * 2 endfor,向量化內層循環(huán)是錯誤的哦！ 舉例來說，在（I2，J2）的迭代中，原來的內層循環(huán)中語句T先行讀取了A(2,3)的舊值來計算B(2,2)；而在向量化后的循環(huán)中，向量化的語句S則在（I2）迭代中先行更新了A(2,3)的值；而隨后向量化語句T則只能使用新的A(2,3)來計算！顯然是錯誤的！,國家高性能計算中心（合肥）,29,2020/8/5,考查以下循環(huán)可向量化的情況。 （2） for I = 1 to N do for J = 1 to N do S : D(I, J)

22、 = A( I, J ) + C T : A(I+1, J+1) = B(I, J) * 2 endfor endfor 嘗試向量化內層循環(huán)如下： for I = 1 to N do S : D(I, 1:N) = A( I, 1:N ) + C T : A(I+1, 2:N+1) = B(I, 1:N) * 2 endfor,存在依賴T f S, 方向為（1，1）,向量化正確嗎？ 不存在（0，1）的T f S,國家高性能計算中心（合肥）,30,2020/8/5,（2） for I = 1 to N do for J = 1 to N do S : D(I, J) = A( I, J ) +

23、C T ：A(I+1, J+1) = B(I, J) * 2 endfor endfor,部分展開循環(huán)如下： I=1時：J = 1,2,N S(1,1): D(1,1) = A(1,1) T(1,1): A(2,2) = B(1,1) S(1,2): D(1,2) = A(1,2) T(1,2): A(2,3) = B(1,2) (外層 I 循環(huán)依然串行執(zhí)行,保持I層依賴關系，如 A(2,2)的寫與讀。) I=2時：J=1,2,N S(2,1): D(2,1) = A(2,1) T(2,1): A(3,2) = B(2,1) S(2,2): D(2,2) = A(2,2) T(2,2): A(

24、3,3) = B(2,2) ,向量化為： D(1,1:N) = A(1,1:N),向量化為： A(2,2:N+1) = B(1,1:N),向量化為： D(2,1:N) = A(2,1:N),向量化為： A(3,2:N+1) = B(2,1:N),國家高性能計算中心（合肥）,31,2020/8/5,循環(huán)并行化 將循環(huán)的迭代空間劃分成不同的子集，分布到不同的處理機上執(zhí)行（此時對各迭代子集的執(zhí)行次序不作要求）。一般用doall(或 par-do)表示將循環(huán)并行化。 可并行化循環(huán) 如果一個循環(huán)的各個迭代（子集）可按任意次序執(zhí)行而結果與串行執(zhí)行相同的話。 以下循環(huán)可以并行化： for I = 1 to

25、N dodoall I = 1 to N A(I) = A(I) + B(I) A(I) = A(I) + B(I) endfor enddoall,循環(huán)并行化,國家高性能計算中心（合肥）,32,2020/8/5,可并行化循環(huán)的充要條件 循環(huán)L=(L1,L2,. . ., Lm)中內層循環(huán)Lk可并行化當且僅當循環(huán)L中不存在層次為k的依賴關系，即不存在方向向量為（0,0,1k,*,*)(含k-1個前導零）的依賴關系（即由K層攜帶的依賴關系）。 考察以下循環(huán)：,for I = 1 to N do for J = 1 to M do X(I, J) = X( I, J-1) + X(I, J+1)

26、endfor endfor,L1: for I = 0 to 4 do L2: for J = 0 to 4 do S: X(I+1, J+2) = Y( I, J) + 1 T: Y(I+2, J+1) = X(I, J) + 1 endfor endfor,存在方向為(0,1)的依賴關系,存在方向為(1,1)的依賴關系： S T 和 T S,國家高性能計算中心（合肥）,33,2020/8/5,for I = 1 to N do for J = 1 to M do X(I, J) = X( I, J-1) + X(I, J+1) endfor endfor,L1: for I = 0 to

27、4 do L2: for J = 0 to 4 do S: X(I+1, J+2) = Y( I, J) + 1 T: Y(I+2, J+1) = X(I, J) + 1 endfor endfor,doall I = 1 to N for J = 1 to M do X(I, J) = X( I, J-1) + X(I, J+1) endfor enddoall,L1: for I = 0 to 4 do L2: doall J = 0 to 4 S: X(I+1, J+2) = Y( I, J) + 1 T: Y(I+2, J+1) = X(I, J) + 1 enddoall endfo

28、r,并行化 外層循環(huán)I,并行化內層循環(huán)J,國家高性能計算中心（合肥）,34,2020/8/5,循環(huán)變換,循環(huán)變換的主要目的在于發(fā)掘程序中更多的并行性 循環(huán)變換是改變循環(huán)中語句實例的執(zhí)行次序但不改變語句實例集合的程序變換技術。對于循環(huán)L中的語句實例S(i)和T(j)，如果存在T(j)依賴于S(i)，且在變換后的循環(huán)L中仍然有T(j)的執(zhí)行遲于S(i)，那么稱該循環(huán)變換合法，循環(huán)L和L等價。 循環(huán)變換技術很多，如循環(huán)交換、語句重排、循環(huán)分布與置換等等等等。,國家高性能計算中心（合肥）,35,2020/8/5,循環(huán)分布,循環(huán)分布（loop distribution） 是一種語句級變換，將一個循環(huán)分解

29、為多個小循環(huán)，每個小循環(huán)和原來的循環(huán)有相同的迭代空間，只是包含的語句少些。該變換主要用于： 分解出可向量化或可并行化的循環(huán) 將原循環(huán)分解為較小循環(huán)以改善cache局部性 創(chuàng)建緊嵌套循環(huán) 分解原循環(huán)為若干使用較少變量的循環(huán)以提高寄存器的使用效率 該變換根據語句依賴圖進行其上的強連通子圖分類，得到所謂凝聚圖，并按其中的偏序關系執(zhí)行分解后的循環(huán),國家高性能計算中心（合肥）,36,2020/8/5,循環(huán)分布,考慮如下循環(huán)： L1：for I = 4 to 100 do S1 : A(I) = B(I-2) + 1 S2: C(I) = B(I-1) +F(I) S3: B(I) = A(I-1) +

30、2 S4: D(I) = D(I+1) + B(I-1) endfor,依賴關系如下： S1 f S3 S3 f S1 S3 f S2 S3 f S4 S4 a S4,國家高性能計算中心（合肥）,37,2020/8/5,S1,S2,S3,S4,S1，S3,S2,S4,語句依賴圖,凝聚圖,國家高性能計算中心（合肥）,38,2020/8/5,這樣把原循環(huán)分解成兩大部分： L1： for I = 4 to 100 do S1 : A(I) = B(I-2) + 1 S3: B(I) = A(I-1) + 2 endfor L2：for I = 4 to 100 do S2: C(I) = B(I-1

31、) +F(I) endfor L3：for I = 4 to 100 do S4: D(I) = D(I+1) + B(I-1) endfor,語句實例執(zhí)行次序為： （1）首先執(zhí)行循環(huán)L1 （2）L1執(zhí)行完后，可同時執(zhí)行循環(huán)L2和L3 此外： 循環(huán)L2可以并行化執(zhí)行； 循環(huán)L3可以向量化執(zhí)行；,國家高性能計算中心（合肥）,39,2020/8/5,語句重排,語句重排（statement reordering)是基于語句依賴圖的程序變換，它改變語句的詞法順序但不改變語句間依賴關系。該變換常用于循環(huán)向量化。當循環(huán)中語句間有循環(huán)依賴關系時，可通過此變換將與語句執(zhí)行順序相反的依賴關系改變?yōu)榕c語句執(zhí)行順序

32、一致的依賴關系，從而使循環(huán)向量化。 考慮如下循環(huán)例1： L : for I = 2 to N do S1 : A(I) = B(I) + C(I+1) S2: D(I) = A(I+1) + 1 S3: C(I) = D(I) endfor,國家高性能計算中心（合肥）,40,2020/8/5,上述循環(huán)中依賴關系為： S2 a S1 S1 a S3 和 S2 f S3，其中依賴關系 S2 a S1使得循環(huán)不能向量化。,S1,S2,S3,原語句依賴圖,語句重排,S2,S1,S3,重排后的語句依賴圖,國家高性能計算中心（合肥）,41,2020/8/5,語句重排后，原來的循環(huán)可以向量化,語句順序為：

33、S2：D(2:N) = A(3:N+1) + 1 S1 : A(2:N) = B(2:N) + C(3:N+1) S3: C(2:N) = D(2:N),國家高性能計算中心（合肥）,42,2020/8/5,循環(huán)置換,循環(huán)置換(loop permutation)是改變循環(huán)位置的程序變換，屬于迭代級的變換，而循環(huán)交換即是此種變換的特例。該變換有如下特點： 置換外層無循環(huán)依賴的循環(huán)與內層有依賴的循環(huán)，使得置換后內層可向量化； 置換無依賴的循環(huán)到外層使得整個循環(huán)嵌套可以并行執(zhí)行，可增加每次迭代的并行粒度并減少障礙同步次數； 在有多層可向量化的循環(huán)時，置換范圍較大的循環(huán)到外層可以增加向量的長度。,國家高

34、性能計算中心（合肥）,43,2020/8/5,考慮如下循環(huán)例2 ： L1 : for I = 1 to M do L2: for J = 1 to M do S : B(I,J) = A(I,J-1) T : A(I,J) = B(I,J) * C(I,J) endfor endfor 循環(huán)中存在(0,1)的依賴關系TS，不能對內層向量化?？梢岳醚h(huán)置換（交換）： L2: for J = 1 to M do L1: for I = 1 to M do 此時，上述循環(huán)嵌套在內層可以向量化！,國家高性能計算中心（合肥）,44,2020/8/5,再考慮以下循環(huán)例3 ： for I = 2 to N

35、 do for J = 2 to N do S: A(I,J) = ( A(I-1,J) + A(I+1,J) ) /2 endfor endfor 此循環(huán)中依賴關系：方向向量為(1,0)的S f S和(1,0)的S a S；因此循環(huán)嵌套中外層不可并行，內層可以并行(沒有依賴關系），但并行粒度僅為一條語句。可以采用交換循環(huán)的方式： for J = 2 to N do for I = 2 to N do 此時外層循環(huán)可以并行，其粒度為一個（內層）循環(huán)。,國家高性能計算中心（合肥）,45,2020/8/5,循環(huán)置換的充要條件： 假定P是mXm的置換矩陣，由P定義的m層循環(huán)嵌套L的置換是合法的，當且僅當對于L的每一個方向向量，均有 P 0 成立。 這里mXm的置換矩陣P定義為： 每個元素非0即1 每行有且僅有一個元素為1 每列有且僅有一個元素為1 令(i)表示P中第i列中為1的元素所在的行號，則函數：i (i)是集合1,2,m上的一個置換，它完全確定矩陣P。P可以表示為：,1, 2, , m (1), (2), (m),P ,或,(1), (2), (m),國家高性能計算中心（合肥）,46,2020/8/5