并行程序設(shè)計(jì)簡介續(xù)

國家高性能計(jì)算中心（合肥）數(shù)據(jù)劃分與處理器指派帶狀劃分方法:又叫行列劃分，就是將矩陣的整行或整列地分成若干組，各組指派給一個處理器。四個處理器上16×16矩陣帶狀劃分循環(huán)程序并行化的一般方法

國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

數(shù)據(jù)劃分與處理器指派

例3.1

設(shè)矩陣A有n行和m列，對其串行處理的程序段如下：fori=1tondo

forj=1tomdoProcess(a[i,j])endforendfor其中，Process(a[i,j])表示對矩陣元素a[i,j]某種處理過程。設(shè)有p個處理器，令，。⑴行劃分：在采用行劃分的情況下，例3.1串行程序段可轉(zhuǎn)化為如下的并行程序段：fork=1toppar-dofori1=1tordoforj=1tomdoProcess(a[(k-1)r+i1,j])endforendforendfor其中“par-do”表示對循環(huán)體用p個處理器并行執(zhí)行。國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

數(shù)據(jù)劃分與處理器指派⑵列劃分：在采用列劃分的情況下，例3.1串行程序段可轉(zhuǎn)化為如下的并行程序段：fork=1toppar-doforj1=1tosdofori=1tondoProcess(a[i,(k-1)s+ j1])endforendforendfor⑶ 行循環(huán)劃分：在采用行循環(huán)劃分的情況下，例3.1串行程序段可轉(zhuǎn)化為如下的并行程序段：fork=1toppar-dofori1=1tordoforj=1tomdoProcess(a[i1-1]p+k,j)endforendfor endfor國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

數(shù)據(jù)劃分與處理器指派⑷ 列循環(huán)劃分：在采用列循環(huán)劃分的情況下，例3.1串行程序段可轉(zhuǎn)化為如下并行程序段：fork=1toppar-dofori=1tondoforj1=1tosdoProcess(a[i,(j1-1)p+k])endforendforendfor國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

數(shù)據(jù)劃分與處理器指派

2、塊狀劃分方法所謂塊狀劃分又叫棋盤劃分（CheckerBoardPartitioning），就是將矩陣劃分成若干個子矩陣，每個子矩陣指派給一個處理器，此時任一處理器均不包含整行或整列。可分為圖3.11(a)所示的塊棋盤劃分（Block-checkerBoardPartitioning）和圖3.11(b)所示的循環(huán)棋盤劃分（Cyclic-checkerBoardPartitioning）。國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

四個處理器上4×4矩陣棋盤劃分棋盤劃分比帶狀劃分可開發(fā)更高的并行度。例如，對于一個的方陣，棋盤劃分最多可使用n2個處理器；而帶狀劃分可用的處理器數(shù)不能多于n個。

數(shù)據(jù)劃分與處理器指派國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法

數(shù)據(jù)劃分與處理器指派3.數(shù)據(jù)劃分準(zhǔn)則:

⑴并行粒度準(zhǔn)則：

若多處理機(jī)系統(tǒng)有p臺處理器，所有工作的處理器均經(jīng)由一單獨(dú)的全局信號燈同步，要是某一項(xiàng)給定的任務(wù)在其完成后要求同步時的最壞時間復(fù)雜度為t(m)，那么最大可能加速比為。

⑵數(shù)據(jù)相關(guān)性準(zhǔn)則：

劃分后的數(shù)據(jù)要指派給各處理器去執(zhí)行一些操作，所以劃分應(yīng)該減少處理器間的通信，把那些彼此相關(guān)的數(shù)據(jù)盡可能分配到同一個處理器上，以使各處理器能獨(dú)立地工作或只進(jìn)行少量的通信。

國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法數(shù)據(jù)劃分與處理器指派

4.基于數(shù)據(jù)內(nèi)部相關(guān)分析的劃分?jǐn)?shù)據(jù)內(nèi)部相關(guān)分析是指同一數(shù)據(jù)劃分的相關(guān)分析。例3.2設(shè)A為一個n階方陣，有如下串行程序段：

fori=1tondo forj=1tondo a[i,j]=a[i-1,j] endfor endfor

分析矩陣A的元素下標(biāo)i和j，則i和j的相關(guān)方向向量為，各列之間數(shù)據(jù)無任何相關(guān)關(guān)系。因此對矩陣A可按列劃分。串行程序段可轉(zhuǎn)化為如下并行程序段：

fork=1toPPar-do

forj1=1tomdo

fori=1tondo a[i,(k-1)m+j1]=a[i-1,(k-1)m+j1]

endfor endfor endfor

國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法數(shù)據(jù)劃分與處理器指派

4.基于數(shù)據(jù)內(nèi)部相關(guān)分析的劃分

例3.3設(shè)A為矩陣，有如下串行程序段：

fori=1tondo forj=1tondo a[3i,2j]=a[3i-2,2j-1] endfor endfor

