并行算法設(shè)計(jì)與分析

并行算法設(shè)計(jì)與分析第2章并行算法的設(shè)計(jì)技術(shù)本章主要內(nèi)容2.1平衡樹(shù)方法2.2倍增技術(shù)2.3分治策略2.4劃分原理2.5流水線技術(shù)2.6加速級(jí)聯(lián)策略2.7破對(duì)稱技術(shù)2.1平衡樹(shù)方法設(shè)計(jì)思想將樹(shù)葉結(jié)點(diǎn)為輸入，中間結(jié)點(diǎn)為處理結(jié)點(diǎn)，由葉向根或由根向葉逐層并行處理。并行處理過(guò)程相當(dāng)于由底向上（自頂向下）動(dòng)態(tài)生成一個(gè)平衡二叉樹(shù)。2.1.1并行求n個(gè)元素的最大值

算法2.1SIMD-SM上求最大值算法Begin//m=lognfork=m-1to0do//k為樹(shù)的層號(hào)forj=2kto2k+1-1par-do//k層上2k結(jié)點(diǎn)（處理器）并行求最大值A(chǔ)[j]=max{A[2j],A[2j+1]}endforendforEnd復(fù)雜度分析：t(n)=m×O(1)=O(m)=O(logn)，p(n)=n/2c(n)=O(nlogn)，代價(jià)非最優(yōu)（原因：活躍處理器數(shù)目逐層減半）

2.1.2前綴和的并行計(jì)算前綴和問(wèn)題定義：n個(gè)元素S={x1,x2,…,xn}，S的第i個(gè)前綴和Si=x1*x2*…*xi,1≤i≤n，這里*可以是＋或×。前綴和串行（遞歸）算法：Si=Si－1*xi，計(jì)算時(shí)間為O(n)。前綴和并行算法的設(shè)計(jì)思想令A(yù)[i]=xi,i=1~n,引入輔助數(shù)組B[h,j]和C[h,j]，h=0~logn,j=1~n/2h。數(shù)組B記錄由葉到根逐層正向并行遍歷樹(shù)中各結(jié)點(diǎn)的信息(并行求“前綴子和”)。數(shù)組C記錄由根到葉逐層反向并行遍歷樹(shù)中各結(jié)點(diǎn)的信息(并行播送“前綴子和”)算法2.2SIMD-SM上非遞歸并行求前綴和高層描述算法Begin//高層描述并行算法——不考慮可用處理器的數(shù)目(1)forj=1tonpar-do//初始化B[0,j]=A[j]endfor

//正向遍歷求前綴子和(2)forh=1tologndo//h為樹(shù)層號(hào)forj=1ton/2hpar-do//n/2h為h層結(jié)點(diǎn)數(shù)B[h,j]=B[h-1,2j-1]*B[h-1,2j]endforendfor

//反向遍歷播送前綴子和(3)forh=lognto0do//h為樹(shù)層號(hào)forj=1ton/2hpar-do//n/2h為h層結(jié)點(diǎn)數(shù)(i)ifj=eventhen//該結(jié)點(diǎn)為其父結(jié)點(diǎn)右兒子C[h,j]=C[h+1,j/2]endif(ii)ifj=1then//該結(jié)點(diǎn)為最左結(jié)點(diǎn)C[h,1]=B[h,1]endif(iii)ifj=odd>1then//該結(jié)點(diǎn)為其父結(jié)點(diǎn)左兒子C[h,j]=C[h+1,(j-1)/2]*B[h,j]endifendforendforend

復(fù)雜度分析:(1)時(shí)間：O(1)，(2)：lognO(1)=O(logn)，(3)：lognO(1)=O(logn)，

t(n)=O(1)+O(logn)+O(logn)=O(logn)，p(n)=n/2,c(n)=n/2O(logn)=O(nlogn)代價(jià)非最優(yōu)（原因：活躍處理器數(shù)目逐層減半）W(n)=n+(n/21+n/22+…+n/2logn)+(n/2logn++…n/21+n/20)=n+(n-1)+(2n-1)=3n-2=O(n)2.2倍增技術(shù)(指針跳躍技術(shù)，pointerjumping)設(shè)計(jì)思想對(duì)于規(guī)模為n的問(wèn)題，每當(dāng)遞歸（迭代）調(diào)用時(shí)，將所要處理數(shù)據(jù)之間的距離（下標(biāo)，規(guī)模）逐步加倍，經(jīng)過(guò)k=logn步后，即可完成距離(規(guī)模)為2k=n的所有數(shù)據(jù)的計(jì)算。倍增技術(shù)特別適合于處理鏈表或有向樹(shù)之類的數(shù)據(jù)結(jié)構(gòu)。2.2.1表序問(wèn)題

設(shè)L為n個(gè)元素的線性表，求出L中每個(gè)元素k在L中的次第號(hào)rank(k)（位序，秩）,rank(k)=L中小于k的元素?cái)?shù)目。算法2.4SIMD-EREW上求元素表序并行算法

