互连网络模型的并行算法

1、93 SIMD互连网络模型的并行算法（一） 网孔上的随机序列搜索算法给定一整数序列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,1)和P(2,2)，一旦计算出b2,1和b

2、2,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)。并行算法：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748算法9.3.1 串行输入和输出的网孔上的搜索算法输入：随机序列S=(s1

3、,sn)和x输出：若si,j=x，则bi,j=1，否则为0MESH SEARCH(S,x,k)/*P(1,1)读取输入*/if(x=s1,1) b1,11;else b1,10;/*展开*/for(i=1;i=;i+)par for(j=1;j=i;j+) P(j,i)发送(bj,i,x)给P(j,i+1);if(x=sj,i+1 | bj,i=1) bj,i+11;else bj,i+10;par for(j=1;j=2;i-)par for(j=1;j=i;j+)P(j,i)发送bi,i给P(j,i-1);par for(j=1;j=i-1;j+) bj,i-1bj,i;if(bi,i-1

4、=1 | bi,i=1) bi,i-11;else bi,i-10;par for(j=1;j=i-1;j+) P(i,j)发送bi,j给P(i-1,j);par for(j=1;j=i-2;j+)bi-1,jbi,j;if (bi-1,i-1=1 | bi,i-1=1) bi-1,i-11;else bi-1,i-10;/*P(1,1)产生输出*/if(b1,1=1) answeryes;else answerno;在网孔上的随机序列搜索算法中，读取和输出各取常数时间，展开和折叠共迭代次，每次取常数时间，所以提问(即确定S中是否有数等于x)的时间为。因为展开的第一次迭代之后，P(1,1)已空

5、闲，它就可接受新的提问；在相继迭代过程中，其它处理器也有类似情况，所以提问可以流水线方式处理。例9_5 令一个16记录的文件已存在44网孔连接的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的工作且现在可接受新的提问了。12348765910111

6、216151413(a)1515 1515(b)1515 1515 (c)1515 1515 1515(d)15 1515 151515(e)1515 151515151515(f) 1515 151515151515(g) 15 151515151515151515(h) 00000000100000(i) 0000000010000(j) 00000010000(k)000000100(l)0000100(m)00100(n)1000(o)000(p)图9_15 44网孔上搜索过程示例（二） 树机上的矩阵和向量乘法矩阵-向量乘法(Matrix-Vector Multiplication)是

7、将一个mn阶矩阵A乘以n1的向量U=u1,u2,unT得到一个具有m个元素的列向量V=v1,v2,vnT。其中V中元素vi为, 1im。在树的连接SIMD机器上作矩阵和向量相乘时，假定二叉树如图9_16进行组织，图中m=3和n=4：树有n个叶处理器P1,Pn；有n-2个内节点处理器 Pn+1, P2n-2；还有一个根处理器P2n-1。其中叶处理器Pi中存有向量ui；矩阵A逐行由叶处理器P1Pn输入。算法思想： 当叶处理器Pi收到aji时，计算ajiui并将结果发送往其父节点； 当中间节点(即内节点)或根节点从其两个子节点收到输入时，先求和再将结果发往其父节点； 最终vj由根节点产生。u1u2u

8、3u4v1v2v3P7P5 P6P1 P2 P3 P4a11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a34图9_16 树机上的矩阵向量乘法并行算法：12345678910111213141516171819算法9.3.2 SIMD-BT模型上的矩阵乘向量算法输入：U=u1,unT存于叶中，Amn由叶处理器输入输出：根节点产生V=v1,vmTBTREE MATRIX-VECTOR MULTIPLICATION(A,U)par for(i=1;i=n;i+) for(j=1;j=m;j+)compute ajiui;send result to parent;

9、par for(i=n+1;i=2n-1;i+) while(Pi receives two inputs)compute the sum of the two inputs;if(i2n-1) send the result to parent;else produce result as output;在树机上的矩阵和向量乘法中，从A的第一行进入到叶节点，到v1出现在根节点，中间花费了log n步；m-1步之后，vm正好出现在根节点。所以算法总共花了(m-1+log n)步。（三） 一维线性阵列上的奇偶转置排序算法奇偶转置排序，待排序的n个数的输入序列S=(x1,x2,xn)，且有n个处理

10、器可用。在算法的执行过程中，处理器Pi (1in)存有输入数yi，开始时yi=xi，经过排序后对所有的1in-1，有yiyi+1，则Pi和Pi+！彼此交换内容；（2） 所有偶数编号的处理器Pi均被激活，且接收来自Pi+1中的yi+1的副本，若yiyi+1，则Pi和Pi+！彼此交换内容。交替重复上述两步，经次迭代后算法结束。并行算法：12345678910111213算法9.3.3 SIMD-LC模型上奇偶转置排序算法输入：S=(x1,x2,xn)输出：S=(y1,y2,yn), yiyi+1, 1in-1O-E TRANSPOSITION SORTfor(k=1;k=;k+)par for(i

11、=1;iyi+1) yi yi+1;par for(i=2;iyi+1) yi yi+1;算法分析：在一维线性阵列上的奇偶转置排序算法中，处理器个数为n，第步和第步执行一次比较和两次数据传输都可在常数步内完成。整个算法执行次，所以总的时间t(n)=O(n)。例9_6对输入序列S=(7,6,5,4,3,2,1)的奇偶转置排序过程如图9_17所示图9_17 奇偶转置排序过程（四） 树机上的排序算法算法的基本思想： n个待排序的数开始时加载到个叶处理器； 每个内节点同时比较其两个子节点中的数，并将较小者送往其父节点；经过1+log n步之后，S中最小者将由根节点输出并存放于输出缓冲区。重复以上步骤，

