并行算法的设计与分析(15).ppt

并行算法的设计与分析,第15章图论并行算法,15.2图的传递闭包,15.2.1传递闭包1.定义给定有向图G=(V,E),A=(aij)nn为G的邻接矩阵,A的传递闭包A+=(bij)nn,bij为1时当且仅当顶点i到顶点j之间有一条路径：2.串行传递闭包算法时间复杂度:O(n3)示例,0100A=001000011000,2,1111A+=111111111111,15.2图的传递闭包,3.基于布尔矩阵乘积的图传递闭包算法原理令B=A+I,I为单位阵,B=(b(1)ij)nn,b(1)ij=1i=j或ij有有向边ij有长为0或1的有向路径.对于B2=(A+I)2=(b(2)ij)nn,b(2)ij=k=1nb(1)ikb(1)kj,表示“逻辑或”则有,b(2)ij=1顶点i顶点j有长度2的有向路径.类似地,Bk=(b(k)ij)nn,b(k)ij=1ij有长度k的有向路径.因此,A+=Br,rn-1所以,BB2B4B2=A+,共有次相乘,15.2图的传递闭包,4.示例,15.2图的传递闭包,5.SIMD-CC上的传递闭包算法求图传递闭包等价于求图的连通性(连通矩阵),用(A+I)自乘log(n-1)次获得将n3个处理器排成nnn的三维阵列,Pr的坐标为(i,j,k),r=i*n2+j*n+k，Pr有三个寄存器A(i,j,k),B(i,j,k)和C(i,j,k),0i,j,kn-1初始时:A(0,j,k)ajk，0j,kn-1;结束时:C(0,j,k)为A+的(j,k)元素算法15.1SIMD-CC上的传递闭包（连通矩阵）算法Begin/输入:Ann,输出:Cnn(1)forj=0ton-1doinparallelA(0,j,j)=1endfor/形成A+I矩阵,O(1)(2)forj=0ton-1doinparallel/O(1)fork=0ton-1doinparallelB(0,j,k)A(0,j,k)；/复制A给B(3)fori=1todo(3.1)调用SIMD-CC上矩阵乘法算法(A,B,C);/用代替求和，O(logn)(3.2)forj=0ton-1doinparallel/O(1)fork=0ton-1doinparallel/更新A，BA(0,j,k)C(0,j,k);B(0,j,k)C(0,j,k);endforEnd/t(n)=O(log2n),p(n)=n3,c(n)=O(n3log2n),Sp(n)=O(n3/log2n),15.3图的连通分量,15.3.1SIMD-CC模型上的连通分量算法1.利用求图传递闭包（连通矩阵）方法求连通分量算法原理(1)利用算法15.1求解图的传递闭包（连通矩阵C）；(2)构造矩阵D:djk=vk，当cjk=1时，0j,kn-10，其他(3)由D计算出顶点vj的分量号2.示例,15.3图的连通分量,由D计算连通分量=连通分量0:v0,v3,v6,v8连通分量1:v1,v4,v7连通分量2:v2,v5,15.3图的连通分量,3.SIMD-CC上图的连通分量算法/输入:A(0,j,k)ajk,0j,kn-1/输出:C(0,j,0)vj的连通分量号,0jn-1Begin(1)调用算法15.1(A,C)求出连通矩阵C;/O(log2n)(2)forj=0ton-1doinparallel/O(1)fork=0ton-1doinparallelifC(0,j,k)=1thenC(0,j,k)vk/构造矩阵D;(3)forj=0ton-1doinparallel第j行处理器P(0,j,k)寻找C(0,j,l)!=0的最小l;/k=0n-1,O(logn)C(0,j,0)l;/用二分竞赛树并行查找方法查找出最小lEnd算法复杂度：t(n)=O(log2n),p(n)=n3,c(n)=(n3log2n),Sp(n)=O(n3/log2n),15.4图的最短路径,15.4.1所有顶点对之间的最短路径1.设有向图G=(V,E)中无负权有向回路,边权矩阵W=(wij)nn,求最短路径长度矩阵D=(dij)nn.2.已有求最短路径长度方法：Dijkstra-Floyd的MatrixMultiplication3.基于矩阵乘法的求最短路径算法原理记d(k)ij为从顶点i到顶点j至多有k-1个中间顶点的最短路径长度(1)d(1)ij=wij，ij；若i,j之间无连边存在，则记d(1)ij=wij=0,i=j(2)应用贪心算法思想和组合最优性原理计算:d(k)ij=minl=1nd(k/2)il+d(k/2)lj注:“+”“”,“min”“”=Dk=Dk/2Dk/2(3)应用矩阵乘法:DD2D4D2=Dn,共有次相乘,15.4图的最短路径,将n3个处理器排成nnn的超立方结构,Pr的坐标为(i,j,k),r=in2+jn+k，Pr有三个寄存器A(i,j,k),B(i,j,k)和C(i,j,k),0i,j,kn-1。算法初始时：A(0,j,k)=wjk，0j,kn-1;结束时：C(0,j,k)为Vj-Vk的最短路径。算法15.5SIMD-CC模型上并行计算所有顶点对之间最短路径算法Begin(1)forj=0ton-1doinparallel/构造D1fork=0ton-1doinparallel/O(1)时间ifj!=kandA(0,j,k)=0thenA(0,j,k)=“无穷大”;/顶点i和j之间无边B(0,j,k)=A(0,j,k);(2)fori=1tolog(n-1)do/构造D2，D4，D8，.调用SIMD-CC上矩阵乘积算法(A,B,C);/+代替*，min代替；O(logn)forj=0ton-1doinparallelfork=0ton-1doinparallelA(0,j,k)=C(0,j,k);B(0,j,k)=C(0,j,k);