并行算法设计与(2)

《并行算法设计与(2)》由会员分享，可在线阅读，更多相关《并行算法设计与(2)（22页珍藏版）》请在金锄头文库上搜索。

1、并行算法设计与分析,第2章 并行算法的设计技术,本章主要内容,2.1 平衡树方法 2.2 倍增技术 2.3 分治策略 2.4 划分原理 2.5 流水线技术 2.6 加速级联策略 2.7 破对称技术,2.1 平衡树方法,设计思想 将树叶结点作为输入，中间结点作为处理结点，由叶向根 或 由根向叶逐层并行处理。 并行处理过程相当于由底向上（自顶向下）动态生成一个逻辑平衡二叉树。 2.1.1 并行求n个元素的最大值 算法2.1 SIMD-SM上求最大值算法 Begin / m=logn逻辑二叉树的高度 for k=m-1 to 0 do / k为树的层号 for j=2k to 2k+1-1 par-

2、do / k层上2k结点（处理器）并行求最大值 Aj=maxA2j, A2j+1 end for end for End 复杂度分析：t(n)=mO(1) =O(m) =O(logn)，p(n)=n/2 c(n)=O(nlogn) ，代价非最优（原因：活跃处理器数目逐层减半）,2.1.2 前缀和的并行计算,前缀和问题定义：n个元素S=x1,x2,xn， S的第i 个前缀和Si=x1*x2*xi, 1in， 这里*可以是或。 （递归）前缀和串行算法： Si=Si-1*xi ，i=2n, S1=x1, 计算时间为 O(n) 。 前缀和并行算法的设计思想 令Ai=xi, i=1n, 引入辅助数组Bh

3、,j和Ch,j，h=0logn, j=1n/2h B0,j保存第j 个前缀和的初始值， j=1 n。 数组B记录由叶到根逐层正向并行遍历树中各结点的信息(并行求“前缀子和”)。 数组C记录由根到叶逐层反向并行遍历树中各结点的信息(并行播送“前缀子和”) 。 C0,j保存最终的第j个前缀和， j=1 n。,算法2.2 SIMD-SM上非递归并行求前缀和高层描述算法,Begin /高层描述并行算法不考虑可用处理器的数目 (1)for j=1 to n par-do /初始化 B0,j=Aj end for /由叶到根生成高为logn的逻辑二叉树 / 正向遍历二叉树求前缀子和 (2)for h=1

4、to logn do / h为树层号 for j=1 to n/2h par-do /n/2h 为h层结点数 Bh,j=Bh-1,2j-1*Bh-1,2j end for end for,/ 自顶向下反向遍历二叉树播送前缀子和 (3) for h=logn to 0 do / h为树层号 for j=1 to n/2h par-do /n/2h 为h层结点数 (i) if j=even then / 该结点为其父结点右儿子 Ch,j=Ch+1,j/2 end if (ii) if j=1 then /该结点为最左结点 Ch,1=Bh,1 end if (iii) if j=odd1 then

5、/该结点为其父结点左儿子 Ch,j=Ch+1,(j-1)/2*Bh,j end if end for end for End,复杂度分析: 步(1)时间：O(1)，步(2)：logn O(1)= O(logn)，步(3)：logn O(1)= O(logn)， t(n)= O(1)+ O(logn) +O(logn)= O(logn) ， p(n)=n/2 , c(n) = n/2 O(logn) =O(nlogn) 代价非最优（原因：活跃处理器数目逐层减半） W(n)=n+(n/21 + n/22 + + n/2logn)+(n/2logn + n/21 + n/20)=n+(n-1)+(2

6、n-1)=3n-2=O(n),2.2 倍增技术(指针跳跃技术，pointer jumping),设计思想 对于规模为n的问题，每当递归（迭代）调用时，将所要处理数据之间的距离（下标，规模）逐步加倍，经过k=logn步后，即可完成距离(规模)为2k =n的所有数据的计算（处理）。 倍增技术特别适合于处理链表或有向树之类的数据结构。 2.2.1 表序问题 设L为n个元素的线性表，求出L中每个元素k在L中的次第号rank(k) （位序，秩）, rank(k) =L中“小于”k的元素数目。,算法2.4 SIMD-EREW上求元素表序并行算法 引入指针数组next(k)，定义next(k)为k 的下一个

