分布式系统开发第六章并行算法的一般设计策略

1、1分布式系统开发第六章 并行算法的一般设计策略26.1 串行算法的直接并行化6.2 从问题描述开始设计并行算法6.3 借用已有算法求解新问题6.4 串行算法的直接并行化补充实例:八皇后问题和单源最短路径问题3设计并行算法一般有3种方法：（1）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；（2）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；（3）借助已有的并行算法求解新问题。 46.1 串行算法的直接并行化方法描述发掘和利用现有串行算法中的

2、并行性，直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；并非所有的串行算法都可以并行化；一个好的串行算法并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法 ；显著优点：无需考虑算法的稳定性、收敛性等复杂问题。5积分算法的直接并行化-的计算6计算的串行C代码#define N 1000000main() double local, pi = 0.0, w;long i;w=1.0/N;for (i = 0; iN; i +) local =

3、(i + 0.5)*w;pi = pi + 4.0/(1.0+local * local);printf(“pi is %f n”, pi *w);7k个处理器并行地计算部分和8计算的MPI代码 # define N 100000 main ( )，pi，w，temp=0.0； long i ，taskid，numtask； A：w=1.0/N； MPI_ Init(&argc，& argv)；/*MPI 初始化*/ MPI _Comm _rank (MPI_COMM_WORLD，&taskid)；/*每个处理器确定各自ID*/ MPI _Comm _Size (MPI_COMM_WORLD，