12、每次可将一个次小者依次放入输出缓冲区中。算法的描述：12345678910111213141516171819202122232425262728算法9.3.4 SIMD-TC模型上求最小值算法输入：S=(x1,x2,xn)输出：非降序有序序列MINMUM EXTRACTION SORT(S)(1) par for(all 叶节点)Pi读取输入序列S的一个元素;(2)for(i=1;i=2n+(log n)-1;i+)par for(all内结点)if(Pi为根节点)将其放入输出缓冲区;elseif(Pi为空)激活两个子节点;if(其中一个子结点为空)将非空节点数送往父结点;elseif (两

13、子节点均不为空)将较小子节点数送往父结点;在树机上求最小值算法中，处理器个数为2n-1，读取S需要常数时间O(1)；因为树高为1+log n，所以产生待排序的第一个元素是在1+log n之后；在根节点处需要两个单位时间，一是从两个子节点中获得最小数，二是将其放入输出缓冲区，所以对于其余的n-1个数，每两步产生一个次小数，总共需要的时间为2n+(log n)-1。例9_7 对于输入序列S=(8,7,6,5,4,3,2,1)在树机上求最小值的过程如图9_18所示。输出缓冲87654321(a)输出缓冲75318642(b)输出缓冲75138642(c)输出缓冲76513284(d)1输出缓冲765

14、2384(e)1输出缓冲7652384(f)12输出缓冲765384(g)12输出缓冲765348(h)123输出缓冲76548(i)123输出缓冲76548(j)1234输出缓冲7658(k)1234输出缓冲7658(l)12345输出缓冲768(m)12345输出缓冲768(n)123456输出缓冲78(o)123456输出缓冲87(p)1234567输出缓冲8(q)1234567输出缓冲8(r)12345678输出缓冲(s)图9_18 树机上求最小值的过程（五） 树机上的连通分量算法图G的连通分量是G的一个最大子图，使得子图中的每对顶点间均有一条路径。在树机上，设编号为1,2,n的n点无

15、向图由邻接矩阵表示，其中顶点i和j之间有边，则eij=1，否则为0。两顶点间如果有一路径，则此两顶点处于同一连通分量中。当算法结束时，第i个叶处理器含有顶点i所属的连通分量中最小的顶点标号。算法运行n遍，每遍考虑邻接矩阵的一行，即在第i遍时，只将邻接矩阵的第i行读入树的叶节点处理器中。顶点i的现行连通分量标号也保持在叶节点中。算法的基本思想是：当读第j行时，就知道所有与j相邻的顶点，这样，顶点j以及它的相邻者和那些处在相同连通分量中的顶点均必须归并成一条连通分量。其方法是：求找顶点j和与j相邻的任意顶点的最小连通分量标号c；将c播送给所有的叶节点，若任何顶点k的连通分量是这些被归并者之一，就将

16、k的连通分量设置为c。设每个叶节点处理器有一个整型变量componenti，它等于包括顶点i的现行连通分量标号，尚有一位当且仅当eij=1时edgei才为1的变量；还有一位当且仅当顶点i被选择时selectedi才为1的变量1007。该并行算法的描述如下：123456789101112131415161718192021222324252627282930313233算法9.3.5 SIMD-TC模型上的连通分量算法输入：nn的邻接矩阵输出：每个顶点的连通分量号SIMD-TC LIPTON-VALDESfor(all leaves i)componenti i /*初始化*/for(j=1;j

17、=n;j+)for(all leaves i)edgei eij; /*读第j行*/for(all leaves i)selectedi edgei; /*选择j和所有与j相邻的节点*/compute c=mincomponenti| selectedi=1 at the root;/*c是与j相邻节点的最小分量号*/broadcast c to all leaves;while(selectes processors remain)choose at the root some d=componenti such i that selectedi=1;broadcast d to all l

18、eaves;for(all leaves i)if(componenti=d)componenti c;selectedi 0;在树机上的连通分量算法中，处理器个数为n，初始化时间为O(log n)，因为初始化信号是由根发出的，一旦叶处理器收到此信号，将其复制到componenti寄存器中只要O(1)时间；假定叶节点的号码并没有放进叶处理器中，即处理器不知道其号码，而是由根告诉给它们，所以向所有的叶节点发送初始信号和正确的起始值就需要O(log2n)。用二叉树对所选的节点计算连通分量标号的最小值，需用O(log2n)时间。播送操作需O(log n)时间。While循环语句不会多于O(log2n)时间。而整个算法运