并行編譯簡(jiǎn)介

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

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

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

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

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

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

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

8、（1） 當(dāng)S 0 P 0 成立。成立。這里mXm的置換矩陣P定義為： 每個(gè)元素非0即1 每行有且僅有一個(gè)元素為1 每列有且僅有一個(gè)元素為1令(i)表示P中第i列中為1的元素所在的行號(hào)，則函數(shù)：i (i)是集合1,2,m上的一個(gè)置換，它完全確定矩陣P。P可以表示為：1, 2, , m(1), (2), (m) P 或 (1), (2), (m)國(guó)家高性能計(jì)算中心（合肥）462022-3-7 考慮循環(huán)例2和例3：對(duì)于例2，置換矩陣P = 2, 1 , 而原循環(huán)中的方向向量為 = (0,1), P = (0,1) 2,1 = ( 1,0 ) 0。因此該循環(huán)交換是合法的。 對(duì)于例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國(guó)家高性能計(jì)算中心（合肥）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)變換后，它的方向向量均為正向量，則稱(chēng)該變換前后的循環(huán)等價(jià)，該變換是合法的?？紤]如下循環(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國(guó)家高性能計(jì)算中心（合肥）482022-3-7 循環(huán)例4的迭代依賴(lài)圖如下，可知它含有方向向量為(1,-1)的依賴(lài)關(guān)系，其內(nèi)層循環(huán)可以并行化（但粒度為5次迭代），其外層不能并行化，也不能進(jìn)行循環(huán)交換。（為什么？）對(duì)循環(huán)J進(jìn)行并行，粒度為5次迭代國(guó)家高性能計(jì)算中心（合肥）492022-3-7但對(duì)例4中，循環(huán)J進(jìn)行逆轉(zhuǎn)，則方向向量變?yōu)?1,1)?？梢詫?duì)循環(huán)嵌套進(jìn)行循環(huán)交循環(huán)交換換。此時(shí)內(nèi)層循環(huán)I可以并行化（粒度為100次迭代?。?，迭代依賴(lài)圖如右所示：for J = 5 downto 1 do for I = 1 to 100 doS: A(I,J) = A(I-1,J+1) +1 endforendfor國(guó)家高性能計(jì)算中心（合肥）502022-3-7 圈收縮(cycle shrinking)此變換技術(shù)一般用于依賴(lài)距離大于1的循環(huán)中，它將一個(gè)串行循環(huán)分成兩個(gè)緊嵌套循環(huán)，其中外層依然串行執(zhí)行，而內(nèi)層則是并行執(zhí)行（一般粒