并行算法的一般设计策略讲稿.ppt
《并行算法的一般设计策略讲稿.ppt》由会员分享,可在线阅读,更多相关《并行算法的一般设计策略讲稿.ppt(65页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、并行算法的一般设计策略并行算法的一般设计策略1第一页,讲稿共六十五页哦第六章第六章 并行算法的一般设计策略并行算法的一般设计策略6.1 串行算法的直接并行化串行算法的直接并行化6.2 从从问题描述开始描述开始设计并行算法并行算法6.3 借用已有算法求解新借用已有算法求解新问题6.4 串行算法的直接并行化串行算法的直接并行化补充充实例例:八皇后八皇后问题和和单源最短路径源最短路径问题2第二页,讲稿共六十五页哦设计并行算法一般有并行算法一般有3种方法:种方法:(1)检查和开拓和开拓现有串行算法中固有的并行性,直有串行算法中固有的并行性,直接将其并行化,接将其并行化,该方法并不是方法并不是对所有所有
2、问题总是可行的,但是可行的,但对很多很多应用用问题仍不失仍不失为一种有效的方法;一种有效的方法;(2)从)从问题本身的描述出本身的描述出发,根据,根据问题的固有属性,的固有属性,从从头设计一个全新的并行算法,一个全新的并行算法,这种方法有一定种方法有一定难度,但度,但所所设计的并行算法通常是高效的;的并行算法通常是高效的;(3)借助已有的并行算法求解新)借助已有的并行算法求解新问题。3第三页,讲稿共六十五页哦6.1 串行算法的直接并行化串行算法的直接并行化方法描述方法描述发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。评注注由串行算法直接并行化的方法是并行算法设计的最常用方法之
3、一;并非所有的串行算法都可以并行化;一个好的串行算法并不能并行化为一个好的并行算法,相反一个不好的串行算法则有可能产生很优秀的并行算法,例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法;显著优点:无需考虑算法的稳定性、收敛性等复杂问题。4第四页,讲稿共六十五页哦积分算法的直接并行化积分算法的直接并行化-的计算的计算5第五页,讲稿共六十五页哦计算计算的串行的串行C代码代码#defineN1000000main()doublelocal,pi=0.0,w;longi;w=1.0/N;for(i=0;iN;i+)local=(i+0.5)*w;pi=pi+4.0/(1.
4、0+local*local);printf(“piis%fn”,pi*w);6第六页,讲稿共六十五页哦k个处理器并行地计算部分和个处理器并行地计算部分和7第七页,讲稿共六十五页哦计算计算的的MPI代码代码#defineN100000main()doublelocal=0.0,pi,w,temp=0.0;longi,taskid,numtask;A:w=1.0/N;MPI_Init(&argc,&argv);/*MPI初始化初始化*/MPI_Comm_rank(MPI_COMM_WORLD,&taskid);/*每个每个处理器确定各自理器确定各自ID*/MPI_Comm_Size(MPI_COM
5、M_WORLD,&numtask);/*每个每个处理器确定理器确定总处理理 器个数器个数*/B:for(i=taskid;iaj thenk=k+1 end ifend for(3)bk=aiend forEnd10第十页,讲稿共六十五页哦枚举排序的并行算法枚举排序的并行算法对该算法的并行化是很算法的并行化是很简单的,假的,假设对一个一个长为n的的输入序列使用入序列使用n个个处理器理器进行排序,只需每个行排序,只需每个处理器理器负责完成完成对其中一个元素的定位,然后将所有的定位信息其中一个元素的定位,然后将所有的定位信息集中到主集中到主进程中,由主程中,由主进程程负责完成所有元素的最完成所有元
6、素的最终排位。排位。11第十一页,讲稿共六十五页哦枚举排序并行算法枚举排序并行算法输入:无序数入:无序数组a1an输出:有序数出:有序数组b1bnBegin(1)P0播送播送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);步骤);步骤中主进程完成中主进程完成的数组元素重定位操作的时间复杂度为的数组元素重定位操作
7、的时间复杂度为O(n),通),通信复杂度分别为信复杂度分别为O(n);同时);同时中的通信复杂度为中的通信复杂度为O(n2);所以总的计算复杂度为);所以总的计算复杂度为O(n),总的通信复杂度为),总的通信复杂度为O(n2)。)。12第十二页,讲稿共六十五页哦快速排序(快速排序(Quick Sort)快速排序(快速排序(Quick Sort)是一种最基本的排序算法)是一种最基本的排序算法基本思想:在当前无序区基本思想:在当前无序区R1,n中取一个中取一个记录作作为比比较的的“基基准准”,用此基准将当前的无序区,用此基准将当前的无序区R1,n划分成左右两个无序的划分成左右两个无序的子区子区R1
8、,i-1和和Ri,n(1in),且左,且左边的无序子区中的无序子区中记录的所有的所有关关键字均小于等于基准的关字均小于等于基准的关键字,右字,右边的无序子区中的无序子区中记录的所的所有关有关键字均大于等于基准的关字均大于等于基准的关键字。字。快速排序算法的性能主要决定于快速排序算法的性能主要决定于输入数入数组的划分是否均衡,而的划分是否均衡,而这与基准元素的与基准元素的选择密切相关。密切相关。在最坏情况下,划分的在最坏情况下,划分的结果是一果是一边有有n-1个元素,而另一个元素,而另一边有有0个元素。如果每次个元素。如果每次递归排序中的划分都排序中的划分都产生生这种极度的不平衡,种极度的不平衡
9、,那么整个算法的复那么整个算法的复杂度将是度将是(n2)。在最好的情况下,每次)。在最好的情况下,每次划分都使得划分都使得输入数入数组平均分平均分为两半,那么算法的复两半,那么算法的复杂度度为O(nlogn)。在一般的情况下)。在一般的情况下该算法仍能保持算法仍能保持O(nlogn)的)的复复杂度,只不度,只不过其具有更高的常数因子。其具有更高的常数因子。13第十三页,讲稿共六十五页哦 快速排序算法的串行实现快速排序算法的串行实现SISD上的快排序算法上的快排序算法输入:无序序列入:无序序列(Aq,Ar)输出:有序序列出:有序序列(Aq,Ar)ProcedureQUICKSORT(A,q,r)
10、Beginifq8thenOutputResult(chessboard)/*结束束递归并并输出出结果果*/elseforcol=1to8do/*判断是否有列、判断是否有列、对角角线或反或反对角角线冲突冲突*/(1)no_collision=true(2)i=1(3)while no_collision and i 0do(2.1)从某个从)从某个从进程程i接收信号接收信号signal(2.2)ifsignal=Accomplishedthen从从从从进程程i接收并接收并记录解解endif(2.3)ifhas_more_boardsthen()向从向从进程程i发送送NewTask信号信号()向
11、从向从进程程i发送一个新棋送一个新棋盘else()向从向从进程程i发送送Terminate信号信号()active_slaves=active_slaves-1endifendwhileEnd/*EightQueensMaster*/35第三十五页,讲稿共六十五页哦从进程算法从进程算法procedure EightQueenSlaveBegin(1)向主)向主进程程发送送Ready信号信号(2)finished=false(3)while not finished do (3.1)从主)从主进程接收信号程接收信号signal (3.2)if signal=NewTask then ()从主从主
12、进程接收新棋程接收新棋盘 ()if 新棋新棋盘合法合法 then 在新棋盘的基础上找出所有合法的解,并将解发送 给主进程 end if else/*signal=Terminate*/finished=true end ifend whileEnd/*EightQueenSlave*/36第三十六页,讲稿共六十五页哦附附2:单源最短路径问题:单源最短路径问题单源最短路径源最短路径(SingleSourceShortestPath)问题是指求是指求从一个指定从一个指定顶点点s到其它所有到其它所有顶点点i之之间的距离,因的距离,因为是是单一一顶点到其它点到其它顶点的距离,所以称点的距离,所以称为单
13、源。源。设图G(V,E)是一个有向加是一个有向加权网网络,其中,其中V和和E分分别为顶点集点集合和合和边集合,其集合,其边权邻接矩接矩阵为W,边上上权值w(i,j)0,i,jV,V=0,1,N-1。设dist(i)为最短的路径最短的路径长度,即距离,其中度,即距离,其中sV且且is。这里采用著名的里采用著名的Dijkstra算法,并将其并行化。算法,并将其并行化。37第三十七页,讲稿共六十五页哦最短路径问题最短路径问题用用带权的有向的有向图表示一个交通运表示一个交通运输网,网,图中:中:顶点点表示城市表示城市边表示城市表示城市间的交通的交通联系系权表示此表示此线路的路的长度或沿此度或沿此线路运
14、路运输所花的所花的时间或或费用等用等问题:从某从某顶点出点出发,沿,沿图中的中的边是否有路可达是否有路可达另一另一顶点?若有点?若有多条路径可达,多条路径可达,则在所在所经过的路径中,各的路径中,各边上上权值之和最小的之和最小的一条路径一条路径最短路径最短路径。这这就是就是就是就是路由路由路由路由选择选择。如:如:邮政自政自动分分拣机的路机的路选装置、装置、计算机网算机网络中的路由中的路由选择等等。问题提出问题提出38第三十八页,讲稿共六十五页哦单单源最短路径:源最短路径:源最短路径:源最短路径:指的是指的是指的是指的是对对已知已知已知已知图图G=(V,E)G=(V,E),给给定源点定源点定源
15、点定源点s s V V,找出,找出,找出,找出s s到到到到图图中其它各中其它各中其它各中其它各顶顶点点点点的最短路径。的最短路径。的最短路径。的最短路径。每每每每对结对结点点点点间间的最短路径的最短路径的最短路径的最短路径指的是指的是指的是指的是对对已知已知已知已知图图G=(V,E)G=(V,E),任意的任意的任意的任意的顶顶点点点点V Vi i,V,Vj j V V,找出从,找出从,找出从,找出从V Vi i到到到到V Vj j的最的最的最的最短路径。短路径。短路径。短路径。两种最常两种最常见的最短路径算法:的最短路径算法:求求单源最短路径的源最短路径的迪杰斯特拉(迪杰斯特拉(Djikst
16、ra)算法)算法和求所有和求所有顶点之点之间的最短路径的的最短路径的弗洛伊德(弗洛伊德(Floyd)算法)算法。39第三十九页,讲稿共六十五页哦单单源源源源最最最最短短短短路路路路径径径径问题:给定定带权有有向向图G=(V,E),求求从从某某个个给定定的的源点源点v0 V到其余各到其余各顶点的最短路径。点的最短路径。迪杰斯特拉算法迪杰斯特拉算法 40第四十页,讲稿共六十五页哦0 02 24 41 170705 53 350501010353530303 315152020101015152020源源点点终终点点最短路径最短路径路径长路径长度度01(0,2,3,1)452(0,2)103(0,2
17、,3)254(0,2,3,1,4)555(a)(a)带权的有向图带权的有向图带权的有向图带权的有向图GG(b)(b)图图图图GG顶点顶点顶点顶点0 0的单源最短路径的单源最短路径的单源最短路径的单源最短路径迪杰斯特拉算法迪杰斯特拉算法迪杰斯特拉算法迪杰斯特拉算法按从源点到其他各顶点的按从源点到其他各顶点的按从源点到其他各顶点的按从源点到其他各顶点的最短路径长度最短路径长度最短路径长度最短路径长度的的的的从小到大的次序从小到大的次序从小到大的次序从小到大的次序逐一产生最短路径。逐一产生最短路径。逐一产生最短路径。逐一产生最短路径。41第四十一页,讲稿共六十五页哦把把V V分成两分成两组:(1 1
18、)S S:存放已求得最短路径的:存放已求得最短路径的顶点的集合点的集合(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 V
19、0 0到此到此顶点的点的最短路径最短路径长度度;T T中中顶点点对应的距离的距离值,是从,是从V V0 0到此到此顶点的点的只包括只包括S S中中顶点作中点作中间顶点点的的当前最短路当前最短路径径长度度。42第四十二页,讲稿共六十五页哦单源最短路径图例单源最短路径图例求上图中源点求上图中源点求上图中源点求上图中源点0 0 0 0到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径10100 02 24 41 170705 53 350501010353530303 3151520201010151520205050707043第四十三页,讲稿共六十五页哦单源
20、最短路径图例单源最短路径图例求上图中源点求上图中源点求上图中源点求上图中源点0 0 0 0到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径0 02 24 41 170705 53 350501010353530303 315152020101015152020101050502525707044第四十四页,讲稿共六十五页哦单源最短路径图例单源最短路径图例求上图中源点求上图中源点求上图中源点求上图中源点0 0 0 0到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径到其他各顶点的最短路径0 02 24 41 170705 53 350501
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并行 算法 一般 设计 策略 讲稿
限制150内