



版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(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ù)依賴關(guān)系國(guó)家高性能計(jì)算中心(合肥)52022-3-7依賴關(guān)系示例國(guó)家高性能計(jì)算中心(合肥)62022-3-7依賴關(guān)系示例依賴關(guān)系:國(guó)家高性能計(jì)算中心(合肥)72022-3-7數(shù)據(jù)依賴關(guān)系表示同一個(gè)存儲(chǔ)單元表示同一個(gè)存儲(chǔ)單元M國(guó)家高性能計(jì)算中心(合肥)82022-3-7依賴距離和依賴向量 令 =(1,2,n) 和 =(1,2,n)是n層循環(huán)內(nèi)的n個(gè)整數(shù)下標(biāo)向量,假定 和 存在數(shù)據(jù)相關(guān)性,則依賴距離向量依賴距離向量(D
2、ependent Distance Vector)D = (D1,D2,Dn)定義為-;而依賴方向向量依賴方向向量(Dependent Direction Vector)d = (d1,d2,dn)定義為:iiiiiii 國(guó)家高性能計(jì)算中心(合肥)92022-3-7國(guó)家高性能計(jì)算中心(合肥)102022-3-7語(yǔ)句依賴圖和迭代依賴圖-國(guó)家高性能計(jì)算中心(合肥)112022-3-7語(yǔ)句依賴圖示例國(guó)家高性能計(jì)算中心(合肥)122022-3-7 語(yǔ)句T流依賴于語(yǔ)句S,即S f T,滿足依賴關(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流依賴于語(yǔ)句T,即T f S,滿足依賴關(guān)系的偶對(duì)集合為: | i = j -2 ; 6 | i = j -2 ; 6j j200 200 語(yǔ)句S輸出依賴于語(yǔ)句U,即 U o S ,滿足依賴關(guān)系的偶對(duì)集合為: | i = j -1 ; 5 | i = j -1 ; 5j j200 200 語(yǔ)句T反依賴于語(yǔ)句U,即U a T ,滿足依賴關(guān)系的偶對(duì)集合為: | j = 2 | j = 2* *i + 1 ; 4i + 1 ; 4i99i99 語(yǔ)句語(yǔ)句T T是否流依賴于語(yǔ)句是否流依賴于語(yǔ)句U U呢?呢?國(guó)家高性能計(jì)算中心(合肥)
4、132022-3-7語(yǔ)句依賴圖示例國(guó)家高性能計(jì)算中心(合肥)142022-3-7迭代依賴圖示例(1)國(guó)家高性能計(jì)算中心(合肥)152022-3-7迭代依賴圖(1)國(guó)家高性能計(jì)算中心(合肥)162022-3-7迭代依賴圖示例(2)國(guó)家高性能計(jì)算中心(合肥)172022-3-7 語(yǔ)句T流依賴于語(yǔ)句S,即S f T,滿足依賴關(guān)系的偶對(duì): S(i1,i2), T(j1,j2) | j1 = i1+1, j2=i2-1,0i13, 1i24 ,距離向量為(1,-1),方向向量為(1, -1)。此依賴關(guān)系由循環(huán)L1攜帶; 語(yǔ)句S流依賴于語(yǔ)句T,即T f S,滿足依賴關(guān)系的偶對(duì): T(i1,i2), S(j
5、1,j2) | j1 = i1, j2=i2+1,0i14, 0i23 ,距離向量為(0,1),方向向量為(0, 1)。此依賴關(guān)系由循環(huán)L2攜帶; 語(yǔ)句U流依賴于語(yǔ)句T,即T f U,滿足依賴關(guān)系的偶對(duì): T(i1,i2), U(j1,j2) | j1 = i1, j2=i2,0i14, 0i24 ,距離向量為(0,0),方向向量為(0,0)。此依賴關(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依賴關(guān)系方程國(guó)家高性能計(jì)算中
6、心(合肥)212022-3-7依賴關(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可以改寫為等價(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ǔ)句后,按原來語(yǔ)句次序執(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為什么?國(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)變換后,它的方向向量均為正向量,則稱該變換前后的循環(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的迭代依賴圖如下,可知它含有方向向量為(1,-1)的依賴關(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次迭代!),迭代依賴圖如右所示: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ù)一般用于依賴距離大于1的循環(huán)中,它將一個(gè)串行循環(huán)分成兩個(gè)緊嵌套循環(huán),其中外層依然串行執(zhí)行,而內(nèi)層則是并行執(zhí)行(一般粒
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 干燥性喉炎的護(hù)理查房
- 腹股溝黑素細(xì)胞痣護(hù)理
- 2025屆黑龍江省海林市朝鮮族中學(xué)物理高一第二學(xué)期期末調(diào)研模擬試題含解析
- 藥物性肝硬化護(hù)理課件
- 肝周膿腫的護(hù)理課件
- 虛擬現(xiàn)實(shí)城市景觀設(shè)計(jì)-洞察闡釋
- 高端儀器出口競(jìng)爭(zhēng)力研究-洞察闡釋
- 2025屆遼寧省瓦房店市第三高級(jí)中學(xué)高一物理第二學(xué)期期末綜合測(cè)試試題含解析
- 財(cái)務(wù)信息化系統(tǒng)建設(shè)-洞察闡釋
- 2025年福建省廈門市湖里區(qū)雙十中學(xué)物理高一第二學(xué)期期末達(dá)標(biāo)檢測(cè)試題含解析
- 2025至2030中國(guó)燕窩行業(yè)市場(chǎng)運(yùn)行分析及競(jìng)爭(zhēng)格局與投資方向報(bào)告
- 2025年河北省中考語(yǔ)文試卷真題及答案詳解(精校打印版)
- 口服靶向藥講課件
- 12024-2025學(xué)年暑假安全教育主題班會(huì)課件
- 肝膽外科醫(yī)學(xué)科普
- 能源轉(zhuǎn)型與碳市場(chǎng)機(jī)制協(xié)同的路徑優(yōu)化研究
- 陽(yáng)光房制作安裝合同協(xié)議書范本8篇
- GB/T 45449-2025再生粉末高溫合金原料
- 工程投資人合同協(xié)議
- 包席合同協(xié)議
- 資產(chǎn)評(píng)估風(fēng)險(xiǎn)管理制度
評(píng)論
0/150
提交評(píng)論