1分布式系统DistributedSystem计算机学院软件工程系主讲：陈蕾E-mail:chenleijx@sohu
com2第六章并行算法的一般设计策略6
1串行算法的直接并行化6
2从问题描述开始设计并行算法6
3借用已有算法求解新问题6
4串行算法的直接并行化补充实例:八皇后问题和单源最短路径问题3设计并行算法一般有3种方法：（1）检查和开拓现有串行算法中固有的并行性，直接将其并行化，该方法并不是对所有问题总是可行的，但对很多应用问题仍不失为一种有效的方法；（2）从问题本身的描述出发，根据问题的固有属性，从头设计一个全新的并行算法，这种方法有一定难度，但所设计的并行算法通常是高效的；（3）借助已有的并行算法求解新问题
1串行算法的直接并行化串行算法的直接并行化方法描述发掘和利用现有串行算法中的并行性，直接将串行算法改造为并行算法
评注由串行算法直接并行化的方法是并行算法设计的最常用方法之一；并非所有的串行算法都可以并行化；一个好的串行算法并不能并行化为一个好的并行算法，相反一个不好的串行算法则有可能产生很优秀的并行算法，例如枚举排序不是一种好的串行算法
但是将其直接并行化后可以得到比较好的并行算法；显著优点：无需考虑算法的稳定性、收敛性等复杂问题
5积分算法的直接并行化--π的计算0112341220044110
51iNdxxNiN6计算π的串行C代码#defineN1000000main(){doublelocal,pi=0
0,w;longi;w=1
0/N;for(i=0;ia[j])or(a[i]=a[j]andi>j)thenk=k+1endifendfor(3)P0收集k并按序定位End步骤⑵的时间复杂度为O（n）；步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O（n），通信复杂度分别为O（n）；同时
