并行算法的設(shè)計(jì)技術(shù)

第四章

并行算法的設(shè)計(jì)技術(shù)

并行算法的設(shè)計(jì)步驟劃分(Partitioning)分解成小的任務(wù)，開拓并發(fā)性通訊(Communication)確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測(cè)劃分的合理性；組合(Agglomeration)依據(jù)任務(wù)的局部性，組合成更大的任務(wù)映射(Mapping)將每個(gè)任務(wù)分配到處理器上，提高算法的性能

并行算法的設(shè)計(jì)技術(shù)平衡樹方法倍增技術(shù)分治策略流水線技術(shù)平衡樹技術(shù)平衡樹設(shè)計(jì)思想以樹的葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層進(jìn)行并行處理。

A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1應(yīng)用----N個(gè)數(shù)求和輸入：數(shù)組A(1:N)，N=2K輸出：數(shù)組值的總和存儲(chǔ)于A(1)中beginp=n/2whilep>0dofori=1topdoinparallelA(i)=A(2i-1)+A(2i)endparallelp=p/2endwhileend應(yīng)用-------計(jì)算前綴和問題定義n個(gè)元素{x1,x2,…,xn}，前綴和是n個(gè)部分和：Si=x1*x2*…*xi,1≤i≤n這里*可以是＋或×串行算法：

Si=Si－1*xi

計(jì)算時(shí)間為O(n)

并行算法：SIMD-TC上非遞歸算法

令A(yù)[i]=xi,i=1~n,B[h,j]和C[h,j]為輔助數(shù)組(h=0~logn,j=1~n/2h)

數(shù)組B記錄由葉到根正向遍歷樹中各結(jié)點(diǎn)的信息(求和)數(shù)組C記錄由根到葉反向遍歷樹中各結(jié)點(diǎn)的信息(播送前綴和)82023/2/6

計(jì)算前綴和例：n=8,p=8,C01~C08為前綴和SIMD-TC模型上非遞歸求前綴和算法輸入：n=2k的數(shù)組A，k為非負(fù)整數(shù)輸出：數(shù)組C，其中C(0,j)是第j個(gè)前綴和begin(1)forj=1tonpar-doB(0,j)<---A(j)endfor(2)forh=1tologndoforj=1ton/2hpar-doB(h,j)<---B(h-1,2j-1)*B(h-1,2j)endforendfor

SIMD-TC模型上非遞歸求前綴和算法(3)forh=lognto0doforj=1ton/2hpar-do(i)ifj=eventhenC(i,j)<---C(h+1,j/2)endif(ii)ifj=1thenC(h,1)<--B(h,1)endif(III)IFJ=odd>1thenC(H,j)<---C(h+1,(j-1)/2)*B(h,j)endforendforendforend122023/2/6

倍增設(shè)計(jì)技術(shù)設(shè)計(jì)思想通過多次處理；每一次處理都會(huì)改變處理的范圍。適用于處理以鏈表或有向有根樹之類表示的數(shù)據(jù)結(jié)構(gòu)。每當(dāng)遞歸調(diào)用時(shí)，要處理的數(shù)據(jù)之間的距離將逐步加倍，經(jīng)過k步后就可完成距離為2k的所有數(shù)據(jù)的計(jì)算示例表序問題:就是確定出表列中每個(gè)元素K在表列中的位序號(hào)。132023/2/6

表序問題問題描述

n個(gè)元素的列表L，求出每個(gè)元素在L中的位序號(hào)(rank(k))，rank(k)可視為元素k至表尾的距離；示例：n=7

(1)p[a]=b,p[b]=c,p[c]=d,p[d]=e,p[e]=f,p[f]=g,p[g]=g

r[a]=r[b]=r[c]=r[d]=r[e]=r[f]=1,r[g]=0(2)p[a]=c,p[b]=d,p[c]=e,p[d]=f,p[e]=p[f]=p[g]=gr[a]=r[b]=r[c]=r[d]=r[e]=2,r[f]=1,r[g]=0(3)p[a]=e,p[b]=f,p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=4,r[b]=4,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0(4)p[a]=p[b]=p[c]=p[d]=p[e]=p[f]=p[g]=gr[a]=6,r[b]=5,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=0表序問題

SIMD-EREW模型上求元素表序算法輸入：N個(gè)元素的表列L輸出：rank(k)Begin:(1)forallk∈lpar_do(1.1)p(k)←next(k)(1.2)ifp(k)≠kthendistance(k)←1

elsedistance(k)←0

endif

endfor(2)repeat「logn」times

(2.1)forallk∈lpar_doIfp(k)≠p(p(k))then(ⅰ)distance(k)←distance(k)+distance(p(k))(ⅱ)p(k)←p(p(k))endif

endfor(2.2)forallk∈lpar_dorank(k)←distance(k)endforendrepeatend

