92SIMD共享存储模型的并行算法

19．2SIMD共享存储模型的并行算法（一）播送算法基本思想：为解决N个处理器同时读取共享存储器中的数据m在SIMD-EREW机上引起的读冲突，可以使用一个长度为N的共享数组B(开始时为空，且用B(i)表示B的第i个位置)，每个处理器在读取数据m的同时向B的后继单元写入，通过延长B来增加下次读取的并行度，当算法结束时所有的N个处理器都接受到了数据m。具体步骤：(1)由处理器P1把m写入B[1]；(2)由处理器P1把B[1]写入B[2]；由P1,P2把B[1],B[2]并行写入B[3],B[4]中；…；由P1,P2,…,Pi把B[1],B[2],…,B[i]并行写入B[i+1],B[i+2],…,B[2i]中；…；由P1,P2,…,PN/2把B[1],B[2],…,B[N/2]并行写入B[N/2+1],B[N/2+2],…,B[N]中；(3)处理器Pi(i=1,…,N)从B[i]中并行读取数据m。并行算法：12345678910算法9.2.1播送算法输入：共享存储器中数据m，N个处理器，共享数组B输出：所有的N个处理器都接受到数据mBROADCAST(m,N,B){处理器P1将m复制到存储器中;处理器P1将m写入B[1];for(i=0;i=logN-1;i++)parfor(j=1;j=2i;j++){处理器Pj将B[j]复制到自己的存储器中;处理器Pj将B[j]写入B[2i+j];}}算法分析：在该并行算法中，并行写入数组的时间复杂度为O(logN)，并行读取数据m的时间复杂度为O(1)，因此该算法的时间复杂度为O(logN)。（二）求和算法求和是指处理器Pi(1≤i≤N)中含有数据Si，用和ijjS1来代替Pi中的Si。求和算法的基本思想是充分利用上次累加结果来作下次并行累和。第j次累加(0≤j≤logN-1)为：ddSjijijij)1(2)1()(2j＜i≤N2显然对于i≤2j+1有[1004]：ikkjiSS1)(具体步骤：第1步处理器Pi(2≤i≤N)计算SiSi+Si-1；第2步处理器Pi(3≤i≤N)计算SiSi+Si-2；第3步处理器Pi(5≤i≤N)计算SiSi+Si-4；……第j步处理器Pi(2j+1≤i≤N)计算SiSi+Sji2，其中j=logN-1。并行算法：12345678算法9.2.2求和算法输入：S1,S2,…,SN输出：Pi中的Si为和ijjS1，i=1,2,…,NALLSUMS(S1,S2,…,SN){for(j=0;j=logN-1;j++)parfor(i=2j+1;i=N;i++){处理器Pi经共享存储器获得Sji2;SiSi+Sji2;}}该并行算法的时间复杂度为O(logN)。例9_1当N=7时并行求和的执行过程如图9.12所示。++++++第一步S1S2S3S4S5S6S7+++++第二步S1S2S3S4S5S6S7第三步S1S2S3S4S5S6S73图9_12N=7时并行求和执行过程（三）并行k-选择算法并行k-选择算法，假定输入序列S=(x1,…,xn)，且系统中有N=n1-ε(0＜ε＜1)个处理器可用，欲求S中第k个最小者(1≤k≤n)。算法思想：(1)先将S分成若干个段，每段指派给一个处理器；(2)各段同时并行求取各自的中值(可使用任意的顺序选择算法)；(3)求各中值之中值，将其播送到各个处理器中；(4)以其为准，将S划分成分别小于、等于、大于该值的三个子序列；(5)以一定的规则判断各子序列长度与k值的大小关系，以确定k值，或继续在相应子序列中重复上述过程，直到找到第k个最小者为止。并行算法：1234567891011121314151617算法9.2.3并行k-选择算法输入：S=(x1,…,xn),|S|=n输出：S中第k个最小者(1≤k≤n)PARALLELSELECT(k,S){if(|S|3){使用一个处理器return(k);}else{将S分成长度各为nε的n1-ε个序列，每个各指派一个处理器;}parfor(i=1;i=n1-ε;i++){Pi使用顺序选择算法找其所辖子序列的中值mi(即第2n个最小者);Pi将mi写入共享存储器中数组M的第i个单元M(i);}调用PARALLELSELECT(2|M|,M)找M之中值m(即第2|M|个最小者);将S分成三个子序列S1,S2,S3，其中元素分别小于,等于,大于m;if(|S1|≥k){PARALLELSELECT(k,S1);}else{if(|S1|+|S2|≥k){return(m);}else{PARALLELSELECT(k-|S1|-|S2|,S3);}}}并行k-选择算法中，播送时间为O(logn1-ε)，每个处理器使用顺序选择算法求中值时间为O(nε)，使用归并划分法将S划分为S1,S2,S3的时间为O(nε)，该算法的时间复杂度为O(nε)。4例9_2对于S=(18,35,21,24,29,13,33,17,31,27,15,28,11,22,19,25,34,32,16,12,23,30,26,14,20)，|S|=25。假定N=5,k=6，于是ε=0.5。从25个数中选取第6个最小者的过程如图9_13所示。图9_13从25个数中选第6个最小者的过程（四）并行桶排序算法桶排序(BucketSorting)也称为分布排序(DistributedSorting)，一般执行过程分为三个阶段：①按键的特性将其分配到各个桶中；②在各桶内施行排序；③桶的组合输出。桶排序所需的桶数与键的属性有关。设n个待排序的数ci(0≤i≤n-1)取值范围为{0:m-1}，则须设有m个桶，即在公共存储器中开辟m个区域mj(0≤j≤m-1)，每个桶对应一个区域，处理器从0开始按顺序编号，Pi指派给ci，且处理器Pi负责将号码i置于相应的ci桶中，然后用桶中的处理号码去激活相应处理器以给出排序好的文件。由于n个数的序列中可能有重复元素，从而导致多个处理器同时向同一桶中存放不同i值，为了彻底解决存冲突，可将每个桶扩容至n个存储单元，从而存储空间复杂度为O(m×n)。采用删除相同元素重复副本的方法来实现并行桶排序，对于处理器Pi，如果存在另一个处理器Pj，其中ji且cj=ci，那么Pi就暂时被封锁(即不活动)。具体方法是：对每个存储区域mj，分配n个单元(编号从0到n-1)，每个处理器可以决定同一区域中其它处理器(称为伙伴)是否是活5动的。若是活动的，则具有较高序号的处理器不活动；若伙伴是不活动的，或者它是活动的但具有较高的序号，则处理器将继续工作，将其标记移向序号比它小的伙伴位置。经过logn次迭代后，一个区域的第一个位置，当且仅当在该区域中的任一个处理器当初是活动的，将被标记。123456789101112131415161718192021222324252627282930算法9.2.4并行桶排序算法输入：AREA[j,i]=0(共处理器留下标记用)，BUCKET[j]=-1(保存处理器号码)，其中0≤i≤n-1,0≤j≤m-1；ci∈{0:m-1}输出：若ci=j则BUCKET[j]=min{i}；否则BUCKET[j]=0令ek=0…010…0(从右数起第k位为1，其余均为0)PARALLELBUCKETSORT(AREA,BUCKET,ci){parfor(i=0;i=n-1;i++){(1)令i=blogn…b1/*是i的二进制表示*/(2)xi;/*x是标记Pi的位置*/(3)AREA[ci,x]=1/*指明Pi的存在且正在活动*/(4)activeTRUE;(5)for(k=1;k=logn;k++)/*在同一区域内决定其伙伴是否是活动的*/{Buddyx○+ek;/*伙伴的地址，○+操作完成x的第k位取补*/CountAREA[ci,buddy];/*若伙伴是活动的,count≠0*/if(xk==1&&count≠0)/*xk表示从右数起的x的第k位*/{ActiveFALSE;/*若伙伴是活动的且Pi的序号较高，则Pi被封锁，而伙伴继续工作*/}if(xk==1&&count≠0&&active){AREA[ci,x]=0;/*若伙伴不是活动的且Pi的序号较低，则Pi将其标记移向伙伴的位置*/Xbuddy;AREA[ci,x]=1;}}(6)if(active){BUCKET[ci]i;}}}并行桶排序算法的存储空间为O(m×n)，使用了n台处理器而运行的时间为O(logn)。6例9_3设n=8，数的取值范围是{0:4}，即m=5(为此设有5个桶)且起始分布如下：处理器Pi：ciP0：2P1：1P2：4P3：2P4：0P5：4P6：3P7：4BUCKET[j]-1-1-1-1-1AREA[j,i]PiMj01234567000000000100000000200000000300000000400000000因为是并行算法，所以算法9.2.4中第(2)、(3)、(4)步对所有的i均同时执行，其结果，AREA[j,i]分布如下：AREA[j,i]PiMj01234567000001000101000000210010000300000010400100101所有的处理器均是活动的。对于第(5)步的循环顺序执行如下：i=0=000(i的二进制表示)k=1k=2k=3x：000000000ek：001010100………buddy：001010100BUCKET[2]=0i=1=001k=1x：001ek：001…buddy：000因为x1=1且count=0同时active=TRUE，所以P1将其标记移向他的伙伴位置(000)。现在x=000，循环的其余部分不再变化。BUCKET[1]=1i=2=010k=1k=2x：010010ek：0010107……buddy：011000处理器P2将其标记移向位置000BUCKET[4]=2i=3=011k=1k=2x：011011ek：001010……buddy：010001经过k=1后，处理器将其标记移向其伙伴位置010。K=2之后，伙伴序号较低且是活动的，所以处理器被封锁因为不向桶中写数。由此看出，如果开始时在同一区域中不止一个处理器是活动的，则只有最小i的Pi才能向桶中置数。算法结束时，各桶中内容如下：BUCKET[j]iPiciBUCKET[0]4P40BUCKET[1]1P11BUCKET[2]0P02BUCKET[3]6P63BUCKET[4]2P24（五）有序表搜索并行算法有序表搜索并行算法，假定文件f包含有n个记录，每个记录含有一个s域；诸s域按非降序排列，即s1≤s2≤…≤sn，给定整数x，有N个处理器(1＜N≤n)，为确定S=(s1,…,sn)中某一sk是否等于x，每次将序列划分成N+1个等长子序列，N个处理器同时将相继子序列之间的边界元素s与x进行比较：若sx，则放弃所有大于等于s的元素；若sx，则放弃所有小于等于s的元素。显然每个处理器都会放弃明显不包含x的段因为S是非降有序序列，所以第一次迭代将取各个保留段的公共区间作为下一次迭代的子序列，其长度为原序列长度的1/(N+1)。此序列在下一次迭代时再按上述同样方法进行，直到找到x或者所有元素均被放弃为止。具体的，令ji为处理器Pi试探元素的下标，ijs为S中Pi所试探的元素，ijs与x比较之后，Pi赋值ci：当xsij时，ci=left，即Pi保留ijs左边的元素；当xsij时，ci=right，即Pi保留ijs右边的元素。并且约定c0=right和cN+1=left。若ci≠ci-1则下一次被搜索的序列将从sq到sr，其中q=(i-1)(N+1)g-1+1(左边界)，r=i(N+1)g-1-1(右边界)。因为正好只有一个处理器更新共享存储器中的q和r，而所有其它的处理器可同时读取此更新的值，所以该算法的模型是SIMD-CREW。该并行算法的描述如下：算法9.