《并行計算-多媒體課件-并行程序設計-ch03并行程序設計簡》由會員分享，可在線閱讀，更多相關《并行計算-多媒體課件-并行程序設計-ch03并行程序設計簡（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、并行計算,第一級,第二級,第三級,第一級,第二級,第三級,國家高性能計算中心（合肥）,*,數(shù)據(jù)劃分與處理器指派,帶狀劃分方法,:,又叫,行列劃分,，就是將矩陣的整行或整列地分成若干組，各組指派給一個處理器。,四個處理器上,1616,矩陣帶狀劃分,循環(huán)程序并行化的一般方法,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,例,3.1,設矩陣,A,有,n,行和,m,列，對其串行處理的程序段如下：,for,i=1,to,n,do,for,j=1,to,m,do,Process(ai,j,),endfor,endfor,其中，,Process(ai,j,),表示對矩陣元素,a

2、i,j,某種處理過程。設有,p,個處理器，令，。,行劃分：,在采用行劃分的情況下，例,3.1,串行程序段可轉化為如下的并行程序段：,for,k=1,to,p,par-do,for,i1=1,to,r,do,for,j=1,to,m,do,Process(a(k-1)r+i1,j),endfor,endfor,endfor,其中“,par-do”,表示對循環(huán)體用,p,個處理器并行執(zhí)行。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,列劃分：,在采用列劃分的情況下，例,3.1,串行程序段可轉化為如下的并行程序段：,for,k=1,to,p,par-do,for,j1=

3、1,to,s,do,for,i=1,to,n,do,Process(ai,(k-1)s+j1),endfor,endfor,endfor,行循環(huán)劃分：,在采用行循環(huán)劃分的情況下，例,3.1,串行程序段可轉化為如下的并行程序段：,for,k=1,to,p,par-do,for,i1=1,to,r,do,for,j=1,to,m,do,Process(ai1-1p+k,j),endfor,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,列循環(huán)劃分：,在采用列循環(huán)劃分的情況下，例,3.1,串行程序段可轉化為如下并行程序段：,for,k=1,to

4、,p,par-do,for,i=1,to,n,do,for,j1=1,to,s,do,Process(ai,(j1-1)p+k),endfor,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,2,、,塊狀劃分方法,所謂塊狀劃分又叫,棋盤劃分,（,Checker Board Partitioning,），就是將矩陣劃分成若干個子矩陣，每個子矩陣指派給一個處理器，此時任一處理器均不包含整行或整列。,可分為圖,3.11(a),所示的,塊棋盤劃分,（,Block-checker Board Partitioning,）和圖,3.11(b),所示的

5、,循環(huán)棋盤劃分,（,Cyclic-checker Board Partitioning,）。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,四個處理器上,44,矩陣棋盤劃分,棋盤劃分比帶狀劃分可開發(fā)更高的并行度。例如，對于一個的方陣，棋盤劃分最多可使用,n2,個處理器；而帶狀劃分可用的處理器數(shù)不能多于,n,個。,數(shù)據(jù)劃分與處理器指派,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,3.,數(shù)據(jù)劃分準則,:,并行粒度準則：,若多處理機系統(tǒng)有,p,臺處理器，所有工作的處理器均經(jīng)由一單獨的全局信號燈同步，要是某一項給定的任務在其完成后要求同步時的最壞時間復雜度為,t

6、(m,),，那么最大可能加速比為 。,數(shù)據(jù)相關性準則,：,劃分后的數(shù)據(jù)要指派給各處理器去執(zhí)行一些操作，所以劃分應該減少處理器間的通信，把那些彼此相關的數(shù)據(jù)盡可能分配到同一個處理器上，以使各處理器能獨立地工作或只進行少量的通信。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,4.,基于數(shù)據(jù)內部相關分析的劃分,數(shù)據(jù)內部相關分析是指同一數(shù)據(jù)劃分的相關分析。,例,3.2,設,A,為一個,n,階方陣，有如下串行程序段：,for i=1 to n do,for j=1 to n do,ai,j,=ai-1,j,endfor,endfor,分析矩陣,A,的元素下標,i,和,j,

7、，則,i,和,j,的相關方向向量為，各列之間數(shù)據(jù)無任何相關關系。因此對矩陣,A,可按列劃分。,串行程序段可轉化為如下并行程序段：,for,k=1,to,P,Par-do,for,j1=1,to,m,do,for,i=1,to,n,do,ai,(k-1)m+j1=ai-1,(k-1)m+j1,endfor,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,4.,基于數(shù)據(jù)內部相關分析的劃分,例,3.3,設,A,為矩陣，有如下串行程序段：,for i=1 to n do,for j=1 to n do,a3i,2j=a3i-2,2j-1,endf

8、or,endfor,其相關方向向量為，可知行和列間同時存在數(shù)據(jù)相關。在此我們可以試用行劃分、列劃分和方塊劃分,.,在行劃分的情況下令,例,3.3,的串行程序段可以轉化為如下的并行程序段：,for,k=1,to,P,Par-do,for,i1=1,to,m,do,for,j=1,to,n,do,a3(k-1)m+3i1,2j=a 3(k-1)m+3i1-2,2j-1,endfor,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關分析的劃分,所謂數(shù)據(jù)外部相關分析是指對不同數(shù)據(jù)劃分的相關分析。,例,3.4,設,A,和,B,

