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

并行算法的设计与分析第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;c[1··p]0;c[p+1]=1;//c为中间标志数组(2)while(bot+1top)do(2.1)fori=1topdoinparallel//并行p+1分搜索{j=bot+「i(top-bot)/(p+1)];//j为每个搜索子区间的中间位置，取上整ifzx[j]thenc[i]=0elsec[i]=1;}(2.2)newbot=bot;newtop=「(top-bot)/(p+1)];//取上整(2.3)fori=1topdoinparallelifc[i]c[i+1]then{newbot=「bot+i(top-bot)/(p+1)];newtop=「bot+(i+1)(top-bot)/(p+1)];}(2.4)bot=newbot;top=newtop;//更新下次并行搜索区间的上下限endwhile(3)ifz=x[top]then输出匹配位置topEnd.7.2SIMD-SM模型上有序序列的并行搜索3.算法复杂度因为下次迭代进行并行搜索时，待搜索的元素区间内的数据个数是当前搜索区间内数据个数的(p+1)分之一，也即第i次迭代并行处理时，待搜索的元素区间内的数据个数是(n+2)/(p+1)i，i=1~k,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迭代bottopnewbotnewtopc[1]c[2]c[3]j(P1)j(P2)初态0170016121060611124202021111230101111并行3-分搜索过程(相当于动态生成一棵三叉树)：-12345678910111213141516+-,123456-,127.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=0endifendforn),...,,......,,...,(1111nnnnssssSnn7.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-1bj,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,jbi,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)=O()+(-1)=O()Sp(n)=O(n)/O()=O()//方根加速nnnnnnnnnnnn7.5网孔连接的SIMD模型上随机序列的并行搜索5.示例:={1,2,3,4,8,7,6,5,9,10,11,12,16,15,14,13},x=15