资源描述：
《共享存储模型的并行算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、9．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]并行
2、写入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++){处理器
3、Pj将B[j]复制到自己的存储器中;处理器Pj将B[j]写入B[2i+j];}}算法分析：在该并行算法中，并行写入数组的时间复杂度为O(logN)，并行读取数据m的时间复杂度为O(1)，因此该算法的时间复杂度为O(logN)。（二）求和算法求和是指处理器Pi(1≤i≤N)中含有数据Si，用和来代替Pi中的Si。求和算法的基本思想是充分利用上次累加结果来作下次并行累和。第j次累加(0≤j≤logN-1)为：2j＜i≤N显然对于i≤2j+1有[1004]：具体步骤：第1步处理器Pi(2≤i≤N)计算SißSi+Si-1；第2步处理器Pi(3≤i≤N)计算SißS
4、i+Si-2；第3步处理器Pi(5≤i≤N)计算SißSi+Si-4；……第j步处理器Pi(2j+1≤i≤N)计算SißSi+，其中j=logN-1。并行算法：12345678算法9.2.2求和算法输入：S1,S2,…,SN输出：Pi中的Si为和，i=1,2,…,NALLSUMS(S1,S2,…,SN){for(j=0;j<=logN-1;j++)parfor(i=2j+1;i<=N;i++){处理器Pi经共享存储器获得;SißSi+;}}该并行算法的时间复杂度为O(logN)。例9_1当N=7时并行求和的执行过程如图9.12所示。++++++第一步S1S2
5、S3S4S5S6S7+++++第二步S1S2S3S4S5S6S7第三步S1S2S3S4S5S6S7图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值
6、的大小关系，以确定k值，或继续在相应子序列中重复上述过程，直到找到第k个最小者为止。并行算法：1234567891011121314151617算法9.2.3并行k-选择算法输入：S=(x1,…,xn),
7、S
8、=n输出：S中第k个最小者(1≤k≤n)PARALLELSELECT(k,S){if(
9、S
10、<3){使用一个处理器return(k);}else{将S分成长度各为nε的n1-ε个序列，每个各指派一个处理器;}parfor(i=1;i<=n1-ε;i++){Pi使用顺序选择算法找其所辖子序列的中值mi(即第个最小者);Pi将mi写入共享存储器中数组M的第
11、i个单元M(i);}调用PARALLELSELECT(,M)找M之中值m(即第个最小者);将S分成三个子序列S1,S2,S3，其中元素分别小于,等于,大于m;if(
12、S1
13、≥k){PARALLELSELECT(k,S1);}else{if(
14、S1
15、+
16、S2
17、≥k){return(m);}else{PARALLELSELECT(k-
18、S1
19、-
20、S2
21、,S3);}}}并行k-选择算法中，播送时间为O(logn1-ε)，每个处理器使用顺序选择算法求中值时间为O(nε)，使用归并划分法将S划分为S1,S2,S3的时间为O(nε)，该算法的时间复杂度为O(nε)。例9
22、_2对于S=(18,35,21,24,29,13,3