4、&numtask)；/*每个处理器确定总处理 器个数*/ B： for (i= taskid； iaj thenk=k+1 end ifend for(3)bk= aiend forEnd11枚举排序的并行算法对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。 12枚举排序并行算法输入：无序数组a1an输出：有序数组b1bnBegin(1)P0播送a1an给所有Pi(2)for all Pi where 1in para-do (2.1)k=1 (2.

5、2)for j = 1 to n doif (ai aj) or (ai = aj and ij) then k = k+1end if end for(3)P0收集k并按序定位End 步骤的时间复杂度为O（n）；步骤中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时中的通信复杂度为O（n2）；所以总的计算复杂度为O（n），总的通信复杂度为O（n2）。13快速排序（Quick Sort）快速排序（Quick Sort）是一种最基本的排序算法基本思想：在当前无序区R1,n中取一个记录作为比较的“基准”，用此基准将当前的无序区R1,n划分成左右两个无序的子区R1

6、,i-1和Ri,n(1in)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。快速排序算法的性能主要决定于输入数组的划分是否均衡，而这与基准元素的选择密切相关。在最坏情况下，划分的结果是一边有n-1个元素，而另一边有0个元素。如果每次递归排序中的划分都产生这种极度的不平衡，那么整个算法的复杂度将是（n2）。在最好的情况下，每次划分都使得输入数组平均分为两半，那么算法的复杂度为O（nlogn）。在一般的情况下该算法仍能保持O（nlogn）的复杂度，只不过其具有更高的常数因子。 14 快速排序算法的串行实现SISD上的快排序算法 输

7、入：无序序列(Aq,Ar) 输出：有序序列(Aq,Ar) Procedure QUICKSORT（A, q, r） Begin if q 8 then OutputResult(chessboard)/* 结束递归并输出结果 */ elsefor col = 1 to 8 do/* 判断是否有列、对角线或反对角线冲突 */（1）no_collision = true（2）i = 1（3）while no_collision and i 0 do （）从某个从进程i接收信号signal （）if signal = Accomplished then 从从进程i接收并记录解 end if （）if

8、 has_more_boards then ()向从进程i发送NewTask信号 ()向从进程i发送一个新棋盘 else ()向从进程i发送Terminate信号 ()active_slaves = active_slaves - 1 end if end whileEnd /* EightQueensMaster */36从进程算法procedure EightQueenSlaveBegin（1）向主进程发送Ready信号（2）finished = false（3）while not finished do （）从主进程接收信号signal （）if signal = NewTask the

9、n ()从主进程接收新棋盘 ()if 新棋盘合法 then 在新棋盘的基础上找出所有合法的解，并将解发送 给主进程 end if else /* signal = Terminate */finished = true end ifend whileEnd /* EightQueenSlave */37附2：单源最短路径问题单源最短路径(Single Source Shortest Path)问题是指求从一个指定顶点s到其它所有顶点i之间的距离，因为是单一顶点到其它顶点的距离，所以称为单源。设图G(V,E)是一个有向加权网络，其中V和E分别为顶点集合和边集合，其边权邻接矩阵为W，边上权值w(i

10、,j) 0，i,jV，V=0,1,N-1。设dist( i )为最短的路径长度，即距离，其中sV且is。这里采用著名的Dijkstra算法，并将其并行化。38最短路径问题用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图中的边是否有路可达另一顶点？若有多条路径可达，则在所经过的路径中，各边上权值之和最小的一条路径最短路径。这就是路由选择。如：邮政自动分拣机的路选装置、计算机网络中的路由选择等。问题提出39单源最短路径：指的是对已知图G=(V,E)，给定源点sV，找出s到图中其它各顶点的最短路径。每

11、对结点间的最短路径指的是对已知图G=(V,E)，任意的顶点Vi,Vj V，找出从Vi到Vj的最短路径。两种最常见的最短路径算法：求单源最短路径的迪杰斯特拉（Djikstra）算法和求所有顶点之间的最短路径的弗洛伊德（Floyd）算法。40单源最短路径问题：给定带权有向图G=(V,E)，求从某个给定的源点v0V到其余各顶点的最短路径。迪杰斯特拉算法 41024170535010353031520101520源点终点最短路径路径长度01（0,2,3,1）452（0,2）103（0,2,3）254（0,2,3,1,4）555(a) 带权的有向图G(b) 图G顶点0的单源最短路径迪杰斯特拉算法按从源点

12、到其他各顶点的最短路径长度的从小到大的次序逐一产生最短路径。42把V分成两组：（1）S：存放已求得最短路径的顶点的集合（2）T=V-S：尚未确定最短路径的顶点集合将T中顶点按最短路径非递减的次序加入到S中。迪杰斯特拉（Dijkstra）算法思想：这个过程中，总保持： 从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。而且每个顶点对应一个距离值：S中顶点对应的距离值，是从V0到此顶点的最短路径长度；T中顶点对应的距离值，是从V0到此顶点的只包括S中顶点作中间顶点的当前最短路径长度。43单源最短路径图例求上图中源点0到其他各顶点的最短路径100241705350103

13、53031520101520507044单源最短路径图例求上图中源点0到其他各顶点的最短路径0241705350103530315201015201050257045单源最短路径图例求上图中源点0到其他各顶点的最短路径0241705350103530315201015201045256046单源最短路径图例求上图中源点0到其他各顶点的最短路径0241705350103530315201015201045255547单源最短路径图例求上图中源点0到其他各顶点的最短路径0241705350103530315201015201045255548单源最短路径图例求上图中源点0到其他各顶点的最短路径02

14、41705350103530315201015201045255549迪杰斯特拉算法求单源最短路径步骤：首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有顶点之间的最短路径都已求得为止。初始状态下集合S中只有源点v0，即： S=v0，T=其余顶点。T中顶点vi对应的当前最短路径长度： 若存在，为弧上的权值w(v0,vi) 若不存在 ，为50从T中选取一个当前最短路径长度最小的顶点vk加入S。对T中剩余顶点vi的当前最短路径长度进行修改：若加进vk作中间顶点，从v0到vi的距离值比不加vk的路径要短，则修改此距离值。重复上述步骤，按照当前最短路径长度的非

15、减次序产生下一条最短路径，并将该路径的终点tT加入S中，并更新T中剩余顶点的当前最短路径长度。直到SV时（即从源点v0到其他所有结点之间的最短路径都已求得为止），算法结束。51选择数据结构 一维数组d di中存放从源点v0到vi的当前最短路径长度，该路径上除顶点vi自身外，其余顶点都属于S，并且是所有这些路径中的最短者。 一维整型数组path pathi给出从v0到顶点vi的最短路径上，位于顶点vi前面的那个顶点。例如：从v0到v1的最短路径为（v0,v2,v3,v1）则有path1=3，path3=2，path2=0一维布尔数组s 若si为true，表示顶点vi在S中；否则表示vi在V-S中

16、。52Sd0path0d1path1d2path2d3path3d4path4d5path500，-1 初始状态S=v0，T=其余顶点。024170535010353031520101520源点v0到自身的路径长度为0，路径上0前面的顶点不存在因此为-1。初始状态下T中顶点vi对应的当前最短路径长度di和该路径上i前面的结点pathi值为：若存在，则di为弧上的权值w(v0,vi) ，且pathi=0；若不存在 ，则di为，且pathi=-1。50，0 10，0 ，-1 70，0 ，-1053第一条最短路径是T=V-v0集合中所有顶点的当前最短路径中最短者： 求第一条最短路径Sd0path0d

17、1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-1024170535010353031520101520选择顶点v2加入集合S，则d2为源点v0到顶点v2的最短路径，path2为该最短路径上顶点v2前面的那个顶点v0 。0254024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-1顶点vk加入S后，对所有T=V-S集合中的剩余顶点vi ，按公式修正从

18、源点v0到该顶点的当前最短路径长度：更新d和path若di值被更新，则pathi值也随之更新为k。0255重复下面步骤：（1）按照非减次序选择下一条最短路径的终点（T=V-S中具有最短的当前最短路径长度的顶点vk），满足：直到SV时算法结束。（2） vk加入S集合中后，修正T中剩余顶点vi的当前最短路径长度di和pathi值：若di更新，则pathi也相应的更新为k56024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270

19、，0，-1选择顶点v3加入S。则d3为源点v0到顶点v3的最短路径， path3为最短路径上顶点v3前面的那个顶点。02357024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-102358024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-

20、170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10231将顶点v1加入S。则d1为源点v0到顶点v1的最短路径， path1为最短路径上顶点v1前面的那个顶点。59024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-1023

21、160024170535010353031520101520Sd0path0d1path1d2path2d3path3d4path4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-10231选择顶点v4加入S。则d4为源点v0到顶点v4的最短路径， path4为最短路径上顶点v4前面的那个顶点。461024170535010353031520101520Sd0path0d1path1d2path2d3path3d4pa

22、th4d5path500，-150，010，0，-170，0，-10,20，-150，010，025，270，0，-10,2,30，-145，310，025，260，3，-10,2,3,10，-145，310，025，255，1，-10,2,3,1,40，-145，310，025，255，1，-10214362Dijkstra算法(Dijkstra Algorithm) Dijkstra算法(Dijkstra Algorithm)是单源最短路径问题的经典解法之一，基本思想如下：假定有一个待搜索的顶点表VL，初始化时做： dist(s)0，dist(i)=(is)，VL=V。每次从VL（非空集）中选取这样的一个顶点u，它的dist(u)最小。将选出的u点作为搜索顶点，对于其它还在VL内的顶点v，若E,而且dist(u)+w(u,v)dist(v)，则