并行计算-多媒体课件-并行算法设计与分析-ch15_Graph_Algorithms.ppt

Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,Y.Xu Copyright USTC,Parallel Algorithms,*,/Ch15,Parallel Algorithms,Chapter,15,Graph Algorithms,2026/2/1 周日,Y.Xu Copyright USTC,主要内容,15.1,图的并行搜索,15.2,图的传递闭包,15.3,图的连通分量,15.4,图的最短路径,15.5,图的最小生成树,2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,15.1.1,算法原理,1.,并行搜索的一般方法,(1),建立一个主表和,p,个子表,;,(2),开始时主表空,任取一个顶点作为待搜索顶点,并置入主表,;,(3)p,个处理器分别搜索与该顶点相邻的边,将搜索到的顶点加入子表,;,(4),以一定的策略,将子表链到主表,并从主表中任取一个作为待搜索顶点,;,(5),重复,(3),、,(4),直至所有的顶点加入到主表,.,2.,串行搜索的上界,设搜索、加入顶点及表链接需要一个单位时间,则,T,s,i,=1n,(d,i,+1)=2m+n,d,i,为顶点,v,i,的度,注,:,因为每个待搜索顶点,v,i,需要检查,d,i,条邻接边,需要搜索,d,i,次,;,每个顶点,只可能加入一次,.,2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,3.,三种并行搜索示例,(1)p-,深度优先搜索,7,9,8,2,6,5,1,3,4,(a),图,G,2,1,4,3,7,8,6,9,5,(1),(1),(7),(2),(2),(6),(3),(3),(4),(5),(b),两个处理器的,p-,深度优先搜索,2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,(2)p-,宽深优先搜索,7,9,8,2,6,5,1,3,4,(a),图,G,2,1,5,3,7,8,6,9,4,(1),(2),(2),(3),(4),(5),(1),(3),(6),(c),两个处理器的,p-,宽深优先搜索,(5),2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,(3)p-,宽度优先搜索,7,9,8,2,6,5,1,3,4,(a),图,G,2,1,5,3,7,8,6,9,4,(1),(2),(2),(3),(4),(6),(1),(3),(6),(d),两个处理器的,p-,宽度优先搜索,(5),2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,15.1.2 p-,深度优先搜索,1.,算法描述,(1),主表为栈,任取一个顶点置入主表,;,(2),对栈顶元素开始搜索,p,个处理器搜索一次,将子表链接,到主表,;,(3),某顶点的边搜索完,从主表中删除,;,(4),重复,(2),(3),直至主表为空,.,2.,计算时间,搜索与顶点,i,相邻所有边的次数,p,个元素链接成一个子表的时间,2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,15.1.2 p-,宽深优先搜索,1.,算法描述,(1),主表为栈,任取一个顶点置入主表,;,(2),对栈顶元素开始搜索,p,个处理器搜索完所有的邻边,再将,子表链接到主表,;,(3),某顶点的边搜索完,从主表中删除,;,(4),重复,(2),(3),直至主表为空,.,2.,计算时间,搜索与顶点,i,相邻所有边的次数 将,p,个子表链接起来的时间,2026/2/1 周日,Y.Xu Copyright USTC,15.1,图的并行搜索,15.1.2 p-,宽度优先搜索,1.,算法描述,(1),主表为,FIFO,队列,任取一个顶点置入主表,;,(2),对队头元素开始搜索,并从主表中删除,;p,个处理器搜索完,所有的邻边,;,(3),将子表链接起来,并入主表中,;,(4),重复,(2),(3),直至主表和子表皆为空,.,2.,计算时间,宽度搜索的最大层数,2026/2/1 周日,Y.Xu Copyright USTC,主要内容,15.1,图的并行搜索,15.2,图的传递闭包,15.3,图的连通分量,15.4,图的最短路径,15.5,图的最小生成树,2026/2/1 周日,Y.Xu Copyright USTC,15.2,图的传递闭包,15.2.1,传递闭包,1.,定义,有向图,G=(V,E),A=(,a,ij,),nn,为邻接矩阵,A,的传递闭包,A,+,=(,b,ij,),nn,b,ij为,1,时当且仅当顶点,i,到顶点,j,之间有一条路径,这里,2.,串行算法,:O(n,3,),1,4,3,2,(a),1 1 1 1,1 1 1 1,1 1 1 1,1 1 1 1,(b),2026/2/1 周日,Y.Xu Copyright USTC,15.2,图的传递闭包,3.,基于布尔矩阵乘积的算法原理,令,B=A+I,I,为单位阵,B=(b,(1),ij,),nn,则有,b,(1),ij,=1,i=j,或,i,j,有有向边,i,j,有长为,0,或,1,的有向路径,对于,B,2,=(A+I),2,=(b,(2),ij,),nn,b,(2),ij,=,k=1n,b,(1),ik,b,(1),kj,这里,为逻辑或,则有,b,(2),ij,=1,i,j,有长度,2,的有向路径,.,类似地,B,k,=(,b,(k),ij,),nn,b,(k),ij,=1,i,j,有长度,k,的有向路径,.,因此,A,+,=B,r,(rn-1),所以,B,B,2,B,4,B,2,=A,+,共有 次相乘,2026/2/1 周日,Y.Xu Copyright USTC,15.2,图的传递闭包,4.,计算示例,1,4,3,2,(a),1 1 0 0,0 1 1 0,0 0 1 1,1 0 0 1,(b),B=A+I=,1 1 1 0,0 1 1 1,1 0 1 1,1 1 0 1,(c),B,2,=,1 1 1 1,1 1 1 1,1 1 1 1,1 1 1 1,(d),B,4,=,=A,+,2026/2/1 周日,Y.Xu Copyright USTC,15.2,图的传递闭包,5.SIMD-CC,上的传递闭包算法,-n,3,个处理器排成,nnn,的三维阵列,P,r,坐标为,(,i,j,k,),有三个寄存器,A(i,j,k,),B(i,j,k,),和,C(i,j,k,),其中,r=in,2,+jn+k,(0i,j,kn-1),初始时,:A(0,j,k),a,jk,0j,kn-1;,结束时,:C(0,j,k),为,A,+,的,(,j,k,),元素,-,算法描述,:,算法,15.1,Begin /,输入,:,A,nn,输出,:,C,nn,(1),加入单位阵,:Par-do,A(0,j,j),1,0jn-1,(2)A,复制给,B:Par-do,B(0,j,k),A(0,j,k),0j,kn-1,(3)for i=1 to do,(3.1)CAB /,调用,DNS,乘法算法,12.7,O(logn,),(3.2)par-do:,A(0,j,k),C(0,j,k),B(0,j,k),C(0,j,k),0j,kn-1,endfor,End /,t(n,)=O(log,2,n),p(n,)=n,3,c(n,)=O(n,3,log,2,n),2026/2/1 周日,Y.Xu Copyright USTC,主要内容,15.1,图的并行搜索,15.2,图的传递闭包,15.3,图的连通分量,15.4,图的最短路径,15.5,图的最小生成树,2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,15.3.1 SIMD-CC,模型上的连通分量法,-,基于传递闭包求解算法,15.3.2 SIMD-CREW,上的连通分量算法,-,基于顶点合并的求解算法,2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,15.3.1 SIMD-CC,模型上的连通分量法,1.,传递闭包求解算法原理,(1),用算法,15.1,求解,G,的传递闭包,即连通矩阵,C,(2),构造矩阵,D:,d,jk,=,v,k,当,c,jk,=1,时,0j,kn-1,0,其他,(3),由,D,计算出顶点,v,j,的分量号,2.,示例,:,P420,例,15.3,v,1,v,4,v,7,v,2,v,5,v,8,v,0,v,6,v,3,0 1 2 3 4 5 6 7 8,0 0 0 0,1,0 0,1,0,1,1 0 0 0 0,1,0 0,1,0,2 0 0 0 0 0,1,0 0 0,3,1,0 0 0 0 0 0 0 0,4 0,1,0 0 0 0 0 0 0,5 0 0,1,0 0 0 0 0 0,6,1,0 0 0 0 0 0 0 0,7 0,1,0 0 0 0 0 0 0,8,1,0 0 0 0 0 0 0 0,=G,2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,由,D,计算连通分量,=,连通分量,0:v,0,v,3,v,6,v,8,/,v,0,v,3,v,6,v,8,所在处理器并发写下标,/,取最小下标,连通分量,1:,v,1,v,4,v,7,连通分量,2:v,2,v,5,0 1 2 3 4 5 6 7 8,0,1,0 0,1,0 0,1,0,1,1 0,1,0 0,1,0 0,1,0,2 0 0,1,0 0,1,0 0 0,3,1,0 0,1,0 0,1,0,1,4 0,1,0 0,1,0 0,1,0,5 0 0,1,0 0,1,0 0 0,6,1,0 0,1,0 0,1,0,1,7 0,1,0 0 0 0 0,1,0,8,1,0 0,1,0 0,1,0,1,=C,0 1 2 3 4 5 6 7 8,0,v,0,0 0,v,3,0 0,v,6,0,v,8,1 0,v,1,0 0,v,4,0 0,v,7,0,2 0 0,v,2,0 0,v,5,0 0 0,3,v,0,0 0,v,3,0 0,v,6,0,v,8,4 0,v,1,0 0,v,4,0 0,v,7,0,5 0 0,v,2,0 0,v,5,0 0 0,6,v,0,0 0,v,3,0 0,v,6,0,v,8,7 0 v,1,0 0 v,4,0 0,v,7,0,8,v,0,0 0,v,3,0 0,v,6,0,v,8,=D,2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,3.SIMD-CC,上的算法,/,输入,:A(0,j,k),a,jk,0,j,k,n-1,/,输出,:C(0,j,0)v,j,的连通分量号,0,j,n-1,Begin,(1),调用算法,15.1,求出连通矩阵,C;/O(log,2,n),(2),构造矩阵,D;/O(1),(3)for all P(0,j,k)Par-do:,第,j,行处理器,P(0,j,k),将,v,k,的下标写入,C(0,j,0),并取最小顶点下标,;/,O(logn,),endfor,End,=,t(n,)=O(log,2,n),p(n,)=n,3,2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,15.3.2 SIMD-CREW,上的连通分量算法,1.,顶点合并的求解算法原理,初始时,:,给每个顶点一个标号,;,结束时,:,使处在相同连通分量中的不同顶点有相同的标号,该标号是所在,连通片顶点中最小标号,.,2.,示例,(1),求出每个顶点,i,的最小相邻顶点,c(i,),并指向最小相邻顶点,;,v,4,v,6,(a),v,9,v,8,v,7,v,5,v,1,v,3,v,2,v,1,v,2,v5,v,3,v,6,v,7,v,4,v,9,v,8,(b),2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,(2),用指针跳跃技术,逐步指向树根,(,连通片中标号最小的顶点,),形成星树,;,(3),每棵星树根作为超顶,超顶代表整棵星树,当两个超顶中有结点相邻时,则表示这两个超顶有连边,于是构成超图,;,(4),在超图中重复,(1)(3),直至超图成孤立超顶集,;,(5),将最终超图中顶点的标号返回给超顶所代表的所有顶点,.,v,1,v,5,v,2,v,3,v,6,v,7,v,4,v,9,v,8,(c),2026/2/1 周日,Y.Xu Copyright USTC,15.3,图的连通分量,3.SIMD-CREW,上的算法,-,算法描述：,P421,算法,15.4,(1),用,n,2,个处理器实现,;/,O(logn,),(2),用,n,个处理器,实现,;,/,O(logn,),(3),用,n,2,个处理器实现,;/,O(logn,),(4),重复,(1)(3),直至超图均为孤立点,;/,重复次数,logn,-,计算时间,t(n,)=O(log,2,n),p(n,)=n,2,-,如何实现？,(,思考题,),2026/2/1 周日,Y.Xu Copyright USTC,主要内容,15.1,图的并行搜索,15.2,图的传递闭包,15.3,图的连通分量,15.4,图的最短路径,15.5,图的最小生成树,2026/2/1 周日,Y.Xu Copyright USTC,15.4,图的最短路径,15.4.1,所有顶点对间的最短路径,1.,问题,:,有向图,G=(V,E),边权矩阵,W=(,w,ij,),nn,求最短路径长度矩阵,D=(,d,ij,),nn,假定图中无负权有向回路,.,2.,已有解法,:,Matrix Multiplication,Dijkstras,Floyds,3.,基于矩阵乘法的算法原理,记,d,(k),ij,为结点,i,到结点,j,至多有,k-1,个中间结点的最短路径长,(1)d,(1),ij,=,w,ij,ij,如果,i,j,之间无连边存在记为,0,(2),无负权有向回路,=,d,ij,=d,(n-1),ij,(3),应用最优性原理,:,d,(k),ij,=,min,l,=1n,d,(k/2),i,l,+d,(k/2),l,j,视,:“+”,“”,“min”,“”=,D,k,=D,k/2,D,k/2,(4),应用矩阵乘法,:,D,D,2,D,4,D,2,=,D,n,共有 次相乘,2026/2/1 周日,Y.Xu Copyright USTC,15.4,图的最短路径,3.SIMD-CC,上的并行算法,-,算法描述,:P429,算法,15.7,-,时间分析,:,每次矩阵乘时间,O(logn,),共作 次乘法t(n,)=O(log,2,n),p(n,)=n,3,4.,示例,2026/2/1 周日,Y.Xu Copyright USTC,15.4,图的最短路径,2026/2/1 周日,Y.Xu Copyright USTC,主要内容,15.1,图的并行搜索,15.2,图的传递闭包,15.3,图的连通分量,15.4,图的最短路径,15.5,图的最小生成树,2026/2/1 周日,Y.Xu Copyright USTC,15.5,图的最小生成树,15.5.1 SIMD-EREW,模型上的,MST,算法,1.Prim,算法,-,设顶点集,V=v,0,v,1,v,n-1,边权矩阵,W=(,w,ij,)nn,求,MST,令,c(v,i,),为,非树结点,v,i,与树上最近的结点,.,-,算法,:,(1),开始时,任取,v,0,作为初始树,c(v,i,)=v,0,i=1,n-1,(2),只要还有非树结点,做,:,(2.1),对所有不在树上的结点,v,i,取,v,j,使,w(v,j,c(v,j,),达到最小,将,v,j,与边,(,v,j,c(v,j,),加入树中,;,(2.2),对所有不在树上的结点,v,i,修改,c(v,i,),c(v,i,)=,c(v,i,),w(v,i,v,j,),w(v,i,c(v,j,),v,j,other,-,计算时间,:(1)O(n)(2),已有,k,个结点在树中t(n,)=O(n,2,),(2.1)n-k-1,次比较,;(2.1)n-k-1,次比较,2026/2/1 周日,Y.Xu Copyright USTC,15.5,图的最小生成树,2.SIMD-EREW,模型上的,MST,算法,-,数据划分,n/p,n,i,Processors,0,1,p-1,W,c0.n-1,i,0,1,p-1,2026/2/1 周日,Y.Xu Copyright USTC,15.5,图的最小生成树,2.SIMD-EREW,模型上的,MST,算法,-,设有,N,个处理器,P,0,P,1,P,N-1,1Nn,N=n,1-x,0 x(2),的时间,:O(n-1)(n,x,+logn)=,O(n(n,x,+logn,),取,n,x,logn,=N=n,1-x,t(n,)=O(n,1+x,),c(n,)=,t(n)p(n,)=O(n,2,)/,成本最优,2026/2/1 周日,Y.Xu Copyright USTC,End of Chapter 15,2026/2/1 周日,Y.Xu Copyright USTC,