并行編譯簡介

1、并行編譯簡介國家高性能計算中心（合肥）22022-3-7并行編譯簡介國家高性能計算中心（合肥）32022-3-7并行編譯器的組成及任務(wù)國家高性能計算中心（合肥）42022-3-7數(shù)據(jù)依賴關(guān)系國家高性能計算中心（合肥）52022-3-7依賴關(guān)系示例國家高性能計算中心（合肥）62022-3-7依賴關(guān)系示例依賴關(guān)系：國家高性能計算中心（合肥）72022-3-7數(shù)據(jù)依賴關(guān)系表示同一個存儲單元表示同一個存儲單元M國家高性能計算中心（合肥）82022-3-7依賴距離和依賴向量 令 =(1,2,n) 和 =(1,2,n)是n層循環(huán)內(nèi)的n個整數(shù)下標(biāo)向量，假定 和 存在數(shù)據(jù)相關(guān)性，則依賴距離向量依賴距離向量（D

2、ependent Distance Vector）D = (D1,D2,Dn)定義為-；而依賴方向向量依賴方向向量（Dependent Direction Vector）d = (d1,d2,dn)定義為：iiiiiii 國家高性能計算中心（合肥）92022-3-7國家高性能計算中心（合肥）102022-3-7語句依賴圖和迭代依賴圖-國家高性能計算中心（合肥）112022-3-7語句依賴圖示例國家高性能計算中心（合肥）122022-3-7 語句T流依賴于語句S，即S f T，滿足依賴關(guān)系的偶對集合為： | i = j -1 ; 5 | i = j -1 ; 5j j200 200 | i =

3、j -3 ; 7 | i = j -3 ; 7j j200 200 語句S流依賴于語句T，即T f S，滿足依賴關(guān)系的偶對集合為： | i = j -2 ; 6 | i = j -2 ; 6j j200 200 語句S輸出依賴于語句U，即 U o S ，滿足依賴關(guān)系的偶對集合為： | i = j -1 ; 5 | i = j -1 ; 5j j200 200 語句T反依賴于語句U，即U a T ，滿足依賴關(guān)系的偶對集合為： | j = 2 | j = 2* *i + 1 ; 4i + 1 ; 4i99i99 語句語句T T是否流依賴于語句是否流依賴于語句U U呢？呢？國家高性能計算中心（合肥）

4、132022-3-7語句依賴圖示例國家高性能計算中心（合肥）142022-3-7迭代依賴圖示例（1）國家高性能計算中心（合肥）152022-3-7迭代依賴圖（1）國家高性能計算中心（合肥）162022-3-7迭代依賴圖示例（2）國家高性能計算中心（合肥）172022-3-7 語句T流依賴于語句S，即S f T，滿足依賴關(guān)系的偶對： S(i1,i2), T(j1,j2) | j1 = i1+1, j2=i2-1,0i13, 1i24 ，距離向量為(1,-1)，方向向量為(1, -1)。此依賴關(guān)系由循環(huán)L1攜帶； 語句S流依賴于語句T，即T f S，滿足依賴關(guān)系的偶對： T(i1,i2), S(j

5、1,j2) | j1 = i1, j2=i2+1,0i14, 0i23 ，距離向量為(0,1)，方向向量為(0, 1)。此依賴關(guān)系由循環(huán)L2攜帶； 語句U流依賴于語句T，即T f U，滿足依賴關(guān)系的偶對： T(i1,i2), U(j1,j2) | j1 = i1, j2=i2,0i14, 0i24 ，距離向量為(0,0)，方向向量為(0,0)。此依賴關(guān)系與循環(huán)無關(guān)。國家高性能計算中心（合肥）182022-3-70 01 12 23 34 4i i1 12 23 34 4j j國家高性能計算中心（合肥）192022-3-7國家高性能計算中心（合肥）202022-3-7依賴關(guān)系方程國家高性能計算中

