9.2 SIMD共享存储模型的并行算法.doc

9．2 SIMD共享存储模型的并行算法 （一） 播送算法 基本思想： 为解决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。 并行算法： 1 2 3 4 5 6 7 8 9 10 算法9.2.1 播送算法 输入：共享存储器中数据m，N个处理器，共享数组B 输出：所有的N个处理器都接受到数据m BROADCAST(m,N,B) { 处理器P1将m复制到存储器中; 处理器P1将m写入B[1]; for(i=0;i= log N -1;i++) par for(j=1;j=2i;j++) { 处理器Pj将B[j]复制到自己的存储器中; 处理器Pj将B[j]写入B[2i+j]; } } 算法分析： 在该并行算法中，并行写入数组的时间复杂度为O(log N)，并行读取数据m的时间复杂度为O(1)，因此该算法的时间复杂度为O(log N)。 （二）求和算法 求和是指处理器Pi (1≤i≤N)中含有数据Si，用和来代替Pi中的Si。求和算法的基本思想是充分利用上次累加结果来作下次并行累和。第j次累加(0≤j ≤log N -1)为： 2j＜i≤N 显然对于i≤2j+1有[1004]： 具体步骤 ： 第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+，其中j=log N -1。 并行算法： 1 2 3 4 5 6 7 8 算法9.2.2 求和算法 输入：S1,S2,…,SN 输出：Pi中的Si为和，i=1,2,…,N ALLSUMS(S1,S2,…,SN) { for( j=0;j=log N -1;j++) par for(i=2j+1;i=N;i++) { 处理器Pi经共享存储器获得; Si(Si+; } } 该并行算法的时间复杂度为O(log N)。 例9_1 当N=7时并行求和的执行过程如图9.12所示。 + + + + + + 第一步 S1 S2 S3 S4 S5 S6 S7 + + + + + 第二步 S1 S2 S3 S4 S5 S6 S7 第三步 S1 S2 S3 S4 S5 S6 S7 图9_12 N=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个最小者为止。 并行算法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 算法9.2.3 并行k-选择算法 输入：S=(x1,…,xn),|S|=n 输出：S中第k个最小者(1≤k≤n) PARALLEL SELECT(k,S) { if(|S|3) {使用一个处理器return(k);} else { 将S分成长度各为nε的n1-ε个序列，每个各指派一个处理器;} par for(i=1;i=n1-ε;i++) { Pi使用顺序选择算法找其所辖子序列的中值m