引入指針數(shù)組next(k)，定義next(k)為k的下一個(gè)元素，若為最后一個(gè)元素，則next(k)=kBeginforallkinLdoinparallel//O(1)(1.1)P(k)=next(k);//P(k)表示k的后繼(1.2)ifP(k)!=kthendistance(k)=1elsedistance(k)=0//distance(k)為k的距離(2)repeatlogn次//O(logn)(2.1)forallkinLdoinparallel//O(1)ifP(k)!=P(P(k))then//如果k的后繼不等于k的后繼之后繼(i)distance(k)=distance(k)+distance(P(k))//距離倍增(ii)P(k)=P(P(k))//指針跳躍(2.2)forallkinLdoonparallel//O(1)rank(k)=distance(k)//k的位序倍增，每次確定2i個(gè)元素的位序，i=0~lgn-1End算法復(fù)雜度：t(n)=O(1)+logn(O(1)+O(1))=O(logn),p(n)=n,c(n)=O(nlogn)并行求表中元素位序示例：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]=g

r[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]=g

r[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]=g

r[a]=6,r[b]=5,r[c]=4,r[d]=3,r[e]=2,r[f]=1,r[g]=02.2.2求森林的根問(wèn)題描述一組有向樹(shù)F中,如果<i,j>是F中的一條弧，則p[i]=j(即j是i的雙親)；若i為根，則p[i]=i。求每個(gè)結(jié)點(diǎn)j(j=1~n)的樹(shù)根s[j].求森林根并行算法：算法2.5，p69-70,時(shí)間t(n)=O(logn)初始時(shí)P[1]=p[2]=5p[3]=p[4]=p[5]=6P[6]=p[7]=8p[8]=8P[9]=10p[10]=11p[11]=12p[12]=13p[13]=13s[i]=p[i]

示例第一次迭代后第二次迭代后2.3分治策略設(shè)計(jì)思想將原問(wèn)題劃分成若干個(gè)類型相同的子問(wèn)題分而治之，若子問(wèn)題仍然較大，則可以反復(fù)遞歸應(yīng)用分治策略處理這些子問(wèn)題，直至子問(wèn)題易求解為止。2.3.1（并行）分治策略求解問(wèn)題步驟將輸入劃分成若干個(gè)規(guī)模相等的子問(wèn)題；同時(shí)(并行地)遞歸求解這些子問(wèn)題；并行地歸并子問(wèn)題的解成為原問(wèn)題的解。分治策略的重點(diǎn)：在于如何歸并子問(wèn)題的解如果歸并的開(kāi)銷太大，那么可以使用流水線方式的級(jí)聯(lián)分治策略進(jìn)行歸并。2.3.2SIMD-SM上FFT并行算法串行FFT遞歸算法DFT離散富里葉變換的定義給定向量，DFT將A變換為，即

寫成矩陣形式為注：串行直接計(jì)算DFT需要O(nlgn)時(shí)間FFT遞歸并行算法思想：將20個(gè)原問(wèn)題的DFT劃分為21個(gè)規(guī)模為n/2的子問(wèn)題的DFT；將21個(gè)規(guī)模為n/2的子問(wèn)題DFT劃分為22規(guī)模為n/22的子問(wèn)題的DFT；依次類推，直到將2lgn-1個(gè)規(guī)模為n/2lgn-1=2的子問(wèn)題為止。算法2.7SIMD-EREW上FFT并行算法ProcedurePara-FFT(x,y)//t(n),W(n)Beginifn=2theny0=x0+x1;y1=x0-x1;//O(1),W1(n)=1forl=0ton/2-1doinparallel//O(1),W2(n)=2(n/2)=n(2.1)ul=xl

+xn/2+l;(2.2)vl=wl(xl

-xn/2+l);(3)Doinstep(3.1),(3.2)inparallel(3.1)Para-FFT((u0,u1,..un/2-1),z(1)=(z0(1),z1(1),…,zn/2-1(1)));//t(n/2),W(n/2)(3.2)Para-FFT((v0,v1,..vn/2-1),z(2)=(z0(2),z1(2),…,zn/2-1(2)));//t(n/2),W(n/2)(4)Forj=0ton-1doinparallel//O(1),W3(n)=n(4.1)ifj=eventhenyj=zj/2(1)(4.2)ifj=oddthenyj=z(j-1)/2(1)End.,算法復(fù)雜度：t(n)=O(1)+O(1)+t(n/2)+O(1)=t(n/2)+O(1)=O(lgn),p(n)=n/2.C(n)=n/2O(lgn)=O(nlgn),代價(jià)最優(yōu),Sp(n)=O(nlgn)/O(lgn)=O(n)，線性加速W(n)=W1(n)+W2(n)+2W(n/2)+W3(n)=1+n+2W(n/2)+n=2W(n/2)+O(n)=O(nlgn)2.4劃分原理設(shè)計(jì)思想1、將原問(wèn)題劃分成p個(gè)獨(dú)立的規(guī)模幾乎相等的子問(wèn)題；2、P個(gè)處理器并行地求解各子問(wèn)題。劃分方法重點(diǎn)：如何劃分問(wèn)題以使得子問(wèn)題解很容易被組合成原問(wèn)題的解。常見(jiàn)劃分方法均勻劃分：將n個(gè)元素劃分為p組，Pi處理第i組A[(i-1)n/p+1..i*n/p],i=1~p方根劃分：將n個(gè)元素劃分為n1/2組，Pi處理第i組A[(i-1)n1/2+1..i*n1/2],i=1~n1/2