6、心（合肥）212022-3-7依賴關(guān)系方程(丟番圖方程）國家高性能計算中心（合肥）222022-3-7國家高性能計算中心（合肥）232022-3-7國家高性能計算中心（合肥）242022-3-7循環(huán)向量化 循環(huán)向量化將僅含有數(shù)組賦值語句的循環(huán)L轉(zhuǎn)換成等價的向量語句如：循環(huán)for I = 1 to N doS: A(I) = D(I) * ET: C(I) = A(I) + B(I)endfor可以改寫為等價等價的向量語句：S:A(1:N) = D(1:N) * ET:C(1:N) = A(1:N) + B(1:N)國家高性能計算中心（合肥）252022-3-7 可向量化循環(huán)如果將循環(huán)內(nèi)的數(shù)組賦

7、值改為相應(yīng)的向量語句后，按原來語句次序執(zhí)行所得結(jié)果與原來串行執(zhí)行一樣，那么. . . 但以下循環(huán)不可向量化：for I = 1 to N doS: A(I) = A(I-1) + 1; /不能寫成A(1:N) = A(0:N-1) + 1endfor而以下循環(huán)卻可以向量化：for I = 1 to N doS1: A(I) = A(I+1) + 1; /可以寫成A(1:N) = A(2:N1) + 1endfor為什么？國家高性能計算中心（合肥）262022-3-7 可向量化循環(huán)的充要條件對于循環(huán)L=(L1,L2,. . ., Lm)其最內(nèi)層循環(huán)Lm可向量化當(dāng)且僅當(dāng)：Lm中任意兩個語句S和T，

8、（1） 當(dāng)S 0 P 0 成立。成立。這里mXm的置換矩陣P定義為： 每個元素非0即1 每行有且僅有一個元素為1 每列有且僅有一個元素為1令(i)表示P中第i列中為1的元素所在的行號，則函數(shù)：i (i)是集合1,2,m上的一個置換，它完全確定矩陣P。P可以表示為：1, 2, , m(1), (2), (m) P 或 (1), (2), (m)國家高性能計算中心（合肥）462022-3-7 考慮循環(huán)例2和例3：對于例2，置換矩陣P = 2, 1 , 而原循環(huán)中的方向向量為 = (0,1), P = (0,1) 2,1 = ( 1,0 ) 0。因此該循環(huán)交換是合法的。 對于例3，置換矩陣P = 2

9、, 1 , 而原循環(huán)中的方向向量為 = (1,0), P = (1,0) 2,1 = ( 0,1 ) 0。因此該循環(huán)交換是合法的。這里P=2,1 其矩陣形式為：而P= 3, 2, 1的矩陣形式為：0 11 0國家高性能計算中心（合肥）472022-3-7循環(huán)逆轉(zhuǎn) 循環(huán)逆轉(zhuǎn)(loop reversal)顛倒循環(huán)中迭代執(zhí)行的順序，顛倒循環(huán)中迭代執(zhí)行的順序，改變了循環(huán)迭代方向的變換，也使得變換循環(huán)中方向改變了循環(huán)迭代方向的變換，也使得變換循環(huán)中方向向量發(fā)生逆轉(zhuǎn)向量發(fā)生逆轉(zhuǎn)。 如果循環(huán)在逆轉(zhuǎn)變換后，它的方向向量均為正向量，則稱該變換前后的循環(huán)等價，該變換是合法的。考慮如下循環(huán)例4：for I = 1

10、to 100 do for J = 1 to 5 doS: A(I,J) = A(I-1,J+1) +1 endforendfor國家高性能計算中心（合肥）482022-3-7 循環(huán)例4的迭代依賴圖如下，可知它含有方向向量為(1,-1)的依賴關(guān)系，其內(nèi)層循環(huán)可以并行化（但粒度為5次迭代），其外層不能并行化，也不能進行循環(huán)交換。（為什么？）對循環(huán)J進行并行，粒度為5次迭代國家高性能計算中心（合肥）492022-3-7但對例4中，循環(huán)J進行逆轉(zhuǎn)，則方向向量變?yōu)?1,1)?？梢詫ρh(huán)嵌套進行循環(huán)交循環(huán)交換換。此時內(nèi)層循環(huán)I可以并行化（粒度為100次迭代?。?，迭代依賴圖如右所示：for J = 5 downto 1 do for I = 1 to 100 doS: A(I,J) = A(I-1,J+1) +1 endforendfor國家高性能計算中心（合肥）502022-3-7 圈收縮(cycle shrinking)此變換技術(shù)一般用于依賴距離大于1的循環(huán)中，它將一個串行循環(huán)分成兩個緊嵌套循環(huán)，其中外層依然串行執(zhí)行，而內(nèi)層則是并行執(zhí)行（一般粒