其相關(guān)方向向量為，可知行和列間同時存在數(shù)據(jù)相關(guān)。在此我們可以試用行劃分、列劃分和方塊劃分.在行劃分的情況下令,例3.3的串行程序段可以轉(zhuǎn)化為如下的并行程序段：

fork=1toPPar-do

fori1=1tomdo

forj=1tondo a[3(k-1)m+3i1,2j]=a[3(k-1)m+3i1-2,2j-1]

endfor endfor endfor國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法數(shù)據(jù)劃分與處理器指派

5.基于數(shù)據(jù)外部相關(guān)分析的劃分

所謂數(shù)據(jù)外部相關(guān)分析是指對不同數(shù)據(jù)劃分的相關(guān)分析。

例3.4設(shè)A和B均為n階矩陣，有如形式的下串行程序段：

fori=1tondo forj=1tondo endfor endfor

其中、、、都是i，j的線性組合：

國家高性能計(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有國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法數(shù)據(jù)劃分與處理器指派

5.基于數(shù)據(jù)外部相關(guān)分析的劃分經(jīng)變換可寫為：劃分結(jié)果要使得相關(guān)數(shù)據(jù)被劃分至同一處理器中，各處理器間無通信開銷，則必須滿足以下條件：對于固定值c，由此式可求得、及、、。國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法數(shù)據(jù)劃分與處理器指派

5.基于數(shù)據(jù)外部相關(guān)分析的劃分例3.5.設(shè)A為n階矩陣，B為矩陣，對如下二重循環(huán)計(jì)算：fori=2tondoforj=2tondo

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í)行的部分國家高性能計(jì)算中心（合肥）循環(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)圖國家高性能計(jì)算中心（合肥）循環(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元素被分配到相同的處理器中，計(jì)算時處理器之間不發(fā)生通信。由于斜線劃分不利于并行計(jì)算，故采用第二種劃分方法，進(jìn)而可得出相應(yīng)的并行程序：

fori=2tonpar-doforj=2tondo

endfor endfor

迭代空間數(shù)據(jù)相關(guān)圖

國家高性能計(jì)算中心（合肥）循環(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)，從而減少通信開銷，提高計(jì)算的并行性。對如下循環(huán)：fori=1tondoforj=1tondoa[i,j]=a[i-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ā)生矛盾。現(xiàn)交換I,j循環(huán)的先后次序。通過重構(gòu)得到如下并行程序：forj=1tonpar-dofori=1tondoa[i,j]=a[i-1,j] endfor endfor國家高性能計(jì)算中心（合肥）循環(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)：fori=1tondoforj=i+1tondoProcess(a[i,j])

endfor endfor由于內(nèi)層循環(huán)j的初值是外層循環(huán)i的函數(shù)，在循環(huán)交換后，這樣的初值和終值也相應(yīng)地變化為：forj=2tondofori=1toj-1doProcess(a[i,j])

endforendfor國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

2.拉伸法例3.6.在下列程序中：fori=1tondoforj=1tondoa[i,j]=a[i-1,j]+a[i,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，得到如下程序：

fori=1tondoforj=i+1toi+ndoa[i,j-i]=a[i-1,j-i]+a[i,j-i-1]

endfor endfor拉伸前的數(shù)據(jù)相關(guān)圖國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

2.拉伸法由圖可見，對相同j值，沿i方向的計(jì)算無相關(guān)關(guān)系，因此交換i，j循環(huán)先后次序，i循環(huán)可并行執(zhí)行，得到如下并行程序：forj=2to2ndofori=max(1,j-n)tomin(n,j+1)par-doa[i,j-i]=a[i-1,j-i]+a[i,j-i-1]

endfor endfor由上述程序可見，由于各行之間的計(jì)算可以并行，因此對A矩陣進(jìn)行行塊劃分拉伸后的數(shù)據(jù)相關(guān)圖國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

2.拉伸法例3.7.設(shè)A為n階矩陣，有串行程序如下：fori=1tondoforj=1tondoa[i,j]=(a[i,j+1]+a[i,j-1]+a[i+1,j]+a[i-1,j])/4

endfor endforn=5時的數(shù)據(jù)相關(guān)圖國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

2.拉伸法

若按串行程序所定義的執(zhí)行順序，對A中的元素的可并行執(zhí)行順序如前面圖所示。圖中(i,j)位置上的數(shù)字T表示元素a[i,j]可并行計(jì)算的時間。例如a[1,1]可在T=1時計(jì)算，a[2,1]及a[1,2]可在T=2時并行計(jì)算等。即：沿對角線方向上的計(jì)算可以并行。為了挖掘此并行性，我們采用拉伸法對串行程序進(jìn)行改造。對循環(huán)j利用循環(huán)i進(jìn)行拉伸，拉伸系數(shù)為1，得到如下程序：fori=1tondoforj=1+iton+idoa[i,j-i]=(a[i,j+1-i]+a[i,j-1-i]+a[i+1,j-i]+a[i-1,j-i])/4

endfor endfor

通過交換內(nèi)外循環(huán)的先后次序，得到如下并行程序：forj=2to2ndofori=max(1,j-n)tomin(n,j-1)par-doa[i,j-i]=(a[i,j+1-i]+a[i,j-1-i]+a[i+1,j-i]+a[i-1,j-i])/4

endfor endfor

調(diào)整后的內(nèi)層循環(huán)將被并行執(zhí)行，即在同一列的各行之間并行。因此對A進(jìn)行行塊劃分。國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

3.分裂法

分裂法是一種通過將循環(huán)迭代空間細(xì)分成相同形狀和大小的數(shù)據(jù)塊以達(dá)到局部化相關(guān)關(guān)系的變換方法。變換之后，一個子數(shù)據(jù)塊內(nèi)部的全部迭代被同一個處理器執(zhí)行，只有在子數(shù)據(jù)塊之間計(jì)算才需要通信。分裂法的變換分兩步進(jìn)行：第一步，將原算法中的每重循環(huán)按塊連續(xù)劃分，細(xì)化為雙重嵌套循環(huán)，外層對子塊進(jìn)行循環(huán)，內(nèi)層對塊內(nèi)數(shù)據(jù)進(jìn)行循環(huán)；第二步，將所有對子塊的循環(huán)交換至經(jīng)變換后循環(huán)體的最外層以并行執(zhí)行。國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

3.分裂法例3.8.設(shè)A，B，C為n階矩陣，有串行程序如下：fori=1tondoforj=1tondoA[i,j]=A[i,j]+B[i,j]C[i,j]=2*A[i-1,j]

endforendfor經(jīng)分裂法變換后，得到如下并行程序：forit=1tonstepsspar-doforjt=1tonstepsspar-dofori=ittomin(n,it+ss-1)doforj=jttomin(n,jt+ss-1)doA[i,j]=A[i,j]+B[i,j]C[i,j]=2*A[i-1,j]

endfor endfor endfor endfor

國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

3.分裂法

并行計(jì)算中，將同一子塊內(nèi)的全部計(jì)算加載到一個處理器上執(zhí)行。不同處理器執(zhí)行不同子塊。經(jīng)分裂變換，矩陣A、B、C的數(shù)據(jù)都進(jìn)行了方塊劃分，其中對C數(shù)據(jù)的行向分割比A、B低一格。通過此例，可以發(fā)現(xiàn)分裂變換既提高了計(jì)算的并行性，又控制了通信開銷。數(shù)據(jù)A,B,C的劃分圖國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

4.輪轉(zhuǎn)法對于初值為0，步長為1的循環(huán)，我們稱之為正規(guī)循環(huán)。對正規(guī)循環(huán)可以通過實(shí)施輪轉(zhuǎn)法來挖掘其中的并行性，對于非正規(guī)的循環(huán)，我們總可以通過簡單的下標(biāo)變換使之變?yōu)檎?guī)循環(huán)。對于如下正規(guī)循環(huán)：fori=0ton-1doforj=0tom-1doProcess(a[i,j])