9、均為,n,階矩陣，有如形式的下串行程序段：,for i=1 to n do,for j=1 to n do,endfor,endfor,其中 、都是,i,，,j,的線性組合：,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關分析的劃分,現(xiàn)在對 進行一種數(shù)據(jù)劃分，也有一種數(shù)據(jù)劃分與其對應，使它們被劃分的數(shù)據(jù)塊之間無數(shù)據(jù)相關關系，相應處理器之間不產(chǎn)生通信開銷。劃分方法如下：,對 數(shù)組，設其劃分后某一子陣列的元素下標滿足：,c,為某一常數(shù)，對 數(shù)組，劃分后相應子陣列的元素下標有如下關系：,將式 代入 、式得：,對于,A,有,對于,B,有,國家高性能計

10、算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關分析的劃分,經(jīng)變換可寫為：,劃分結果要使得相關數(shù)據(jù)被劃分至同一處理器中，各處理器間無通信開銷，則必須滿足以下條件：,對于固定值,c,，由此式可求得 、及 、。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關分析的劃分,例,3.5,.,設,A,為,n,階矩陣，,B,為 矩陣，對如下二重循環(huán)計算：,for,i=2,to,n,do,for,j=2,to,n,do,endfor,endfor,存在如下數(shù)據(jù)相關關系：,即,滿足上述關系的 有很多組，例如：取 即對常數(shù),

11、c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,來劃分，對于下標空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構成了一個獨立執(zhí)行的部分,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關分析的劃分,滿足上述關系的 有很多組，例如：取 即對常數(shù),c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,來劃分，對于下標空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構成了一個獨立執(zhí)行的部分。,迭代空間數(shù)據(jù)相關圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關

12、分析的劃分,再如：取 即對常數(shù),c,，,B,按,j,=,c,、,A,按,i,=,c,-1,來劃分，對于下標空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構成了一個獨立執(zhí)行的部分。,按圖中的虛線所示劃分數(shù)據(jù)將保證對應的,A,，,B,元素被分配到相同的處理器中，計算時處理器之間不發(fā)生通信。由于斜線劃分不利于并行計算，故采用第二種劃分方法，進而可得出相應的并行程序：,for,i=2,to,n,par-do,for,j=2,to,n,do,endfor,endfor,迭代空間數(shù)據(jù)相關圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構,1.,循環(huán)交換,通過交換內外循環(huán)的先后

13、次序對循環(huán)體結構進行調整，以實現(xiàn)劃分后處理器內部數(shù)據(jù)的局部相關，從而減少通信開銷，提高計算的并行性。對如下循環(huán)：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=ai-1,j,endfor,endfor,按數(shù)據(jù)相關性準則，的相關方向向量為 ，應該對矩陣,A,按列劃分，按并行粒度準則，循環(huán)的最外層是,i,，應該對矩陣,A,按行劃分，兩條準則發(fā)生矛盾?，F(xiàn)交換,I,j,循環(huán)的先后次序。通過重構得到如下并行程序：,for j=1 to n par-do,for i=1 to n do,ai,j,=ai-1,j,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序

14、并行化的一般方法,循環(huán)重構,1.,循環(huán)交換,上例中，對,i,的循環(huán)具有相關性，對它應該串行執(zhí)行，因此可利用循環(huán)交換，使無相關性的分量調換至最外層。在循環(huán)交換時，應該注意循環(huán)初值和終值的變化，對于如下循環(huán)：,for,i=1,to,n,do,for,j=i+1,to,n,do,Process(ai,j,),endfor,endfor,由于內層循環(huán),j,的初值是外層循環(huán),i,的函數(shù)，在循環(huán)交換后，這樣的初值和終值也相應地變化為：,for,j=2,to,n,do,for,i=1,to,j-1,do,Process(ai,j,),endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一

15、般方法,循環(huán)重構,2.,拉伸法,例,3.6.,在下列程序中：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=ai-1,j+ai,j-1,endfor,endfor,有兩個相關向量：及 。,由于行列間皆存在相關關系，所以既不能進行行,列塊劃分、方塊劃分，也不能進行行列循環(huán)劃分。,但如果我們對,j,循環(huán)用,i,循環(huán)進行拉伸，拉伸系數(shù)為,1,，得到如下程序：,for,i=1,to,n,do,for,j=i+1,to,i+n,do,ai,j-i,=ai-1,j-i+ai,j-i-1,endfor,endfor,拉伸前的數(shù)據(jù)相關圖,國家高性能計算中心（合肥）,循環(huán)程序并行化

16、的一般方法,循環(huán)重構,2.,拉伸法,由圖可見，對相同,j,值，沿,i,方向的計算無相關關系，因此交換,i,，,j,循環(huán)先后次序，,i,循環(huán)可并行執(zhí)行，得到如下并行程序：,for,j=2,to,2n,do,for,i=max(1,j-n),to,min(n,j+1),par-do,ai,j-i,=ai-1,j-i+ai,j-i-1,endfor,endfor,由上述程序可見，由于各行之間的計算可以并行，因此對,A,矩陣進行行塊劃分,拉伸后的數(shù)據(jù)相關圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構,2.,拉伸法,例,3.7.,設,A,為,n,階矩陣，有串行程序如下：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=(ai,j+1+ai,j-1+ai+1,j+ai-1,j)/4,endfor,endfor,n=5,時的數(shù)據(jù)相關圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構,2.,拉伸法,若按串行程序所定義的執(zhí)行順序，對,A,中的元素的可并行執(zhí)行順序如前面圖所示。圖中,(,i,j,),位置上的數(shù)字,T,表示元素,a,i,j,可并