劃分和分治策略劃分(partitioning)：將問題分為若干個(gè)獨(dú)立的部分。分治法(divideandconquermethod)：將一個(gè)大問題逐步分割成若干個(gè)原問題的子問題，用簡單且相同的方法對(duì)這些子問題進(jìn)行求解，然后將這些子問題的解組合成原問題的解。在分治法中分解問題和合并結(jié)果常使用遞歸技術(shù)來實(shí)現(xiàn)。遞歸分治法能使各個(gè)子問題并行化執(zhí)行，即各個(gè)進(jìn)程用來執(zhí)行被分解的部分。通常數(shù)據(jù)的劃分也同時(shí)局部化。劃分策略PartitioningStrategies數(shù)據(jù)劃分(datapartitioningordomaindecomposition)----數(shù)據(jù)域并行(SIMD或SPMD)數(shù)據(jù)劃分是并行計(jì)算中的主要策略功能劃分(functionaldecomposition)----控制并行(MIMD或MPMD)例：利用數(shù)據(jù)劃分技術(shù)對(duì)數(shù)列求和。假設(shè)有p個(gè)處理機(jī)，數(shù)列元素個(gè)數(shù)為n。A0…An/p-1An/p…A2n/p-1A2n/p…………A(p-1)n/p…An-1++++………局部和總和2路分治法intadd(ints[]){if(number(s)<=2)return(n1+n2);else{Divide(s,s1,s2);Part_sum1=add(s1);Part_sum2=add(s2);Return(Part_sum1+Part_sum2);}}M路分治法Intadd(int*s){if(number(s)=<4)return(n1+n2+n3+n4);else{divide(s,s1,s2,s3,s4);part_sum1=add(s1);part_sum2=add(s2);part_sum3=add(s3);part_sum4=add(s4);return(part_sum1+part_sum2+part_sum3+part_sum1)}}數(shù)值積分將積分區(qū)域分割為一系列矩形，利用這些矩形的面積近似求出積分區(qū)域的值。矩形面積=d*f(p+d/2)xf(x)apdqb將積分區(qū)域分割為一系列梯形，利用這些梯形的面積近似積分區(qū)域的值。梯形面積=d*(f(p)+f(q))/2)xf(x)apdqb當(dāng)d越小，算法求出的近似值越精確。顯然我們能很容易地將數(shù)值積分問題分解為多個(gè)相互獨(dú)立的部分，每個(gè)部分由一個(gè)單獨(dú)的進(jìn)程完成計(jì)算。一般的靜態(tài)分配的并行算法是將積分區(qū)域按處理機(jī)的個(gè)數(shù)p分為p塊，然后每個(gè)處理機(jī)（進(jìn)程）計(jì)算一塊區(qū)域的面積，最后將其歸并，得到整個(gè)區(qū)域的積分值。采用矩形方法，即計(jì)算每個(gè)小區(qū)間的中間點(diǎn)的函數(shù)值的矩形面積的并行算法：面積=

df(a+d/2)+df(a+d+d/2)+df(a+2d+d/2)+…+df(a+(n-1)d+d/2)

=d{f(a+d/2)+f(a+d+d/2)+f(a+2d+d/2)+…+f(a+(n-1)d+d/2)}1401+x21+()

4

i+0.52

n0i<n1n=dx采用第二種方法，即計(jì)算每個(gè)小區(qū)間的梯形面積的計(jì)算公式：d(f(a)+f(a+d))2d(f(a+d)+f(a+2d))2d

(f(a+(n-1)d)+f(b))2面積=++…+=d+f(a+d)+f(a+2d)+…+f(a+(n-1)d)+f(b)2f(a)2

算法只需做少量修改：

part_sum=0.5*(f(start)+f(end)); for(x=start+d;x<end;x=x+d) {//calcspartialsums part_sum+=f(x); } part_sum=d*part_sum;算法描述在SPMD模式中：If(I==master){printf(“Enternumberofintervals”);scanf(“%d”,&n);}Bcast(&n,pgroup);region=(b-a)/p;start=a+region*I;end=start+region;

算法描述d=(b-a)/n;area=0.0;

for(x=start;x<end;x=x+d)area=area+0.5*(f(x)+f(x+d))*d;reduce_add(&integral,&area,pgroup);-----------------------------------------------------------------------

for(x=start;x<end;x=x+d)area=area+f(x)+f(x+d);area=0.5*area*d;a4a3a2…

a4

a3a2a1

a1…

a4

a3a2…

a4

a3流水線計(jì)算是通過將任務(wù)按功能劃分成若干個(gè)級(jí)(pipelinestage)

或子任務(wù)，每個(gè)級(jí)可以同時(shí)執(zhí)行，且一級(jí)的輸出是下一級(jí)的輸入。每個(gè)子任務(wù)由不同的處理部件執(zhí)行。P0P1P2P3P4…a4…

流水線技術(shù)例1：將數(shù)組a的所有元素累加到sum中順序算法for(i=0;i<n;i++) sum=sum+a[i]并行算法aSinSoutaSinSouta[1]aSinSouta[2]aSinSouta[3]a[0]sum每個(gè)處理機(jī)（流水線中的中間級(jí)）需要執(zhí)行相同的操作：recv(sum,Pi-1);sum=sum+a;send(sum,Pi+1);該過程的程序：假設(shè)第i個(gè)處理機(jī)將數(shù)組的第i個(gè)元素存入局部變量number。

if(processnum>0){recv(sum,Pi-1);sum=sum+number;}if(processnum<n-1)send(sum,Pi+1);流水線應(yīng)用的計(jì)算平臺(tái)流水線操作的一個(gè)關(guān)鍵要求是流水線的相鄰進(jìn)程之間要有發(fā)送消息的能力。這種操作方式?jīng)Q定了它最適合于線性或者環(huán)形網(wǎng)絡(luò)結(jié)構(gòu)，即相鄰的處理機(jī)之間有直接通信鏈路。如下圖例。主機(jī)Processors線性結(jié)構(gòu)的多處理機(jī)系統(tǒng)線性結(jié)構(gòu)和環(huán)形結(jié)構(gòu)可以完美地嵌入到網(wǎng)格和超立方體結(jié)構(gòu)之上。這就使得網(wǎng)格和超立方體成為合適的平臺(tái)。流水線應(yīng)用-----數(shù)列排序任務(wù)：將一個(gè)數(shù)列從大