對(duì)數(shù)劃分：將n個(gè)元素劃分為lgn組，Pi處理第i組A[(i-1)n’lgn+1..i*n’lgn],

i=1~lgn功能劃分：根據(jù)功能將原問(wèn)題劃分成若干不同功能的子問(wèn)題，這些子問(wèn)題被并行處理均勻劃分方法應(yīng)用示例算法2.8MIMD-SM模型上的PSRS（規(guī)整抽樣）排序算法

Begin(1)均勻劃分：將n個(gè)元素A[1..n]均勻劃分成p段，每個(gè)Pi處理A[(i-1)n/p+1..in/p],i=1~p(2)并行局部排序：Pi調(diào)用串行排序算法對(duì)A[(i-1)n/p+1..in/p]排序,i=1~p(3)并行選取樣本：Pi從其有序子序列A[(i-1)n/p+1..in/p]中選取p個(gè)樣本元素,

i=1~p(4)樣本排序：用一個(gè)處理器對(duì)p2個(gè)樣本元素進(jìn)行串行排序(5)選擇主元：用一個(gè)處理器從排好序的樣本序列中選取p-1個(gè)主元，并播送給其他p-1個(gè)處理器(6)并行主元?jiǎng)澐郑篜i按主元將有序子序列A[(i-1)n/p+1..in/p]劃分成p段,i=1~p(7)并行全局交換：Pi將其有序子序列中的有序段按段號(hào)j(j=1~p)交換到相應(yīng)的處理器Pj(j=1~p)中，i=1~p(8)并行歸并排序：Pi對(duì)接收到的各段元素進(jìn)行歸并排序,i=1~pEnd.PSRS排序過(guò)程例:n=27，p=32.5流水線技術(shù)設(shè)計(jì)思想將計(jì)算任務(wù)劃分為一系列子任務(wù)T1,T2,…,Tm，每個(gè)子任務(wù)的輸出作為下一個(gè)子任務(wù)的輸入。一旦子任務(wù)T1完成，后繼的其他子任務(wù)均立即以同樣的速率進(jìn)行計(jì)算、產(chǎn)生出結(jié)果。Remark流水線技術(shù)廣泛應(yīng)用在并行處理。脈動(dòng)算法(Systolicalgorithm)采用流水線技術(shù)。算法2.9SIMD-LC上流水線歸并排序算法思想：P1從輸入序列中讀入一個(gè)數(shù)據(jù)并將它輸出，其他處理器以流水線并行方式讀入數(shù)據(jù)、比較數(shù)據(jù)、歸并輸出，其中Pi接收Pi-1輸出的兩個(gè)長(zhǎng)度為2i-2的子序列，并將歸并成長(zhǎng)度2i-1的序列輸出。Begin//PP.76-77dostep(1),(2)and(3)inparallel(1)P1執(zhí)行如下操作：//P1以流水線方式讀入原始數(shù)據(jù)(1.1)Readx1fromQ1;(1.2)j=0;(1.3)fori=2tondoPrintxi-1toQ2+j;ReadxifromQ1;j=(j+1)mod2(1.4)PrintxntoQ3;(2)fori=2tordoinparallel//P2-Pr以流水線方式并行歸并數(shù)據(jù)（有序子序列）(2.1)j=0;(2.2)k=1;(2.3)whilek<=ndoifQ2(j-1)including2i-2elementsandQ2(j-1)+1including1elementthen{form=1to2i-1do{Pi……..};j=(j+1)mod2;k=k+2i-2;}(3)ifQ2rincluding2r-1elementsandQ2r+1including1elementthenform=1to2rdo//Pr+1以流水線方式輸出有序序列結(jié)果{Pr+1compare1stelementinQ2rwith1stelementinQ2r+1;Pr+1printthelargerelementtoQ2r+1;}End.

2.6加速級(jí)聯(lián)策略設(shè)計(jì)思想：將一個(gè)代價(jià)最優(yōu)但相對(duì)不快的行算法與另一個(gè)非?？斓鷥r(jià)不是最優(yōu)的并行算法級(jí)聯(lián)起來(lái)，以形成一個(gè)稱之為加速級(jí)聯(lián)的并行算法。運(yùn)用代價(jià)最優(yōu)但相對(duì)不快的并行算法求解，直至問(wèn)題規(guī)模減小到某個(gè)閾值為止。采用非?？斓鷥r(jià)不是最優(yōu)的并行算