第六章 并行算法一般设计技术

第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术第六章并行算法的基本设计技术6.1划分设计技术求解步骤：①将给定问题分成p个相互独立的长度基本的子问题；②用p台处理器并行求解每个子问题。划分方法：均匀、方根、对数技术和功能划分等第六章并行算法的基本设计技术36.1.1均匀划分技术划分方法n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p示例：算法6.1MIMD-SM模型上的PSRS排序begin(1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理A[(i-1)n/p+1..in/p](2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序(3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素(4)样本排序：用一台处理器对p2个样本元素进行串行排序(5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并播送给其他pi(6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段(7)全局交换：各处理器将其有序段按段号交换到对应的处理器中(8)归并排序：各处理器对接收到的元素进行归并排序end.第六章并行算法的基本设计技术4例6.1n=27，p=3PSRS排序过程463384159761894069361491726399348207227325884975354211266154403621129391724846391514978472585333322720978969(d)采样排序：(c)正则采样：(b)局部排序：(a)均匀划分：(e)选择主元：63972124069203372612203339406972723369(f)主元划分：(g)全局交换：(h)归并排序：6615440362112939172484639151497725853333227209789696534846403936333227212015141297979391898472726961585465440364846393332272021121514978472978993917258536961第六章并行算法的基本设计技术6.1.2方根划分技术方根划分：取每第i(i=1，2，…)个元素作为划分元素将序列分成若干段，然后分段处理之n第六章并行算法的基本设计技术6划分方法n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)算法6.2SIMD-CREW模型上的Valiant归并(1975年发表)//有序组A[1..p]、B[1..q],(假设p=q),处理器数begin(1)方根划分:A,B分别按；(2)段间比较:A划分元与B划分元比较(至多对)，确定A划分元应插入B中的区段；(3)段内比较:A划分元与B相应段内元素进行比较，并插入适当的位置；(4)递归归并:B按插入的A划分元重新分段，与A相应段(A除去原划分元)构成了成对的段组，对每对段组递归执行(1)~(3)，直至A组为0时，递归结束;各组仍按分配处理器；end.pqkpqk）、分成若干段（和qjpiqjpi~1~1qppqk6.1.2方根划分技术第六章并行算法的基本设计技术7例:A={1,3,6,8,11,13}p=6;B={2,4,5,7,10,12,14},q=7=3,=3A={1,3,6*,8,11,13*}B={2,4,5*,7,10,12*,14},B’={2,4,5,6*,7,1012,13*,14}A11={1,3},A12={8,11},A13={}B11={2,4,5},B12={7,1012},B13={14}A11={1,3*},A12={8,11*},B11={2,4*,5},B12={7,10*,12},B11’={2,3*,4,5},B12’={7,10,11*,12},A111={1},A112={}A121={8},A122={}B111={2},B112={4,5}B121={7,10},B122={12}A111={1*}A121={8*}B111={2*}B121={7,10*}B111’={1*,2*}B121’={7,8*,10*}A1111={},A1112={}A1211={},A1212={}B1111={},B1111={}B1211={7},A1212={}pq第六章并行算法的基本设计技术8算法分析(1)算法在并行递归过程中所需的处理器数≤pqk段间比较:qp比较对数≤kpq＝；段内比较:kpqqp＝）－（1递归调用:设A,B分成若干子段对为(p1,q1),(p2,q2),……则∑pi≤p,∑qi≤q,由Cauchy不等式＝kpqqpqpqpiiiiii综上，整个过程可用处理器数pqk完成。(2)时间分析记λi是第i次递归后的A组最大长度，＝p0,ipii21算法在Ci常数时终止递归，即Cpi常数2＝1loglogCpi常数由(1)知算法中其他各步的时间为O(1),所以Valiant归并算法时间qppOqptk)log(log),(第六章并行算法的基本设计技术6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术第六章并行算法的基本设计技术106.1.3对数划分技术划分方法n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn示例：PRAM-CREW上的对数划分并行归并排序(1)归并过程:设有序组A[1..n]和B[1..m]j[i]=rank(bilogm:A)为bilogm在A中的位序，即A中小于等于bilogm的元素个数(2)例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4=logm=log4=2=j[1]=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=…=8B0:3,9B1:16,21A0:4,6,7A1:10,12,15,18,20A和B归并化为(A0,B0)和(A1,B1)的归并b1blogmB=B1Bia1A=A1Ai............blogm+1......aj(1)aj(1)+1aj(2)......b2logmbilogm+1b(i+1)logmaj(i)+1aj(i+1)......A0B0第六章并行算法的基本设计技术6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术第六章并行算法的基本设计技术126.1.4功能划分技术划分方法n个元素A[1..n]分成等长的p组，每组满足某种特性。示例：(m,n)选择问题(求出n个元素中前m个最小者)功能划分：要求每组元素个数必须大于m；算法：p148算法6.4输入：A=(a1,…,an);输出：前m个最小者；Begin(1)功能划分：将A划分成g=n/m组，每组含m个元素；(2)局部排序：使用Batcher排序网络将各组并行进行排序；(3)两两比较：将所排序的各组两两进行比较，从而形成MIN序列；(4)排序-比较：对各个MIN序列，重复执行第(2)和第(3)步，直至选出m个最小者。End第六章并行算法的基本设计技术13功能划分技术(M)mmmmm(M)mmmMAXMINMAXMIN图6.3(m-n)-选择过程SSSSSS......第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术第六章并行算法的基本设计技术6.2分治设计技术6.2.1并行分治设计步骤6.2.2双调归并网络第六章并行算法的基本设计技术16将输入划分成若干个规模相等的子问题；同时(并行地)递归求解这些子问题；并行地归并子问题的解，直至得到原问题的解。6.2.1并行分治设计步骤第六章并行算法的基本设计技术6.2分治设计技术6.2.1并行分治设计步骤6.2.2双调归并网络第六章并行算法的基本设计技术186.2.1双调归并网络双调序列(p149定义6.2)(1,3,5,7,8,6,4,2,0)(8,7,6,4,2,0,1,3,5)(1,2,3,4,5,6,7,8)以上都是双调序列Batcher定理给定双调序列(x0,x1,…,xn-1),对于si=min{xi,xi+n/2}和li=max{xi,xi+n/2}，则小序列(s0,s1,…,sn-1)和大序列(l0,l1,…,ln-1)仍是双调序列第六章并行算法的基本设计技术19双调归并的基本原理是基于如下的Batcher定理：给定一个双调序列a1，a2，…，a2n，对于所有的1≤i≤n，执行ai和ai+n的比较交换得到bi=min(ai:ai+n)和ci=max(ai:ai+n)。所形成的两个子序列MIN=(b1，b2，…，bn)和MAX=(c1，c2，…，cn)均是双调序列，且对于所有的1≤i，j≤n，满足bi≤cj。证明：略6.2.1双调归并网络第六章并行算法的基本设计技术20双调归并网络的构造方法：一个2n个输入的双调归并网络可以遵循Batcher定理：首先并行地进行两两比较，分别形成两个大小为n的MIN和MAX序列；因为MIN和MAX都是双调的，它们可继续按照Batcher定理形成4个大小为n/2的MIN和MAX双调序列。此过程一直重复到最后，诸MIN和MAX序列中都只有两个元素为止。n元素双调归并器LHLHLHLHa1anan-1a2an+1an+2c1cn+1cnc2cn+2c2n-1c2na1a2a3a4b4b3b2b1n元素双调归并器......cn-1a2n-1a2n.........双调归并网络的构造(4，4)双调归并网络第六章并行算法的基本设计技术2137813116543116758413Min={3,6,5,4}Max={11,7,8,13}3546811713Min1={3,4},Max1={5,6}Min2={8,7},Max2={11,13}3456781113Min1Max1Min2Max2Min3Max3Min4Max4例：第六章并行算法的基本设计技术22(4,4)双调归并网络第六章并行算法的基本设计技术23Batcher双调归并算法输入：双调序列X=(x0,x1,…,xn-1)输出：非降有序序列Y=(y0,y1,…,yn-1)ProcedureBITONIC_MERG(x)Begin(1)fori=0ton/2-1par-do(1.1)si=min{xi,xi+n/2}(1.2)li=max{xi,xi+n/2}endfor(2)RecursiveCall:(2.1)BITONIC_MERG(MIN=(s0,…,sn/2-1))(2.2)BITONIC_MERG(MIN=(l0,…,ln/2-1))(3)outputsequenceMINfollowedbysequenceMAXEnd6.2.1双调归并网络第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术第六章并行算法的基本设计技术6.3平衡树设计技术6.3.1设计思想6.3.2求最大值6.3.3计算前缀和第六章并行算法的基本设计技术266.3.1平衡树设计技术设计思想以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。示例求最大值计算前缀和第六章并行算法的基本设计技术6.3平衡树设计技术6.3.1设计思想6.3.2求最大值6.3.3计算前缀和第六章并行算法的基本设计技术