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

上傳人:dfg****19 文檔編號(hào):248164274 上傳時(shí)間:2024-10-22 格式:PPT 頁數(shù):36 大?。?46KB
收藏 版權(quán)申訴 舉報(bào) 下載
并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯_第1頁
第1頁 / 共36頁
并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯_第2頁
第2頁 / 共36頁
并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯_第3頁
第3頁 / 共36頁

下載文檔到電腦,查找使用更方便

15 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯》由會(huì)員分享,可在線閱讀,更多相關(guān)《并行計(jì)算-多媒體課件-并行程序設(shè)計(jì)-ch08并行編譯(36頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。

1、并行計(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í)別,處理指令級并行調(diào)度,2024/10/22,3,國家高性能計(jì)算中

2、心(合肥),數(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,對,x,的定值;,T,反依賴于,S,;,(,3,)輸出依賴:,S,o,T,,若,xOUT,(,S,)且,xOUT,(,T,)但,S,較之,T,先對,x,進(jìn)行定

3、值;,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

4、):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,),表

5、示同一個(gè)存儲(chǔ)單元,M,(,3,)在,L,的順序執(zhí)行中,,S(i,),先于,T(j,),(,4,)在,L,的順序執(zhí)行中,,S(i,),之間,T(j,),沒有其他對,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,對,S,的依賴即為滿足上述條件的偶對(,S(i),T(j,),)的集合。,2024/10/22,7,國家高性能計(jì)算中心(合肥),依賴距離和依賴向量,令,=(,1,2,n,),和,=(

6、,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

7、(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)方向向量對計(jì)算循環(huán)體間相關(guān)性十分有用,其相關(guān)性是通過相關(guān)方向向量不是”,=”,號(hào)的外層循環(huán)傳遞的;相關(guān)距離向量指明在,同一存儲(chǔ)單元的兩次訪問之間循環(huán)迭代的實(shí)際距離,。它們對開發(fā)并行性或優(yōu)化存儲(chǔ)器層次結(jié)構(gòu)時(shí)起到指引作用。,2024/10/22,9,國家高性能計(jì)算中心(合肥),語句依賴圖和迭代依賴圖,語句依賴圖依賴關(guān)系,的有向圖。將語句,如,S,和,T,,看成結(jié)點(diǎn),若有,S,T,,則:,間接依賴關(guān)系 ,即依

8、賴關(guān)系的傳遞閉包。,若,S T,,則在語句依賴圖中存在,S,到,T,的一條路徑。,迭代依賴圖即(循環(huán))迭代之間的依賴關(guān)系。在循環(huán),L,中,若語句,T,依賴于語句,S,,即,S,T,。令,S(I),和,T(J),是滿足依賴關(guān)系的偶對,,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

9、),+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)系的偶對集合為:,|i=j-1;5,j,200 ,|i=j-3;7,j,200,語句,S,流依賴于語句,T,,即,T,f,S,,滿足依賴關(guān)系的偶對集合為:,|i=j-2;6,j,200,語句,S,輸出依賴于語句,U,,即,U,o,S,,滿足依賴關(guān)系的偶對集合為:,|i=j-1;5,j,200,語句,T,反依賴于語句,U,,即,U,a,T,,滿足依賴關(guān)系的偶對集合為:,|j=2

10、*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(,

11、i,j,),endfor,endfor,顯然,,S,f,S,。滿足依賴關(guān)系的偶對集合:,|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)=,

12、B(i1,i2+1),2,endfor,endfor,2024/10/22,16,國家高性能計(jì)算中心(合肥),語句,T,流依賴于語句,S,,即,S,f,T,,滿足依賴關(guān)系的偶對:,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)系的偶對:,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),

13、L2,攜帶;,語句,U,流依賴于語句,T,,即,T,f,U,,滿足依賴關(guān)系的偶對:,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/

14、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,2

15、0,國家高性能計(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,

16、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),對應(yīng)的數(shù)組變量會(huì)導(dǎo)致,S,和,T,之間的依賴。,2024/10/22,23,國家高性能計(jì)算中心(合肥),循環(huán)向量化,循環(huán)向量化,將僅含有數(shù)組賦值語句的循環(huán),L,轉(zhuǎn)換成等價(jià)

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!