7、元素，若为最后一个元素，则next(k)=k,Begin (1) for all k in L do in parallel / O(1) (1.1) P(k)=next(k); / P(k)表示k的后继 (1.2) if P(k) != k then distance(k) =1 else distance(k) =0 / distance(k)为k的距离 (2) repeat logn 次 / O(logn) (2.1) for all k in L do in parallel / O(1) if P(k)!=P(P(k) then / 如果k的后继不等于k的后继之后继 (i) dist

8、ance(k)= distance(k)+ distance(P(k) / 距离倍增 (ii) P(k)=P(P(k) / 指针跳跃 (2.2) for all k in L do on parallel / O(1) rank(k)=distance(k) / k的位序倍增，第 i 次确定2i个元素的位序，i=0lgn-1 End 算法复杂度：t(n)= O(1) +logn( O(1)+O(1)= O(logn), p(n)=n,c(n)=O(nlogn),并行求线性表中元素位序示例：n=7,(1) pa=b, pb=c, pc=d, pd=e, pe=f, pf=g, pg=g ra=r

9、b=rc=rd=re=rf=1, rg=0 (2) pa=c, pb=d, pc=e, pd=f, pe=pf=pg=g ra=rb=rc=rd=re=2, rf=1, rg=0 (3) pa=e, pb=f, pc=pd=pe=pf=pg=g ra=4, rb=4, rc=4, rd=3, re=2, rf=1, rg=0 (4) pa=pb=pc=pd=pe=pf=pg=g ra=6, rb=5, rc=4, rd=3, re=2, rf=1, rg=0,2.2.2 求森林的根,问题描述 一组有向树F中, 如果是F中的一条弧，则pi=j(即j是i的双亲)；若i为根，则pi=i。求每个结点j

10、(j=1n)的树根sj. 求森林根并行算法：算法2.5， p69-70, 时间t(n)=O(logn),初始时 P1=p2=5；p3=p4=p5=6；P6=p7=8；8=8 P9=10；p10=11；p11=12； p12=13；p13=13 si=pi,示例,第一次迭代后 第二次迭代后,2.3 分治策略,设计思想 将原问题划分成若干个类型相同的子问题分而治之，若子问题仍然较大，则反复递归应用分治策略处理这些子问题，直至子问题易求解为止。 2.3.1 （并行）分治策略求解问题步骤 将输入划分成若干个规模相等的子问题； 同时(并行地)递归求解这些子问题； 并行地归并子问题的解成为原问题的解。 分

11、治策略的重点：如何归并子问题的解。 如果归并的开销太大，那么可以使用流水线方式的级联分治策略进行归并。,2.3.2 SIMD-SM上FFT并行算法,1、串行FFT递归算法 DFT离散傅里叶变换的定义 给定向量 ，DFT将A变换为 ，即 写成矩阵形式为 串行直接计算DFT的算法需要O(nlogn) 时间,2、FFT递归并行算法思想：将20个规模为n的原问题的DFT划分为21个规模为n/2的子问题的DFT；将21个规模为n/2的子问题DFT划分为22规模为n/22的子问题的DFT；依次类推；直到将2logn-1个规模为n/2logn-1=2的子问题为止直接求解 。,算法2.7 SIMD-EREW上

12、FFT并行算法,Procedure Para-FFT(x,y) / t(n), W(n) Begin if n=2 then y0=x0+x1; y1=x0-x1; return / O(1), W1(n)=1 for l=0 to n/2-1 do in parallel / O(1), W2(n)=2(n/2)=n (2.1) ul=xl + xn/2+l ; (2.2) vl=wl(xl - xn/2+l ); (3) Do in step (3.1), (3.2) in parallel / 并行分治、递归 (3.1) Para-FFT(u0,u1,un/2-1 ), z(1)=(z0

13、(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) For j=0 to n-1 do in parallel /并行归并；O(1), W3(n)=2n (4.1 ) if j=even then yj= zj/2(1) (4.2 ) if j=odd then yj= z(j-1)/2(2) End., 算法复杂度：t(n)=O(1)+O(1)+t(n/2)+O(1)=t(n/2)+O(1)=O(lo

14、gn), p(n)=n/2. C(n)=n/2O(logn)=O(nlogn),代价最优, Sp(n)=O(nlogn)/O(logn)=O(n)，线性加速 W(n)= W1(n)+ W2(n)+ 2W(n/2) + W3(n) =1+ n+ 2W(n/2) +2n= 2W(n/2) +O(n) = 22W(n/22) +2O(n) = 23W(n/23) +3O(n) =O(nlogn),2.4 划分原理,设计思想 将原问题划分成p个独立的规模几乎相等的子问题； p个处理器并行地求解各子问题。 划分方法重点：如何划分问题以使得子问题解很容易被组合成原问题的解。 常见的划分方法 均匀划分：将n

15、个元素划分为p组，每组n/p个元素，处理器Pi 处理第i 组 A(i-1) n/p+1in/p, i=1p 方根划分：将n个元素划分为n1/2组，每组n1/2个元素，处理器Pi处理第i 组A(i-1) n1/2 +1 i n1/2, i=1 n1/2 对数划分：将n个元素划分为logn组，每组n/ logn个元素，处理器Pi处理 第i 组 A(i-1) n/logn+1i n/logn, i=1log n 功能划分：根据功能将原问题划分成若干不同功能的子问题，这些子 问题被并行处理,均匀划分方法应用示例,算法2.8 MIMD-SM模型上的PSRS（规整抽样）排序算法 Begin (1) 均匀划分：将n个元素A1n均匀划分成p段，每个Pi处理A(i-1) n/p+1in/p, i=1p (2) 并行局部排序：Pi调用串行排序算法对A(i-1)n/p+1in/p排序, i=1p (3) 并