《并行计算多媒体课件并行算法设计与分析ch15GraphAlgorithms》由会员分享，可在线阅读，更多相关《并行计算多媒体课件并行算法设计与分析ch15GraphAlgorithms（32页珍藏版）》请在金锄头文库上搜索。
1、Parallel Algorithms1 / Ch15 Parallel Algorithms Chapter 15 Graph Algorithms2024/9/6Y.Xu Copyright USTCParallel Algorithms2 / Ch15主要内容主要内容n15.1 图的并行搜索图的并行搜索 n15.2 图的传递闭包图的传递闭包n15.3 图的连通分量图的连通分量n15.4 图的最短路径图的最短路径n15.5 图的最小生成树图的最小生成树 2024/9/6Y.Xu Copyright USTCParallel Algorithms3 / Ch1515.1 图的并行搜索图的并行
2、搜索15.1.1 算法原理算法原理1.并行搜索的一般方法并行搜索的一般方法 (1)建立一个主表和建立一个主表和p个子表个子表; (2)开始时主表空开始时主表空, 任取一个顶点作为待搜索顶点任取一个顶点作为待搜索顶点, 并置入主表并置入主表; (3)p个处理器分别搜索与该顶点相邻的边个处理器分别搜索与该顶点相邻的边, 将搜索到的顶点加入子表将搜索到的顶点加入子表; (4)以一定的策略以一定的策略, 将子表链到主表将子表链到主表, 并从主表中任取一个作为待搜索顶点并从主表中任取一个作为待搜索顶点; (5)重复重复(3)、(4)直至所有的顶点加入到主表直至所有的顶点加入到主表.2.串行搜索的上界串行
3、搜索的上界 设搜索、加入顶点及表链接需要一个单位时间设搜索、加入顶点及表链接需要一个单位时间, 则则 Tsi=1n(di+1)=2m+n di为顶点为顶点vi的度的度 注注: 因为每个待搜索顶点因为每个待搜索顶点vi需要检查需要检查di条邻接边条邻接边, 需要搜索需要搜索di次次; 每个顶点每个顶点 只可能加入一次只可能加入一次. 2024/9/6Y.Xu Copyright USTCParallel Algorithms4 / Ch1515.1 图的并行搜索图的并行搜索3.三种并行搜索示例三种并行搜索示例 (1)p-深度优先搜索深度优先搜索 798265134(a) 图G214378695(
4、1)(1)(7)(2)(2)(6)(3)(3)(4)(5)(b) 两个处理器的p-深度优先搜索2024/9/6Y.Xu Copyright USTCParallel Algorithms5 / Ch1515.1 图的并行搜索图的并行搜索 (2)p-宽深优先搜索宽深优先搜索 798265134(a) 图G215378694(1)(2)(2)(3)(4)(5)(1)(3)(6)(c) 两个处理器的p-宽深优先搜索(5)2024/9/6Y.Xu Copyright USTCParallel Algorithms6 / Ch1515.1 图的并行搜索图的并行搜索 (3)p-宽度优先搜索宽度优先搜索 7
5、98265134(a) 图G215378694(1)(2)(2)(3)(4)(6)(1)(3)(6)(d) 两个处理器的p-宽度优先搜索(5)2024/9/6Y.Xu Copyright USTCParallel Algorithms7 / Ch1515.1 图的并行搜索图的并行搜索15.1.2 p-深度优先搜索深度优先搜索 1.算法描述算法描述 (1)主表为栈主表为栈, 任取一个顶点置入主表任取一个顶点置入主表; (2)对栈顶元素开始搜索对栈顶元素开始搜索, p个处理器搜索一次个处理器搜索一次, 将子表链接将子表链接 到主表到主表; (3)某顶点的边搜索完某顶点的边搜索完, 从主表中删除从主
6、表中删除; (4)重复重复(2),(3)直至主表为空直至主表为空. 2.计算时间计算时间 搜索与顶点搜索与顶点i相邻所有边的次数相邻所有边的次数 p个元素链接成一个子表的时间个元素链接成一个子表的时间 2024/9/6Y.Xu Copyright USTCParallel Algorithms8 / Ch1515.1 图的并行搜索图的并行搜索15.1.2 p-宽深优先搜索宽深优先搜索 1.算法描述算法描述 (1)主表为栈主表为栈, 任取一个顶点置入主表任取一个顶点置入主表; (2)对栈顶元素开始搜索对栈顶元素开始搜索, p个处理器搜索完所有的邻边个处理器搜索完所有的邻边, 再将再将 子表链接到
7、主表子表链接到主表; (3)某顶点的边搜索完某顶点的边搜索完, 从主表中删除从主表中删除; (4)重复重复(2),(3)直至主表为空直至主表为空. 2.计算时间计算时间 搜索与顶点搜索与顶点i相邻所有边的次数相邻所有边的次数 将将p个子表链接起来的时间个子表链接起来的时间 2024/9/6Y.Xu Copyright USTCParallel Algorithms9 / Ch1515.1 图的并行搜索图的并行搜索15.1.2 p-宽度优先搜索宽度优先搜索 1.算法描述算法描述 (1)主表为主表为FIFO队列队列, 任取一个顶点置入主表任取一个顶点置入主表; (2)对队头元素开始搜索对队头元素开
8、始搜索,并从主表中删除并从主表中删除; p个处理器搜索完个处理器搜索完 所有的邻边所有的邻边; (3)将子表链接起来将子表链接起来, 并入主表中并入主表中; (4)重复重复(2),(3)直至主表和子表皆为空直至主表和子表皆为空. 2.计算时间计算时间 宽度搜索的最大层数宽度搜索的最大层数 2024/9/6Y.Xu Copyright USTCParallel Algorithms10 / Ch15主要内容主要内容n15.1 图的并行搜索图的并行搜索 n15.2 图的传递闭包图的传递闭包n15.3 图的连通分量图的连通分量n15.4 图的最短路径图的最短路径n15.5 图的最小生成树图的最小生成
9、树 2024/9/6Y.Xu Copyright USTCParallel Algorithms11 / Ch1515.2 图的传递闭包图的传递闭包15.2.1 传递闭包传递闭包 1.定义定义 有向图有向图G=(V,E), A=(aij)nn为邻接矩阵为邻接矩阵, A的传递闭包的传递闭包A+=(bij)nn, bij为为1时当且仅当顶点时当且仅当顶点i到顶点到顶点j之间有一条路径之间有一条路径, 这里这里 2.串行算法串行算法: O(n3) 1432(a) 1 1 1 11 1 1 11 1 1 11 1 1 1(b) 2024/9/6Y.Xu Copyright USTCParallel A
10、lgorithms12 / Ch1515.2 图的传递闭包图的传递闭包3.基于布尔矩阵乘积的算法原理基于布尔矩阵乘积的算法原理 令令B=A+I, I为单位阵为单位阵, B=(b(1)ij)nn 则有则有, b(1)ij=1 i=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 ij有长度有长度2的有向路径的有向路径. 类似地类似地, Bk=(b(k)ij)nn, b(k)ij=1 ij有长度有长度k的有向路径的有向
11、路径. 因此因此, A+=Br (rn-1) 所以所以, BB2B4B2 =A+, 共有共有 次相乘次相乘2024/9/6Y.Xu Copyright USTCParallel Algorithms13 / Ch1515.2 图的传递闭包图的传递闭包4.计算示例计算示例 1432(a) 1 1 0 00 1 1 00 0 1 11 0 0 1(b) B=A+I= 1 1 1 00 1 1 11 0 1 11 1 0 1(c) B2= 1 1 1 11 1 1 11 1 1 11 1 1 1(d) B4= =A+ 2024/9/6Y.Xu Copyright USTCParallel Algor
12、ithms14 / Ch1515.2 图的传递闭包图的传递闭包5.SIMD-CC上的传递闭包算法上的传递闭包算法 - n3个处理器排成个处理器排成nnn的三维阵列的三维阵列, Pr坐标为坐标为(i,j,k), 有三个寄存器有三个寄存器A(i,j,k), B(i,j,k)和和C(i,j,k), 其中其中r=in2+jn+k, (0i,j,kn-1) 初始时初始时: A(0,j,k)ajk 0j,kn-1; 结束时结束时: C(0,j,k)为为A+的的(j,k)元素元素 - 算法描述算法描述: 算法算法15.1 Begin /输入输入:Ann, 输出输出:Cnn (1)加入单位阵加入单位阵: Pa
13、r-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(log2n), p(n)=n3, c(n)=O(n3log2n) 2024/9/6Y.Xu Copyright USTCParallel Algorithms15 / Ch15主要内容主要内容
14、n15.1 图的并行搜索图的并行搜索 n15.2 图的传递闭包图的传递闭包n15.3 图的连通分量图的连通分量n15.4 图的最短路径图的最短路径n15.5 图的最小生成树图的最小生成树 2024/9/6Y.Xu Copyright USTCParallel Algorithms16 / Ch1515.3 图的连通分量图的连通分量15.3.1 SIMD-CC模型上的连通分量法模型上的连通分量法 - 基于传递闭包求解算法基于传递闭包求解算法15.3.2 SIMD-CREW上的连通分量算法上的连通分量算法 - 基于顶点合并的求解算法基于顶点合并的求解算法2024/9/6Y.Xu Copyright
15、 USTCParallel Algorithms17 / Ch1515.3 图的连通分量图的连通分量15.3.1 SIMD-CC模型上的连通分量法模型上的连通分量法 1.传递闭包求解算法原理传递闭包求解算法原理 (1)用算法用算法15.1求解求解G的传递闭包的传递闭包, 即连通矩阵即连通矩阵C (2)构造矩阵构造矩阵D: djk= vk 当当cjk=1时时 0j,kn-1 0 其他其他 (3)由由D计算出顶点计算出顶点vj的分量号的分量号 2.示例示例:P420例例15.3v1v4v7v2v5v8v0v6v3 0 1 2 3 4 5 6 7 8 0 0 0 0 1 0 0 1 0 11 0 0
16、 0 0 1 0 0 1 02 0 0 0 0 0 1 0 0 03 1 0 0 0 0 0 0 0 04 0 1 0 0 0 0 0 0 05 0 0 1 0 0 0 0 0 06 1 0 0 0 0 0 0 0 07 0 1 0 0 0 0 0 0 08 1 0 0 0 0 0 0 0 0= G2024/9/6Y.Xu Copyright USTCParallel Algorithms18 / Ch1515.3 图的连通分量图的连通分量 由由D计算连通分量计算连通分量= 连通分量连通分量0: v0,v3,v6,v8 /v0,v3,v6,v8所在处理器并发写下标所在处理器并发写下标, /取最
17、小下标取最小下标 连通分量连通分量1: v1,v4,v7 连通分量连通分量2: v2,v5 0 1 2 3 4 5 6 7 8 0 1 0 0 1 0 0 1 0 11 0 1 0 0 1 0 0 1 02 0 0 1 0 0 1 0 0 03 1 0 0 1 0 0 1 0 14 0 1 0 0 1 0 0 1 05 0 0 1 0 0 1 0 0 06 1 0 0 1 0 0 1 0 17 0 1 0 0 0 0 0 1 08 1 0 0 1 0 0 1 0 1= C 0 1 2 3 4 5 6 7 8 0 v0 0 0 v3 0 0 v6 0 v81 0 v1 0 0 v4 0 0 v7
18、 02 0 0 v2 0 0 v5 0 0 03 v0 0 0 v3 0 0 v6 0 v84 0 v1 0 0 v4 0 0 v7 05 0 0 v2 0 0 v5 0 0 06 v0 0 0 v3 0 0 v6 0 v87 0 v1 0 0 v4 0 0 v7 08 v0 0 0 v3 0 0 v6 0 v8= D2024/9/6Y.Xu Copyright USTCParallel Algorithms19 / Ch1515.3 图的连通分量图的连通分量 3.SIMD-CC上的算法上的算法 /输入输入: A(0,j,k)ajk, 0j,kn-1 /输出输出: C(0,j,0)vj的连通分
19、量号的连通分量号, 0jn-1 Begin (1)调用算法调用算法15.1, 求出连通矩阵求出连通矩阵C; /O(log2n) (2)构造矩阵构造矩阵D; /O(1) (3)for all P(0,j,k) Par-do: 第第j行处理器行处理器P(0,j,k)将将vk的下标写入的下标写入C(0,j,0), 并取最小顶点下标并取最小顶点下标; /O(logn) endfor End = t(n)= O(log2n), p(n)=n3 2024/9/6Y.Xu Copyright USTCParallel Algorithms20 / Ch1515.3 图的连通分量图的连通分量15.3.2 SI
20、MD-CREW上的连通分量算法上的连通分量算法 1.顶点合并的求解算法原理顶点合并的求解算法原理 初始时初始时: 给每个顶点一个标号给每个顶点一个标号; 结束时结束时: 使处在相同连通分量中的不同顶点有相同的标号使处在相同连通分量中的不同顶点有相同的标号, 该标号是所在该标号是所在 连通片顶点中最小标号连通片顶点中最小标号. 2.示例示例 (1)求出每个顶点求出每个顶点i的最小相邻顶点的最小相邻顶点c(i), 并指向最小相邻顶点并指向最小相邻顶点;v4v6(a)v9v8v7v5v1v3v2v1v2v5v3v6v7v4v9v8(b)2024/9/6Y.Xu Copyright USTCParal
21、lel Algorithms21 / Ch1515.3 图的连通分量图的连通分量(2)用指针跳跃技术用指针跳跃技术, 逐步指向树根逐步指向树根(连通片中标号最小的顶点连通片中标号最小的顶点), 形成星树形成星树;(3)每棵星树根作为超顶每棵星树根作为超顶, 超顶代表整棵星树超顶代表整棵星树, 当两个超顶中有结点相邻时当两个超顶中有结点相邻时, 则表示这两个超顶有连边则表示这两个超顶有连边, 于是构成超图于是构成超图;(4)在超图中重复在超图中重复(1)(3), 直至超图成孤立超顶集直至超图成孤立超顶集;(5)将最终超图中顶点的标号返回给超顶所代表的所有顶点将最终超图中顶点的标号返回给超顶所代表
22、的所有顶点.v1v5v2v3v6v7v4v9v8(c)2024/9/6Y.Xu Copyright USTCParallel Algorithms22 / Ch1515.3 图的连通分量图的连通分量3.SIMD-CREW上的算法上的算法 - 算法描述：算法描述：P421 算法算法15.4 (1)用用n2个处理器实现个处理器实现; /O(logn) (2)用用n个处理器个处理器实现实现; /O(logn) (3)用用n2个处理器实现个处理器实现; /O(logn) (4)重复重复(1)(3)直至超图均为孤立点直至超图均为孤立点; /重复次数重复次数logn - 计算时间计算时间 t(n)=O(l
23、og2n), p(n)=n2 - 如何实现？如何实现？( (思考题思考题) )2024/9/6Y.Xu Copyright USTCParallel Algorithms23 / Ch15主要内容主要内容n15.1 图的并行搜索图的并行搜索 n15.2 图的传递闭包图的传递闭包n15.3 图的连通分量图的连通分量n15.4 图的最短路径图的最短路径n15.5 图的最小生成树图的最小生成树 2024/9/6Y.Xu Copyright USTCParallel Algorithms24 / Ch1515.4 图的最短路径图的最短路径15.4.1 所有顶点对间的最短路径所有顶点对间的最短路径 1.
24、问题问题:有向图有向图G=(V,E), 边权矩阵边权矩阵W=(wij)nn, 求最短路径长度矩阵求最短路径长度矩阵 D=(dij)nn, 假定图中无负权有向回路假定图中无负权有向回路. 2.已有解法已有解法: Matrix Multiplication, Dijkstras, Floyds 3.基于矩阵乘法的算法原理基于矩阵乘法的算法原理 记记d(k)ij为结点为结点i到结点到结点j至多有至多有k-1个中间结点的最短路径长个中间结点的最短路径长 (1) d(1)ij= wij ij, 如果如果i,j之间无连边存在记为之间无连边存在记为 0 (2)无负权有向回路无负权有向回路 = dij= d(
25、n-1)ij (3)应用最优性原理应用最优性原理: d(k)ij=minl=1nd(k/2)il + d(k/2)lj 视视:“+”“”,“min”“”=Dk=Dk/2Dk/2 (4)应用矩阵乘法应用矩阵乘法: DD2D4D2 =Dn, 共有共有 次相乘次相乘2024/9/6Y.Xu Copyright USTCParallel Algorithms25 / Ch1515.4 图的最短路径图的最短路径3.SIMD-CC上的并行算法上的并行算法 - 算法描述算法描述: P429算法算法15.7 - 时间分析时间分析: 每次矩阵乘时间每次矩阵乘时间O(logn), 共作共作 次乘法次乘法 = t(
26、n)=O(log2n), p(n)=n34.示例示例2024/9/6Y.Xu Copyright USTCParallel Algorithms26 / Ch1515.4 图的最短路径图的最短路径 2024/9/6Y.Xu Copyright USTCParallel Algorithms27 / Ch15主要内容主要内容n15.1 图的并行搜索图的并行搜索 n15.2 图的传递闭包图的传递闭包n15.3 图的连通分量图的连通分量n15.4 图的最短路径图的最短路径n15.5 图的最小生成树图的最小生成树 2024/9/6Y.Xu Copyright USTCParallel Algorith
27、ms28 / Ch1515.5 图的最小生成树图的最小生成树15.5.1 SIMD-EREW模型上的模型上的MST算法算法 1.Prim算法算法 - 设顶点集设顶点集V=v0,v1,vn-1, 边权矩阵边权矩阵W=(wij)nn, 求求MST, 令令c(vi)为为 非树结点非树结点vi与树上最近的结点与树上最近的结点. - 算法算法: (1)开始时开始时, 任取任取v0 作为初始树作为初始树, c(vi)=v0, i=1,n-1 (2)只要还有非树结点只要还有非树结点, 做做: (2.1)对所有不在树上的结点对所有不在树上的结点vi, 取取vj使使w(vj,c(vj)达到最小达到最小, 将将v
28、j与边与边 (vj, c(vj)加入树中加入树中; (2.2)对所有不在树上的结点对所有不在树上的结点vi, 修改修改c(vi) c(vi)= c(vi) w(vi,vj)w(vi,c(vj) vj other - 计算时间计算时间: (1)O(n) (2)已有已有k个结点在树中个结点在树中 t(n)=O(n2) (2.1)n-k-1次比较次比较;(2.1)n-k-1次比较次比较2024/9/6Y.Xu Copyright USTCParallel Algorithms29 / Ch1515.5 图的最小生成树图的最小生成树2.SIMD-EREW模型上的模型上的MST算法算法 - 数据划分数据
29、划分n/p niProcessors01p-1Wc0.n-1i01p-12024/9/6Y.Xu Copyright USTCParallel Algorithms30 / Ch1515.5 图的最小生成树图的最小生成树2.SIMD-EREW模型上的模型上的MST算法算法 - 设有设有N个处理器个处理器P0,P1,PN-1, 1Nn, N=n1-x, 0x(2)的时间的时间: O(n-1)(nx+logn)=O(n(nx+logn) 取取nxlogn = N=n1-x t(n)=O(n1+x) c(n)=t(n)p(n)=O(n2) /成本最优成本最优2024/9/6Y.Xu Copyright USTCParallel Algorithms32 / Ch15End of Chapter 152024/9/6Y.Xu Copyright USTC
