资源描述：
《互连网络模型的并行算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、9．3SIMD互连网络模型的并行算法（一）网孔上的随机序列搜索算法给定一整数序列S=(s1,…,sn)和一整数x，S不一定有序且各元素不一定相异，确定S中是否有数等于x。在网孔连接的SIMD机器上，令si,j表示P(i,j)中保存的记录的s域，指定P(1,1)为输入和输出端口。算法思想：①展开：P(1,1)读取x(如x=s1,1则产生输出b1,1=1，否则为0)，(b1,1,x)与P(1,2)通信(如x=s1,2或b1,1=1则b1,2=1，否则为0)，两个相邻行之间，P(1,1)和P(1,2)分别同时发送(b1,1,x)和(b1,2,x)给P(2,
2、1)和P(2,2)，一旦计算出b2,1和b2,2则两个相邻列之间P(1,2)和P(2,2)分别同时发送(b1,2,x)和(b2,2,x)给P(1,3)和P(2,3)，…，这种行列交替的展开过程一直继续到x到达P(,)为止；②折叠：展开结束后，每个处理器都有机会看到x，并将其与自己保存的s相比较，折叠式展开的逆过程，即输出响应位经逐行、逐列，以交替方式自右至左，自底至上回收到P(1,1)。并行算法：1234567891011121314算法9.3.1串行输入和输出的网孔上的搜索算法输入：随机序列S=(s1,…,sn)和x输出：若si,j=x，则bi,j
3、=1，否则为0MESHSEARCH(S,x,k){/*P(1,1)读取输入*/if(x==s1,1){b1,1ß1;}else{b1,1ß0;}/*展开*/for(i=1;i<=;i++){parfor(j=1;j<=i;j++){P(j,i)发送(bj,i,x)给P(j,i+1);if(x==sj,i+1
4、
5、bj,i==1){bj,i+1ß1;}else{bj,i+1ß0;}}}15161718192021222324252627282930313233343536373839404142434445464748parfor(j=1;j<=i+1;
6、j++){P(i,j)发送(bi,j,x)给P(i+1,j);if(x==si+1,j
7、
8、bi,j==1){bi+1,jß1;}else{bi+1,jß0;}}/*折叠*/for(;i>=2;i--){parfor(j=1;j<=i;j++){P(j,i)发送bi,i给P(j,i-1);}parfor(j=1;j<=i-1;j++){bj,i-1ßbj,i;}if(bi,i-1==1
9、
10、bi,i==1){bi,i-1ß1;}else{bi,i-1ß0;}parfor(j=1;j<=i-1;j++){P(i,j)发送bi,j给P(i-1,j);}par
11、for(j=1;j<=i-2;j++){bi-1,jßbi,j;}if(bi-1,i-1==1
12、
13、bi,i-1==1){bi-1,i-1ß1;}else{bi-1,i-1ß0;}}/*P(1,1)产生输出*/if(b1,1==1){answerßyes;}else{answerßno;}}在网孔上的随机序列搜索算法中，读取和输出各取常数时间，展开和折叠共迭代次，每次取常数时间，所以提问(即确定S中是否有数等于x)的时间为。因为展开的第一次迭代之后，P(1,1)已空闲，它就可接受新的提问；在相继迭代过程中，其它处理器也有类似情况，所以提问可以流水线方式
14、处理。例9_5令一个16记录的文件已存在4×4网孔连接的SIMD机器中。图9_15(a)中每个方块代表一个处理器，其内的数字是有关记录的s域。现在欲决定是否存在一个s域等于15(即x=15)的记录。图9_15(b)~(h)图示了在阵列中15的传播过程。图9_15(i)示出算法第(2)步结束时有关的b值。图9_15(j)到(o)图示了折叠过程。图9_15(p)示出第(4)步产生的结果。注意，图9_15(e)处理器P(1,1)已空，指明它已完成了传播15的工作且现在可接受新的提问了。12348765910111216151413(a)15151515(b
15、)15151515(c)151515151515(d)151515151515(e)1515151515151515(f)1515151515151515(g)15151515151515151515(h)00000000100000(i)0000000010000(j)00000010000(k)000000100(l)0000100(m)00100(n)1000(o)000(p)图9_154×4网孔上搜索过程示例（二）树机上的矩阵和向量乘法矩阵-向量乘法(Matrix-VectorMultiplication)是将一个m×n阶矩阵A乘以n×1的向
16、量U=[u1,u2,…,un]T得到一个具有m个元素的列向量V=[v1,v2,…,vn]T。其中V中元素vi
