并行算法的设计与分析(7).ppt

并行算法的设计与分析,第7章并行搜索,7.2SIMD-SM模型上有序序列的并行搜索,1.问题描述设有序序列X=x1,x2,xn，令x0=-，xn+1=+，p个处理器并行进行p+1分搜索，以确定出任意输入的数据z是否出现在X中？2.算法描述算法7.1ParallelsearchingonPRAM-CREW/二分查找算法的并行化Begin(1)bot=0;top=n+1;c1p0;cp+1=1;/c为中间标志数组(2)while(bot+1xjthenci=0elseci=1;(2.2)newbot=bot;newtop=(top-bot)/(p+1);/取上整(2.3)fori=1topdoinparallelifcici+1thennewbot=bot+i(top-bot)/(p+1);newtop=bot+(i+1)(top-bot)/(p+1);(2.4)bot=newbot;top=newtop;/更新下次并行搜索区间的上下限endwhile(3)ifz=xtopthen输出匹配位置topEnd.,7.2SIMD-SM模型上有序序列的并行搜索,3.算法复杂度因为下次迭代进行并行搜索时，待搜索的元素区间内的数据个数是当前搜索区间内数据个数的(p+1)分之一，也即第i次迭代并行处理时，待搜索的元素区间内的数据个数是(n+2)/(p+1)i，i=1k,k=logp+1(n+2)，所以算法所需的执行时间为t(n)=O(1)+i=1kO(1)+O(1)=O(k)=O(logp+1(n+2)=O(logp+1n)执行代价c(n)=pO(logp+1n)=O(plogp+1n)=O(p/logp*logn)加速比Sp(n)=O(logn)/O(logp+1n)=O(logp)/对数加速,7.2SIMD-SM模型上有序序列的并行搜索,3.算法示例X=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,n=16,z=1,p(n)=2迭代bottopnewbotnewtopc1c2c3j(P1)j(P2)初态0170016121060611124202021111230101111并行3-分搜索过程(相当于动态生成一棵三叉树)：-12345678910111213141516+-,123456-,12,7.5网孔连接的SIMD模型上随机序列的并行搜索,1.问题:任给无序序列S=s1,s2,sn,搜索输入x是否出现在S中?2.算法思想将n个数据存储在*的二维网孔机器上，每个结点（处理器）存储1个元素。(1)展开(unfolding):按从左至右,自上而下方式,逐行、逐列交替展开，将x播送给MESH的处理器,并将x与处理器中数据比较和保存比较结果;(2)折叠(folding):按从右到左,由底向上方式,逐列、逐行交替折叠，回收比较结果。3.算法描述算法7.6：SIMD-MC2上随机序列并行搜索输入：x和,si,j存放在Pi,j,bi,j是Pi,j的标志变量输出：若si,j=x,P1,1则输出yes，否则输出noBegin(1)ifx=s1,1thenb1,1=1elseb1,1=0endif/P1,1读入x(2)fori=1to-1do/展开:自左至右，自上而下，行列交替(2.1)forj=1toipar-do/当前已获得x的处理器的最大行数i(i)Pj,i发送(bj,i,x)给Pj,i+1/同列处理器自左向右传送;1个路由步(ii)if(x=sj,i+1orbj,i=1)thenbj,i+1=1elsebj,i+1=0endifendfor(2.2)forj=1toi+1par-do/当前已获得x的处理器的最大列数i+1(i)Pi,j发送(bi,j,x)给Pi+1,j/同行处理器自上向下传送;1个路由步(ii)if(x=si+1,jorbi,j=1)thenbi+1,j=1elsebi+1,j=0endifendfor,7.5网孔连接的SIMD模型上随机序列的并行搜索,(3)fori=downto2do/折叠:从右到左，自下而上，列行交替(3.1)forj=1toipar-doPj,i发送bj,i给Pj,i-1/同列处理器将bj,i自右向左传送;1个路由步(3.2)forj=1toi-1par-dobj,i-1bj,i/逐列更新比较结果;1个路由步(3.3)if(bi,i-1=1orbi,i=1)thenbi,i-1=1elsebi,i-1=0endif(3.4)forj=1toi-1par-doPi,j发送bi,j给Pi-1,j/同行处理器将bj,i自下向上传送;1个路由步(3.5)forj=1toi-2par-dobi-1,jbi,j/逐行更新比较结果;1个路由步(3.6)if(bi-1,i-1=1orbi,i-1=1)thenbi-1,i-1=1elsebi-1,i-1=0endifendfor(4)ifb11=1thenP11输出yeselse输出noendifEnd.4.算法复杂度:tc(n)=O(1)+(-1)O(1)+(-1)O(1)+O(1)=O();tr(n)=2(-1)+4(-1)=6(-1)路由步；t(n