并行算法设计与分析

并行算法设计与分析第2章并行算法的设计技术本章主要内容2.1平衡树方法2.2倍增技术2.3分治策略2.4划分原理2.5流水线技术2.6加速级联策略2.7破对称技术2.1平衡树方法设计思想将树叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层并行处理。并行处理过程相当于由底向上（自顶向下）动态生成一个平衡二叉树。2.1.1并行求n个元素的最大值

算法2.1SIMD-SM上求最大值算法Begin//m=lognfork=m-1to0do//k为树的层号forj=2kto2k+1-1par-do//k层上2k结点（处理器）并行求最大值A[j]=max{A[2j],A[2j+1]}endforendforEnd复杂度分析：t(n)=m×O(1)=O(m)=O(logn)，p(n)=n/2c(n)=O(nlogn)，代价非最优（原因：活跃处理器数目逐层减半）

2.1.2前缀和的并行计算前缀和问题定义：n个元素S={x1,x2,…,xn}，S的第i个前缀和Si=x1*x2*…*xi,1≤i≤n，这里*可以是＋或×。前缀和串行（递归）算法：Si=Si－1*xi，计算时间为O(n)。前缀和并行算法的设计思想令A[i]=xi,i=1~n,引入辅助数组B[h,j]和C[h,j]，h=0~logn,j=1~n/2h。数组B记录由叶到根逐层正向并行遍历树中各结点的信息(并行求“前缀子和”)。数组C记录由根到叶逐层反向并行遍历树中各结点的信息(并行播送“前缀子和”)算法2.2SIMD-SM上非递归并行求前缀和高层描述算法Begin//高层描述并行算法——不考虑可用处理器的数目(1)forj=1tonpar-do//初始化B[0,j]=A[j]endfor

//正向遍历求前缀子和(2)forh=1tologndo//h为树层号forj=1ton/2hpar-do//n/2h为h层结点数B[h,j]=B[h-1,2j-1]*B[h-1,2j]endforendfor

//反向遍历播送前缀子和(3)forh=lognto0do//h为树层号forj=1ton/2hpar-do//n/2h为h层结点数(i)ifj=eventhen//该结点为其父结点右儿子C[h,j]=C[h+1,j/2]endif(ii)ifj=1then//该结点为最左结点C[h,1]=B[h,1]endif(iii)ifj=odd>1then//该结点为其父结点左儿子C[h,j]=C[h+1,(j-1)/2]*B[h,j]endifendforendforend

复杂度分析:(1)时间：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)代价非最优（原因：活跃处理器数目逐层减半）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倍增技术(指针跳跃技术，pointerjumping)设计思想对于规模为n的问题，每当递归（迭代）调用时，将所要处理数据之间的距离（下标，规模）逐步加倍，经过k=logn步后，即可完成距离(规模)为2k=n的所有数据的计算。倍增技术特别适合于处理链表或有向树之类的数据结构。2.2.1表序问题

设L为n个元素的线性表，求出L中每个元素k在L中的次第号rank(k)（位序，秩）,rank(k)=L中小于k的元素数目。算法2.4SIMD-EREW上求元素表序并行算法

引入指针数组next(k)，定义next(k)为k的下一个元素，若为最后一个元素，则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个元素的位序，i=0~lgn-1End算法复杂度：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求森林的根问题描述一组有向树F中,如果<i,j>是F中的一条弧，则p[i]=j(即j是i的双亲)；若i为根，则p[i]=i。求每个结点j(j=1~n)的树根s[j].求森林根并行算法：算法2.5，p69-70,时间t(n)=O(logn)初始时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分治策略设计思想将原问题划分成若干个类型相同的子问题分而治之，若子问题仍然较大，则可以反复递归应用分治策略处理这些子问题，直至子问题易求解为止。2.3.1（并行）分治策略求解问题步骤将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题；并行地归并子问题的解成为原问题的解。分治策略的重点：在于如何归并子问题的解如果归并的开销太大，那么可以使用流水线方式的级联分治策略进行归并。2.3.2SIMD-SM上FFT并行算法串行FFT递归算法DFT离散富里叶变换的定义给定向量，DFT将A变换为，即

写成矩阵形式为注：串行直接计算DFT需要O(nlgn)时间FFT递归并行算法思想：将20个原问题的DFT划分为21个规模为n/2的子问题的DFT；将21个规模为n/2的子问题DFT划分为22规模为n/22的子问题的DFT；依次类推，直到将2lgn-1个规模为n/2lgn-1=2的子问题为止。算法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.,算法复杂度：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),代价最优,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划分原理设计思想1、将原问题划分成p个独立的规模几乎相等的子问题；2、P个处理器并行地求解各子问题。划分方法重点：如何划分问题以使得子问题解很容易被组合成原问题的解。常见划分方法均匀划分：将n个元素划分为p组，Pi处理第i组A[(i-1)n/p+1..i*n/p],i=1~p方根划分：将n个元素划分为n1/2组，Pi处理第i组A[(i-1)n1/2+1..i*n1/2],i=1~n1/2

对数划分：将n个元素划分为lgn组，Pi处理第i组A[(i-1)n’lgn+1..i*n’lgn],

i=1~lgn功能划分：根据功能将原问题划分成若干不同功能的子问题，这些子问题被并行处理均匀划分方法应用示例算法2.8MIMD-SM模型上的PSRS（规整抽样）排序算法

Begin(1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个Pi处理A[(i-1)n/p+1..in/p],i=1~p(2)并行局部排序：Pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序,i=1~p(3)并行选取样本：Pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素,

i=1~p(4)样本排序：用一个处理器对p2个样本元素进行串行排序(5)选择主元：用一个处理器从排好序的样本序列中选取p-1个主元，并播送给其他p-1个处理器(6)并行主元划分：Pi按主元将有序子序列A[(i-1)n/p+1..in/p]划分成p段,i=1~p(7)并行全局交换：Pi将其有序子序列中的有序段按段号j(j=1~p)交换到相应的处理器Pj(j=1~p)中，i=1~p(8)并行归并排序：Pi对接收到的各段元素进行归并排序,i=1~pEnd.PSRS排序过程例:n=27，p=32.5流水线技术设计思想将计算任务划分为一系列子任务T1,T2,…,Tm，每个子任务的输出作为下一个子任务的输入。一旦子任务T1完成，后继的其他子任务均立即以同样的速率进行计算、产生出结果。Remark流水线技术广泛应用在并行处理。脉动算法(Systolicalgorithm)采用流水线技术。算法2.9SIMD-LC上流水线归并排序算法思想：P1从输入序列中读入一个数据并将它输出，其他处理器以流水线并行方式读入数据、比较数据、归并输出，其中Pi接收Pi-1输出的两个长度为2i-2的子序列，并将归并成长度2i-1的序列输出。Begin//PP.76-77dostep(1),(2)and(3)inparallel(1)P1执行如下操作：//P1以流水线方式读入原始数据(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以流水线方式并行归并数据（有序子序列）(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以流水线方式输出有序序列结果{Pr+1compare1stelementinQ2rwith1stelementinQ2r+1;Pr+1printthelargerelementtoQ2r+1;}End.

2.6加速级联策略设计思想：将一个代价最优但相对不快的行算法与另一个非常快但代价不是最优的并行算法级联起来，以形成一个称之为加速级联的并行算法。运用代价最优但相对不快的并行算法求解，直至问题规模减小到某个阈值为止。采用非常快但代价不是最优的并行算