电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

精简版第6章并行算法的一般设计策略VIP免费

精简版第6章并行算法的一般设计策略_第1页
1/56
精简版第6章并行算法的一般设计策略_第2页
2/56
精简版第6章并行算法的一般设计策略_第3页
3/56
1分布式系统DistributedSystem计算机学院软件工程系主讲:陈蕾E-mail:chenleijx@sohu.com2第六章并行算法的一般设计策略6.1串行算法的直接并行化6.2从问题描述开始设计并行算法6.3借用已有算法求解新问题6.4串行算法的直接并行化补充实例:八皇后问题和单源最短路径问题3设计并行算法一般有3种方法:(1)检查和开拓现有串行算法中固有的并行性,直接将其并行化,该方法并不是对所有问题总是可行的,但对很多应用问题仍不失为一种有效的方法;(2)从问题本身的描述出发,根据问题的固有属性,从头设计一个全新的并行算法,这种方法有一定难度,但所设计的并行算法通常是高效的;(3)借助已有的并行算法求解新问题。46.16.1串行算法的直接并行化串行算法的直接并行化方法描述发掘和利用现有串行算法中的并行性,直接将串行算法改造为并行算法。评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一;并非所有的串行算法都可以并行化;一个好的串行算法并不能并行化为一个好的并行算法,相反一个不好的串行算法则有可能产生很优秀的并行算法,例如枚举排序不是一种好的串行算法。但是将其直接并行化后可以得到比较好的并行算法;显著优点:无需考虑算法的稳定性、收敛性等复杂问题。5积分算法的直接并行化--π的计算0112341220044110.51iNdxxNiN6计算π的串行C代码#defineN1000000main(){doublelocal,pi=0.0,w;longi;w=1.0/N;for(i=0;ia[j]thenk=k+1endifendfor(3)b[k]=a[i]endforEnd11枚举排序的并行算法对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序,只需每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程中,由主进程负责完成所有元素的最终排位。12枚举排序并行算法输入:无序数组a[1]…a[n]输出:有序数组b[1]…b[n]Begin(1)P0播送a[1]…a[n]给所有Pi(2)forallPiwhere1≤i≤npara-do(2.1)k=1(2.2)forj=1tondoif(a[i]>a[j])or(a[i]=a[j]andi>j)thenk=k+1endifendfor(3)P0收集k并按序定位End步骤⑵的时间复杂度为O(n);步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O(n),通信复杂度分别为O(n);同时⑴中的通信复杂度为O(n2);所以总的计算复杂度为O(n),总的通信复杂度为O(n2)。13快速排序(QuickSort)快速排序(QuickSort)是一种最基本的排序算法基本思想:在当前无序区R[1,n]中取一个记录作为比较的“基准”,用此基准将当前的无序区R[1,n]划分成左右两个无序的子区R[1,i-1]和R[i,n](1≤i≤n),且左边的无序子区中记录的所有关键字均小于等于基准的关键字,右边的无序子区中记录的所有关键字均大于等于基准的关键字。快速排序算法的性能主要决定...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

精简版第6章并行算法的一般设计策略

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部