endfor endfor輪轉(zhuǎn)法的作法與拉伸法很類似，對循環(huán)j和循環(huán)i進(jìn)行拉伸，拉伸系數(shù)為1，可得如下并行程序：fori=0ton-1doforj=0tom-1par-doProcess(a[i,(j+i)modn])

endfor endfor國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

5.并列法

并列法將循環(huán)體中無相關(guān)關(guān)系可以互相并行的部分折分成幾個并列的循環(huán)，使這幾個循環(huán)之間可以互相并行執(zhí)行，以如下循環(huán)為例：fori=1tondoforj=1tondoS1;S2;…;Sm

endfor endfor

這里S1,S2,…,Sm為相互之間無相關(guān)關(guān)系的程序段，而且在任意Sk與Sl對循環(huán)變量i，j的任不同取值的計(jì)算之間也無相關(guān)關(guān)系。則上述串行程序可變換為如下并行程序：fork=1tompar-dofori=1tondoforj=1tondoSk

endfor

endfor endfor

如何從循環(huán)體中劃分出幾個獨(dú)立的模塊，這要使用功能分解的方法。

國家高性能計(jì)算中心（合肥）循環(huán)程序并行化的一般方法循環(huán)重構(gòu)

5.并列法

例3.10

我們以對稱方陣CHOLESKY分解為例，說明利用循環(huán)重構(gòu)的過程。CHOLESKY分解串行算法如下：

輸入：對稱矩陣A輸出：下三角矩陣L，使得A=LLTPROCEDURECHOLESKY(A)Beginfork=1tondoa[k,k]=sqrt(a[k,k])

fori=k+1tondoa[i,k]=a[i,k]/a[k,k]

forj=k+1toidoa[i,j]=a[i,j]-a[i,k]*a[j,k]endforendforendforfori=1tondo

forj=1tondo

if(i≥j)thenl[i,j]=a[i,j]endif

endforendforOUTP