所有结点对间的最短路径-课件.pptVIP

国防科学技术大学并行与分布处理重点实验室 国防科学技术大学并行与分布处理重点实验室 * * 所有结点对间的最短路径 给定一个带权图G=(V,E,?)，所有结点对间的最短路径问题就是寻找所有i?j的vi与vj之间的最短路径 对一个具有n个结点的图，所有结点对间的最短路径的长度可以用一个n×n的矩阵D来表示，其中dk,j表示结点vk与结点vj之间最短路径的长度 串行Dijkstra算法的复杂性为?(n3) * * 基于源结点划分的并行Dijkstra算法 适用条件：结点数n不小于进程数p 每个进程分配到n/p个结点，并分别求解从这些结点中每一个出发的单源最短路径问题 如果邻接矩阵在每个进程上都有副本，则无任何通信开销，并行执行时间为?(n3/p)，并行效率为?(1) * * 基于源结点并行计算的Dijkstra算法 适用条件：结点数n小于进程数p p个进程分为n组，每组p/n个进程，每个单源最短路径问题由一组进程进行求解 不妨假设p为n的倍数，则每个单源最短路径问题在p/n个进程上并行求解，所以并行执行时间为 Tp = ?(n2/(p/n)) + ?(n log (p/n)) 源结点并行计算方法可以有效利用到?(n2/logn)个进程，且等效率函数为?(p1.5log1.5p) * * Floyd算法 对任何两个结点vi与vj，如果记所有中间结点都属于{v1, v2, …, vk}的最短路径为pi,j,k，且记其长度为di,j,k，则di,j＝di,j,n且 * * Floyd算法(续) Floyd_All_Pairs_SP(A, n) for(i:=1; i=n; i++) { for(j:=1; j=n; j++) di,j,0 := ai,j; } for(k:=1; k=n; k++) { for(i:=1; i=n; i++) for(j:=1; j=n; j++) di,j,k := min(di,j,k-1, di,k,k-1+ dk,j,k-1); } * * Floyd算法(续) 二维块调度下的Floyd算法 * * Floyd算法(续) 二维块调度下的Floyd算法 * * Floyd算法(续) 在二维块划分下，Floyd算法一共需要n步 每一步的通信时间为?(n/p1/2logp) 每一步的并行计算时间为?(n2/p) 并行执行时间为 Tp = ?(n3/p) + ?(n2/p1/2log p)) 在直到O(n2/log2n)个进程上算法仍然是渐进最优的，且等效率函数为W=?(p1.5log3p) * * Floyd算法(续) 二维块划分下的流水线模式并行算法 当拥有第k行元素的进程Pi,j完成第k-1次迭代之后，就将Dk-1中的相应元素传给Pi-1,j与Pi+1,j 当拥有第k列元素的进程Pi,j完成第k-1次迭代之后，就将Dk-1中的相应元素传给Pi,j-1与Pi,j+1 当一个进程接收到相应的元素之后，就将其继续沿与接收数据时源进程所在方向相反的方向往前传送，直到到达边界位置 * * Floyd算法(续) 二维块调度 * * Floyd算法(续) 二维块划分下的流水线模式并行算法 第一行的n/p1/2个元素从P0,j出发往下传，第一列的n/p1/2个元素从Pi,0往右传。在p1/2步后，这些元素到达边界，所用的时间为?(n) 后续每次迭代对应的元素每隔?(n2/p)时间收到，从而进程右下角的进程在?(n3/p)＋?(n)时间内完成了其上的整个执行过程 第n行的n/p1/2个元素从最下层进程往上传，第n列的n/p1/2个元素从最右边进程往左传。在p1/2步后，这些元素到达边界，所用的时间为?(n) 国防科学技术大学并行与分布处理重点实验室 国防科学技术大学并行与分布处理重点实验室