精简版第6章并行算法的一般设计策略.ppt
《精简版第6章并行算法的一般设计策略.ppt》由会员分享,可在线阅读,更多相关《精简版第6章并行算法的一般设计策略.ppt(56页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、分布式系统Distributed System计算机学院软件工程系计算机学院软件工程系主讲:陈主讲:陈 蕾蕾E-mail:1第六章第六章 并行算法的一般设计策略并行算法的一般设计策略6.1 串行算法的直接并行化串行算法的直接并行化6.2 从问题描述开始设计并行算法从问题描述开始设计并行算法6.3 借用已有算法求解新问题借用已有算法求解新问题6.4 串行算法的直接并行化补充实例串行算法的直接并行化补充实例:八皇后八皇后问题和单源最短路径问题问题和单源最短路径问题2设计并行算法一般有设计并行算法一般有3种方法:种方法:(1)检查和开拓现有串行算法中固有的并行性,直)检查和开拓现有串行算法中固有的并
2、行性,直接将其并行化,该方法并不是对所有问题总是可行的,但接将其并行化,该方法并不是对所有问题总是可行的,但对很多应用问题仍不失为一种有效的方法;对很多应用问题仍不失为一种有效的方法;(2)从问题本身的描述出发,根据问题的固有属性,)从问题本身的描述出发,根据问题的固有属性,从头设计一个全新的并行算法,这种方法有一定难度,但从头设计一个全新的并行算法,这种方法有一定难度,但所设计的并行算法通常是高效的;所设计的并行算法通常是高效的;(3)借助已有的并行算法求解新问题。)借助已有的并行算法求解新问题。36.1 6.1 串行算法的直接并行化串行算法的直接并行化方法描述方法描述发掘和利用现有串行算法
3、中的并行性,直接将串行算法改发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。造为并行算法。评注评注由串行算法直接并行化的方法是并行算法设计的最常用方由串行算法直接并行化的方法是并行算法设计的最常用方法之一;法之一;并非所有的串行算法都可以并行化;并非所有的串行算法都可以并行化;一个好的串行算法并不能并行化为一个好的并行算法,相一个好的串行算法并不能并行化为一个好的并行算法,相反一个不好的串行算法则有可能产生很优秀的并行算法,反一个不好的串行算法则有可能产生很优秀的并行算法,例如枚举排序不是一种好的串行算法。但是将其直接并行例如枚举排序不是一种好的串行算法。但是将其直接并行化后可
4、以得到比较好的并行算法化后可以得到比较好的并行算法;显著优点:无需考虑算法的稳定性、收敛性等复杂问题。显著优点:无需考虑算法的稳定性、收敛性等复杂问题。4积分算法的直接并行化积分算法的直接并行化-的计算的计算5计算计算的串行的串行C代码代码#define N 1000000main()double local,pi=0.0,w;long i;w=1.0/N;for(i=0;iN;i+)local=(i+0.5)*w;pi=pi+4.0/(1.0+local*local);printf(“pi is%f n”,pi*w);6k个处理器并行地计算部分和个处理器并行地计算部分和7计算计算的的MPI代
5、码代码#define N 100000 main()double local=0.0,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,&numtask);/*每个处理器确定总处理每个处理器确定总处理 器个数器个数*/B:for(i=taskid;iaj thenk=k+1 end ifend
6、 for(3)bk=aiend forEnd10枚举排序的并行算法枚举排序的并行算法对该算法的并行化是很简单的,假设对一个长为对该算法的并行化是很简单的,假设对一个长为n的输的输入序列使用入序列使用n个处理器进行排序,只需每个处理器负责个处理器进行排序,只需每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息完成对其中一个元素的定位,然后将所有的定位信息集中到主进程中,由主进程负责完成所有元素的最终集中到主进程中,由主进程负责完成所有元素的最终排位。排位。11枚举排序并行算法枚举排序并行算法输入:无序数组输入:无序数组a1an输出:有序数组输出:有序数组b1bnBegin(1)P0播送
7、播送a1an给所有给所有Pi(2)for all Pi where 1in para-do (2.1)k=1 (2.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);所以总的计算复杂度);所以总的计算复杂度为
8、为O(n),总的通信复杂度为),总的通信复杂度为O(n2)。)。12快速排序(快速排序(Quick Sort)快速排序(快速排序(Quick SortQuick Sort)是一种最基本的排序算法)是一种最基本的排序算法基本思想:在当前无序区基本思想:在当前无序区R1,nR1,n中取一个记录作为比较的中取一个记录作为比较的“基基准准”,用此基准将当前的无序区,用此基准将当前的无序区R1,nR1,n划分成左右两个无序的划分成左右两个无序的子区子区R1,i-1R1,i-1和和Ri,n(1in)Ri,n(1in),且左边的无序子区中记录,且左边的无序子区中记录的所有关键字均小于等于基准的关键字,右边的
9、无序子区中记的所有关键字均小于等于基准的关键字,右边的无序子区中记录的所有关键字均大于等于基准的关键字。录的所有关键字均大于等于基准的关键字。快速排序算法的性能主要决定于输入数组的划分是否均衡,而快速排序算法的性能主要决定于输入数组的划分是否均衡,而这与基准元素的选择密切相关。这与基准元素的选择密切相关。在最坏情况下,划分的结果是一边有在最坏情况下,划分的结果是一边有n-1n-1个元素,而另一边有个元素,而另一边有0 0个元素。如果每次递归排序中的划分都产生这种极度的不平衡,个元素。如果每次递归排序中的划分都产生这种极度的不平衡,那么整个算法的复杂度将是那么整个算法的复杂度将是(n n2 2)
10、。在最好的情况下,每次)。在最好的情况下,每次划分都使得输入数组平均分为两半,那么算法的复杂度为划分都使得输入数组平均分为两半,那么算法的复杂度为O O(n nloglogn n)。在一般的情况下该算法仍能保持)。在一般的情况下该算法仍能保持O O(n nloglogn n)的复)的复杂度,只不过其具有更高的常数因子。杂度,只不过其具有更高的常数因子。13 快速排序算法的串行实现快速排序算法的串行实现SISD上的快排序算法上的快排序算法 输入:无序序列输入:无序序列(Aq,Ar)输出:有序序列输出:有序序列(Aq,Ar)Procedure QUICKSORT(A,q,r)Begin if q
11、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 (2.1)从某个从进程)从某个从进程i接收信号接收信号signal (2.2)if signal=Accomplished then 从从进程从从进程i接收并记录解接收并记录解 end if (2.3)if has_more_boards then ()向从
12、进程向从进程i发送发送NewTask信号信号 ()向从进程向从进程i发送一个新棋盘发送一个新棋盘 else ()向从进程向从进程i发送发送Terminate信号信号 ()active_slaves=active_slaves-1 end if end whileEnd/*EightQueensMaster*/35从进程算法从进程算法procedure EightQueenSlaveBegin(1)向主进程发送)向主进程发送Ready信号信号(2)finished=false(3)while not finished do (3.1)从主进程接收信号)从主进程接收信号signal (3.2)if
13、 signal=NewTask then ()从主进程接收新棋盘从主进程接收新棋盘 ()if 新棋盘合法新棋盘合法 then 在新棋盘的基础上找出所有合法的解,并将解发送在新棋盘的基础上找出所有合法的解,并将解发送 给主进程给主进程 end if else/*signal=Terminate*/finished=true end ifend whileEnd/*EightQueenSlave*/36附附2:单源最短路径问题:单源最短路径问题单源最短路径单源最短路径(Single Source Shortest Path)问题是指问题是指求从一个指定顶点求从一个指定顶点s到其它所有顶点到其它所有
14、顶点i之间的距离,因为之间的距离,因为是单一顶点到其它顶点的距离,所以称为单源。设图是单一顶点到其它顶点的距离,所以称为单源。设图G(V,E)是一个有向加权网络,其中是一个有向加权网络,其中V和和E分别为顶点集分别为顶点集合和边集合,其边权邻接矩阵为合和边集合,其边权邻接矩阵为W,边上权值,边上权值w(i,j)0,i,jV,V=0,1,N-1。设设dist(i)为最短的路径长度,即距离,其中为最短的路径长度,即距离,其中sV且且is。这里采用著名的这里采用著名的Dijkstra算法,并将其并行化。算法,并将其并行化。37把把V V分成两组:分成两组:(1 1)S S:存放:存放已求已求得得最短
15、路径的顶点的集合最短路径的顶点的集合(2 2)T=V-ST=V-S:尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合将将T T中顶点按最短路径中顶点按最短路径非递减非递减的次序加入到的次序加入到S S中中。迪杰斯特拉(迪杰斯特拉(Dijkstra)算法思想)算法思想:这个过程中,总这个过程中,总保保持持:从源点从源点V V0 0到到S S中各顶点中各顶点的最短路径长度都的最短路径长度都不大于不大于从从V V0 0到到T T中任何顶点中任何顶点的最的最短路径长度短路径长度。而且而且每个顶点对应一个距离值每个顶点对应一个距离值:S S中顶点中顶点对应的距离值对应的距离值,是,是从从V V0 0
16、到此顶点的到此顶点的最短路径长度最短路径长度;T T中顶点中顶点对应的距离值对应的距离值,是,是从从V V0 0到此顶点的到此顶点的只包括只包括S S中顶点作中间顶点中顶点作中间顶点的的当前当前最短路径长度最短路径长度。38迪杰斯特拉算法求单源最短路径步骤:迪杰斯特拉算法求单源最短路径步骤:首先求得长度首先求得长度最短最短的一条最短路径,再求得长度的一条最短路径,再求得长度次短次短的一的一条最短路径,条最短路径,依此类推依此类推,直到从源点到其它所有顶点之间,直到从源点到其它所有顶点之间的最短路径都已求得为止。的最短路径都已求得为止。初始状态初始状态下下集合集合S中只有源点中只有源点v0,即:
17、,即:S=v0,T=其余顶点其余顶点。T中顶点中顶点vi对应的对应的当前最短路径长度当前最短路径长度:若若存在存在v,为,为v 弧上的权值弧上的权值w(vw(v0 0,v,vi i)若若不存在不存在v ,为为39从从T T中选取一个中选取一个当前最短路径长度最小当前最短路径长度最小的顶点的顶点v vk k加入加入S S。对对T T中剩余顶点中剩余顶点v vi i的的当前最短路径长度当前最短路径长度进行进行修改修改:若若加加进进v vk k作作中中间间顶顶点点,从从v v0 0到到v vi i的的距距离离值值比比不不加加v vk k的的路路径径要短要短,则,则修改此修改此距离值距离值。重重复复上
18、上述述步步骤骤,按按照照当当前前最最短短路路径径长长度度的的非非减减次次序序产产生生下下一一条条最最短短路路径径,并并将将该该路路径径的的终终点点t t T T加加入入S S中中,并并更更新新T T中剩余顶点的中剩余顶点的当前最短路径长度当前最短路径长度。直直到到S SV V时时(即即从从源源点点v v0 0到到其其他他所所有有结结点点之之间间的的最最短短路路径都已求得径都已求得为止),算法结束。为止),算法结束。40选择数据结构选择数据结构 一维数组一维数组d d didi 中存放从中存放从源点源点v v0 0到到v vi i的的当前最短路径长度当前最短路径长度,一维整型数组一维整型数组pa
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精简 并行 算法 一般 设计 策略
限制150内