93SIMD互连网络模型的并行算法

19．3SIMD互连网络模型的并行算法（一）网孔上的随机序列搜索算法给定一整数序列S=(s1,…,sn)和一整数x，S不一定有序且各元素不一定相异，确定S中是否有数等于x。在nn网孔连接的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和b2,2则两个相邻列之间P(1,2)和P(2,2)分别同时发送(b1,2,x)和(b2,2,x)给P(1,3)和P(2,3)，…，这种行列交替的展开过程一直继续到x到达P(n,n)为止；②折叠：展开结束后，每个处理器都有机会看到x，并将其与自己保存的s相比较，折叠式展开的逆过程，即输出响应位经逐行、逐列，以交替方式自右至左，自底至上回收到P(1,1)。并行算法：1234567891011121314算法9.3.1串行输入和输出的网孔上的搜索算法输入：随机序列S=(s1,…,sn)和x输出：若si,j=x，则bi,j=1，否则为0MESHSEARCH(S,x,k){/*P(1,1)读取输入*/if(x==s1,1){b1,11;}else{b1,10;}/*展开*/for(i=1;i=1n;i++){parfor(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+11;}else{bj,i+10;}}}215161718192021222324252627282930313233343536373839404142434445464748parfor(j=1;j=i+1;j++){P(i,j)发送(bi,j,x)给P(i+1,j);if(x==si+1,j||bi,j==1){bi+1,j1;}else{bi+1,j0;}}/*折叠*/for(ni;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||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);}parfor(j=1;j=i-2;j++){bi-1,jbi,j;}if(bi-1,i-1==1||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;}}在网孔上的随机序列搜索算法中，读取和输出各取常数时间，展开和折叠共迭代1n次，每次取常数时间，所以提问(即确定S中是否有数等于x)的时间为)(nO。因为展开的第一次迭代之后，P(1,1)已空闲，它就可接受新的提问；在相继迭代过程中，其它处理器也有类似情况，所以提问可以流水线方式处理。例9_5令一个16记录的文件已存在4×4网孔连接的SIMD机器中。图9_15(a)中每个方块代表一个处理器，其内的数字是有关记录的s域。现在欲决定是否存在3一个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)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的向量U=[u1,u2,…,un]T得到一个具有m个元素的列向量V=[v1,v2,…,vn]T。nnmnmmnnvvvuuuaaaaaaaaa2121212222111211.....................其中V中元素vi为njjijiuav1,1≤i≤m。在树的连接SIMD机器上作矩阵和向量相乘时，假定二叉树如图9_16进行组织，图中m=3和n=4：树有n个叶处理器P1,…,Pn；有n-2个内节点处理器Pn+1,…,P2n-2；还有一个根处理器P2n-1。其中叶处理器Pi中存有向量ui；矩阵A逐行由叶处理器P1~Pn输入。4算法思想：①当叶处理器Pi收到aji时，计算ajiui并将结果发送往其父节点；②当中间节点(即内节点)或根节点从其两个子节点收到输入时，先求和再将结果发往其父节点；③最终vj由根节点产生。v1v2v3P7P5P6P1P2P3P4a11a12a13a14a21a22a23a24a31a32a33a34图9_16树机上的矩阵向量乘法并行算法：1234567891011121314151617算法9.3.2SIMD-BT模型上的矩阵乘向量算法输入：U=[u1,…,un]T存于叶中，Am×n由叶处理器输入输出：根节点产生V=[v1,…,vm]TBTREEMATRIX-VECTORMULTIPLICATION(A,U){parfor(i=1;i=n;i++){for(j=1;j=m;j++){computeaji×ui;sendresulttoparent;}}parfor(i=n+1;i=2n-1;i++){while(Pireceivestwoinputs){computethesumofthetwoinputs;if(i2n-1){sendtheresulttoparent;}else{produceresultasoutput;}}u1u2u3u451819}}在树机上的矩阵和向量乘法中，从A的第一行进入到叶节点，到v1出现在根节点，中间花费了logn步；m-1步之后，vm正好出现在根节点。所以算法总共花了(m-1+logn)步。（三）一维线性阵列上的奇偶转置排序算法奇偶转置排序，待排序的n个数的输入序列S=(x1,x2,…,xn)，且有n个处理器可用。在算法的执行过程中，处理器Pi(1≤i≤n)存有输入数yi，开始时yi=xi，经过排序后对所有的1≤i≤n-1，有yiyi+1。算法思想：（1）所有奇数编号的处理器Pi均被激活，且接收来自Pi+1中的yi+1的副本，若yiyi+1，则Pi和Pi+！彼此交换内容；（2）所有偶数编号的处理器Pi均被激活，且接收来自Pi+1中的yi+1的副本，若yiyi+1，则Pi和Pi+！彼此交换内容。交替重复上述两步，经2/n次迭代后算法结束。并行算法：12345678910111213算法9.3.3SIMD-LC模型上奇偶转置排序算法输入：S=(x1,x2,…,xn)输出：S=(y1,y2,…,yn),yiyi+1,1≤i≤n-1O-ETRANSPOSITIONSORT{for(k=1;k=2/n;k++){parfor(i=1;i=12/2n;i=i+2){if(yiyi+1){yiyi+1;}}parfor(i=2;i=2/)1(2n;i=i+2){if(yiyi+1){yiyi+1;}}}}6算法分析：在一维线性阵列上的奇偶转置排序算法中，处理器个数为n，第①步和第②步执行一次比较和两次数据传输都可在常数步内完成。整个算法执行2/n次，所以总的时间t(n)=O(n)。例9_6对输入序列S=(7,6,5,4,3,2,1)的奇偶转置排序过程如图9_17所示图9_17奇偶转置排序过程（四）树机上的排序算法算法的基本思想：①n个待排序的数开始时加载到个叶处理器；②每个内节点同时比较其两个子节点中的数，并将较小者送往其父节点；③经过1+logn步之后，S中最小者将由根节点输出并存放于输出缓冲区。重复以上步骤，每次可将一个次小者依次放入输出缓冲区中。算法的描述：123456算法9.3.4SIMD-TC模型上求最小值算法输入：S=(x1,x2,…,xn)输出：非降序有序序列MINMUMEXTRACTIONSORT(S){(1)parfor(all叶节点){Pi读取输入序列S的一个元素;}(2)for(i=1;i=2n+(logn)-1;i++)778910111213141516171819202122232425262728{parfor(all内结点){if(Pi为根节点){将其放入输出缓冲区;}elseif(Pi为空){激活两个子节点;if(其中一个子结点为空){将非空节点数送往父结点;}elseif(两子节点均不为空){将较小子节点数送往父结点;}}}}}在树机上求最小值算法中，处理器个数为2n-1，读取S需要常数时间O(1)；因为树高为1+logn，所以产生待排序的第一个元素是在1+logn之后；在根节点处需要两个单位时间，一是从两个子节点中获得最小数，二是将其放入输出缓冲区，所以对于其余的n-1个数，每两步产生一个次小数，总共需要的时间为2n+(logn)-1。例9_7对于输入序列S=(8,7,6,5,4,3,2,1)在树机上求最小值的过程如图9_18所示。输出缓冲(a)输出缓冲(b)输出缓冲输出缓冲75318642876543218(c)(d)输出缓冲(e)1输出缓冲(f)1输出缓冲(g)12输出缓冲(h)12输出缓冲(i)123输出缓冲(j)123输出缓冲1234输出缓冲123476548765487653487653847652384765238476513284751386429(k)(l)输出缓冲(m)12345输出缓冲(n)12345输出缓冲(o)123456输出缓冲(p)123456输出缓冲(q)1234567输出缓冲(r)1234567输出缓冲123456788887787687687658765810(s)图9_18树机上求最小值的过程（五）树机上的连通分量算法图G的连通分量是G的一个最大子图，使得子图中的每对顶点间均有一条路径。在树机上，设编号为1,2,…,n的n点无向图由邻接矩阵表示，其中顶点i和j之间有边，则eij=1，否则为0。两顶点间如果有一路径，则此两顶点处于同一连通分量中。当算法结束时，第i个叶处理器含有顶点i所属的连通分量中最小的顶点标号。算法运行n遍，每遍考虑邻接矩阵的一行，即在第i遍时，只将邻接矩阵的第i行读入树的叶节点处理器中。顶点i的现行连通分量标号也保持在叶节点中。算法的基本思想是：当读第j行时，就知道所有与j相邻的顶点，这样，顶点j以及它的相邻者和那些处在相同连通分量中的顶点均必须归并成一条连通分量。其方法是：求找顶点j和与j相邻的任意顶点的最小连通分量标号c；将c播送给所有的叶节点，若任何顶点k的连通分量是这些被归并者之一，就将k的连通分量设置为c。设每个叶节点处理器有一个整型变量component[i]，它等于包括顶点i的现行连通分量标号，尚有一位当且仅当eij=1时edge[i]才为1的变量；还有一位