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

《并行计算-多媒体课件-并行算法设计与分析-ch15_Graph_Algorithms.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ParallelAlgorithmsChapter15GraphAlgorithms2021/7/25Y.XuCopyrightUSTC主要内容15.1图的并行搜索15.2图的传递闭包15.3图的连通分量15.4图的最短路径15.5图的最小生成树2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索15.1.1算法原理1.并行搜索的一般方法(1)建立一个主表和p个子表;(2)开始时主表空,任取一个顶点作为待搜索顶点,并置入主表;(3)p个处理器分别搜索与该顶点相邻的边,将搜索到的顶点加入子表;(4)以一定的策略,将子表链到主表,并从主表中任取一个作为待搜索顶点;(5)重

2、复(3)、(4)直至所有的顶点加入到主表.2.串行搜索的上界设搜索、加入顶点及表链接需要一个单位时间,则Ts≤∑i=1~n(di+1)=2m+ndi为顶点vi的度注:因为每个待搜索顶点vi需要检查di条邻接边,需要搜索di次;每个顶点只可能加入一次.2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索3.三种并行搜索示例(1)p-深度优先搜索798265134(a)图G214378695(1)(1)(7)(2)(2)(6)(3)(3)(4)(5)(b)两个处理器的p-深度优先搜索2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索(2)p-宽深优先

3、搜索798265134(a)图G215378694(1)(2)(2)(3)(4)(5)(1)(3)(6)(c)两个处理器的p-宽深优先搜索(5)2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索(3)p-宽度优先搜索798265134(a)图G215378694(1)(2)(2)(3)(4)(6)(1)(3)(6)(d)两个处理器的p-宽度优先搜索(5)2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索15.1.2p-深度优先搜索1.算法描述(1)主表为栈,任取一个顶点置入主表;(2)对栈顶元素开始搜索,p个处理器搜索一次,将子表链接到主表;(

4、3)某顶点的边搜索完,从主表中删除;(4)重复(2),(3)直至主表为空.2.计算时间搜索与顶点i相邻所有边的次数p个元素链接成一个子表的时间2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索15.1.2p-宽深优先搜索1.算法描述(1)主表为栈,任取一个顶点置入主表;(2)对栈顶元素开始搜索,p个处理器搜索完所有的邻边,再将子表链接到主表;(3)某顶点的边搜索完,从主表中删除;(4)重复(2),(3)直至主表为空.2.计算时间搜索与顶点i相邻所有边的次数将p个子表链接起来的时间2021/7/25Y.XuCopyrightUSTC15.1图的并行搜索15.1.2p-

5、宽度优先搜索1.算法描述(1)主表为FIFO队列,任取一个顶点置入主表;(2)对队头元素开始搜索,并从主表中删除;p个处理器搜索完所有的邻边;(3)将子表链接起来,并入主表中;(4)重复(2),(3)直至主表和子表皆为空.2.计算时间宽度搜索的最大层数2021/7/25Y.XuCopyrightUSTC主要内容15.1图的并行搜索15.2图的传递闭包15.3图的连通分量15.4图的最短路径15.5图的最小生成树2021/7/25Y.XuCopyrightUSTC15.2图的传递闭包15.2.1传递闭包1.定义有向图G=(V,E),A=(aij)n×n为邻接矩阵,A的传递闭包A+=(bij

6、)n×n,bij为1时当且仅当顶点i到顶点j之间有一条路径,这里2.串行算法:O(n3)1432(a)1111111111111111(b)2021/7/25Y.XuCopyrightUSTC15.2图的传递闭包3.基于布尔矩阵乘积的算法原理令B=A+I,I为单位阵,B=(b(1)ij)n×n则有,b(1)ij=1i=j或ij有有向边ij有长为0或1的有向路径对于B2=(A+I)2=(b(2)ij)n×n,b(2)ij=∨k=1~nb(1)ikb(1)kj,这里∨为逻辑或则有,b(2)ij=1ij有长度≤2的有向路径.类似地,Bk=(b(k)ij)n×n,b(k)ij=1i

7、j有长度≤k的有向路径.因此,A+=Br(r≥n-1)所以,BB2B4…B2=A+,共有次相乘2021/7/25Y.XuCopyrightUSTC15.2图的传递闭包4.计算示例1432(a)1100011000111001(b)B=A+I=1110011110111101(c)B2=1111111111111111(d)B4==A+2021/7/25Y.XuCopyrightUSTC15.2图的传递闭包5.SIMD-CC