并行計算,第一級,第二級,第三級,第一級,第二級,第三級,國家高性能計算中心（合肥）,*,數(shù)據(jù)劃分與處理器指派,帶狀劃分方法,:,又叫,行列劃分,，就是將矩陣的整行或整列地分成若干組，各組指派給一個處理器。,四個處理器上,1616,矩陣帶狀劃分,循環(huán)程序并行化的一般方法,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,例,3.1,設(shè)矩陣,A,有,n,行和,m,列，對其串行處理的程序段如下：,for,i=1,to,n,do,for,j=1,to,m,do,Process(ai,j,),endfor,endfor,其中，,Process(ai,j,),表示對矩陣元素,ai,j,某種處理過程。設(shè)有,p,個處理器，令，。,行劃分：,在采用行劃分的情況下，例,3.1,串行程序段可轉(zhuǎn)化為如下的并行程序段：,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,串行程序段可轉(zhuǎn)化為如下的并行程序段：,for,k=1,to,p,par-do,for,j1=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,串行程序段可轉(zhuǎn)化為如下的并行程序段：,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,串行程序段可轉(zhuǎn)化為如下并行程序段：,for,k=1,to,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),所示的,循環(huán)棋盤劃分,（,Cyclic-checker Board Partitioning,）。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,四個處理器上,44,矩陣棋盤劃分,棋盤劃分比帶狀劃分可開發(fā)更高的并行度。例如，對于一個的方陣，棋盤劃分最多可使用,n2,個處理器；而帶狀劃分可用的處理器數(shù)不能多于,n,個。,數(shù)據(jù)劃分與處理器指派,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,3.,數(shù)據(jù)劃分準(zhǔn)則,:,并行粒度準(zhǔn)則：,若多處理機(jī)系統(tǒng)有,p,臺處理器，所有工作的處理器均經(jīng)由一單獨(dú)的全局信號燈同步，要是某一項給定的任務(wù)在其完成后要求同步時的最壞時間復(fù)雜度為,t(m,),，那么最大可能加速比為 。,數(shù)據(jù)相關(guān)性準(zhǔn)則,：,劃分后的數(shù)據(jù)要指派給各處理器去執(zhí)行一些操作，所以劃分應(yīng)該減少處理器間的通信，把那些彼此相關(guān)的數(shù)據(jù)盡可能分配到同一個處理器上，以使各處理器能獨(dú)立地工作或只進(jìn)行少量的通信。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,4.,基于數(shù)據(jù)內(nèi)部相關(guān)分析的劃分,數(shù)據(jù)內(nèi)部相關(guān)分析是指同一數(shù)據(jù)劃分的相關(guān)分析。,例,3.2,設(shè),A,為一個,n,階方陣，有如下串行程序段：,for i=1 to n do,for j=1 to n do,ai,j,=ai-1,j,endfor,endfor,分析矩陣,A,的元素下標(biāo),i,和,j,，則,i,和,j,的相關(guān)方向向量為，各列之間數(shù)據(jù)無任何相關(guān)關(guān)系。因此對矩陣,A,可按列劃分。,串行程序段可轉(zhuǎn)化為如下并行程序段：,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ù)內(nèi)部相關(guān)分析的劃分,例,3.3,設(shè),A,為矩陣，有如下串行程序段：,for i=1 to n do,for j=1 to n do,a3i,2j=a3i-2,2j-1,endfor,endfor,其相關(guān)方向向量為，可知行和列間同時存在數(shù)據(jù)相關(guān)。在此我們可以試用行劃分、列劃分和方塊劃分,.,在行劃分的情況下令,例,3.3,的串行程序段可以轉(zhuǎn)化為如下的并行程序段：,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ù)外部相關(guān)分析的劃分,所謂數(shù)據(jù)外部相關(guān)分析是指對不同數(shù)據(jù)劃分的相關(guān)分析。,例,3.4,設(shè),A,和,B,均為,n,階矩陣，有如形式的下串行程序段：,for i=1 to n do,for j=1 to n do,endfor,endfor,其中 、都是,i,，,j,的線性組合：,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關(guān)分析的劃分,現(xiàn)在對 進(jìn)行一種數(shù)據(jù)劃分，也有一種數(shù)據(jù)劃分與其對應(yīng)，使它們被劃分的數(shù)據(jù)塊之間無數(shù)據(jù)相關(guān)關(guān)系，相應(yīng)處理器之間不產(chǎn)生通信開銷。劃分方法如下：,對 數(shù)組，設(shè)其劃分后某一子陣列的元素下標(biāo)滿足：,c,為某一常數(shù)，對 數(shù)組，劃分后相應(yīng)子陣列的元素下標(biāo)有如下關(guān)系：,將式 代入 、式得：,對于,A,有,對于,B,有,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關(guān)分析的劃分,經(jīng)變換可寫為：,劃分結(jié)果要使得相關(guān)數(shù)據(jù)被劃分至同一處理器中，各處理器間無通信開銷，則必須滿足以下條件：,對于固定值,c,，由此式可求得 、及 、。,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關(guān)分析的劃分,例,3.5,.,設(shè),A,為,n,階矩陣，,B,為 矩陣，對如下二重循環(huán)計算：,for,i=2,to,n,do,for,j=2,to,n,do,endfor,endfor,存在如下數(shù)據(jù)相關(guān)關(guān)系：,即,滿足上述關(guān)系的 有很多組，例如：取 即對常數(shù),c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,來劃分，對于下標(biāo)空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構(gòu)成了一個獨(dú)立執(zhí)行的部分,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關(guān)分析的劃分,滿足上述關(guān)系的 有很多組，例如：取 即對常數(shù),c,，,B,按,i,-,j,=,c,，,A,按,j,=,c,來劃分，對于下標(biāo)空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構(gòu)成了一個獨(dú)立執(zhí)行的部分。,迭代空間數(shù)據(jù)相關(guān)圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,數(shù)據(jù)劃分與處理器指派,5.,基于數(shù)據(jù)外部相關(guān)分析的劃分,再如：取 即對常數(shù),c,，,B,按,j,=,c,、,A,按,i,=,c,-1,來劃分，對于下標(biāo)空間所允許的每一個,c,值，滿足以上二式的,A,，,B,元素構(gòu)成了一個獨(dú)立執(zhí)行的部分。,按圖中的虛線所示劃分?jǐn)?shù)據(jù)將保證對應(yīng)的,A,，,B,元素被分配到相同的處理器中，計算時處理器之間不發(fā)生通信。由于斜線劃分不利于并行計算，故采用第二種劃分方法，進(jìn)而可得出相應(yīng)的并行程序：,for,i=2,to,n,par-do,for,j=2,to,n,do,endfor,endfor,迭代空間數(shù)據(jù)相關(guān)圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),1.,循環(huán)交換,通過交換內(nèi)外循環(huán)的先后次序?qū)ρh(huán)體結(jié)構(gòu)進(jìn)行調(diào)整，以實(shí)現(xiàn)劃分后處理器內(nèi)部數(shù)據(jù)的局部相關(guān)，從而減少通信開銷，提高計算的并行性。對如下循環(huán)：,for,i=1,to,n,do,for,j=1,to,n,do,ai,j,=ai-1,j,endfor,endfor,按數(shù)據(jù)相關(guān)性準(zhǔn)則，的相關(guān)方向向量為 ，應(yīng)該對矩陣,A,按列劃分，按并行粒度準(zhǔn)則，循環(huán)的最外層是,i,，應(yīng)該對矩陣,A,按行劃分，兩條準(zhǔn)則發(fā)生矛盾?，F(xiàn)交換,I,j,循環(huán)的先后次序。通過重構(gòu)得到如下并行程序：,for j=1 to n par-do,for i=1 to n do,ai,j,=ai-1,j,endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),1.,循環(huán)交換,上例中，對,i,的循環(huán)具有相關(guān)性，對它應(yīng)該串行執(zhí)行，因此可利用循環(huán)交換，使無相關(guān)性的分量調(diào)換至最外層。在循環(huán)交換時，應(yīng)該注意循環(huán)初值和終值的變化，對于如下循環(huán)：,for,i=1,to,n,do,for,j=i+1,to,n,do,Process(ai,j,),endfor,endfor,由于內(nèi)層循環(huán),j,的初值是外層循環(huán),i,的函數(shù)，在循環(huán)交換后，這樣的初值和終值也相應(yīng)地變化為：,for,j=2,to,n,do,for,i=1,to,j-1,do,Process(ai,j,),endfor,endfor,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),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,有兩個相關(guān)向量：及 。,由于行列間皆存在相關(guān)關(guān)系，所以既不能進(jìn)行行,列塊劃分、方塊劃分，也不能進(jìn)行行列循環(huán)劃分。,但如果我們對,j,循環(huán)用,i,循環(huán)進(jì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ù)相關(guān)圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),2.,拉伸法,由圖可見，對相同,j,值，沿,i,方向的計算無相關(guān)關(guān)系，因此交換,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,矩陣進(jìn)行行塊劃分,拉伸后的數(shù)據(jù)相關(guān)圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),2.,拉伸法,例,3.7.,設(shè),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ù)相關(guān)圖,國家高性能計算中心（合肥）,循環(huán)程序并行化的一般方法,循環(huán)重構(gòu),2.,拉伸法,若按串行程序所定義的執(zhí)行順序，對,A,中的元素的可并行執(zhí)行順序如前面圖所示。圖中,(,i,j,),位置上的數(shù)字,T,表示元素,a,i,j,可并