分布式系統(tǒng)開發(fā)第六章并行算法的一般設計策略

1、1分布式系統(tǒng)開發(fā)第六章 并行算法的一般設計策略26.1 串行算法的直接并行化6.2 從問題描述開始設計并行算法6.3 借用已有算法求解新問題6.4 串行算法的直接并行化補充實例:八皇后問題和單源最短路徑問題3設計并行算法一般有3種方法：（1）檢查和開拓現(xiàn)有串行算法中固有的并行性，直接將其并行化，該方法并不是對所有問題總是可行的，但對很多應用問題仍不失為一種有效的方法；（2）從問題本身的描述出發(fā)，根據(jù)問題的固有屬性，從頭設計一個全新的并行算法，這種方法有一定難度，但所設計的并行算法通常是高效的；（3）借助已有的并行算法求解新問題。 46.1 串行算法的直接并行化方法描述發(fā)掘和利用現(xiàn)有串行算法中的

2、并行性，直接將串行算法改造為并行算法。評注由串行算法直接并行化的方法是并行算法設計的最常用方法之一；并非所有的串行算法都可以并行化；一個好的串行算法并不能并行化為一個好的并行算法，相反一個不好的串行算法則有可能產(chǎn)生很優(yōu)秀的并行算法，例如枚舉排序不是一種好的串行算法。但是將其直接并行化后可以得到比較好的并行算法 ；顯著優(yōu)點：無需考慮算法的穩(wěn)定性、收斂性等復雜問題。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)；/*每個處理器確定總處理 器個數(shù)*/ B： for (i= taskid； iaj thenk=k+1 end ifend for(3)bk= aiend forEnd11枚舉排序的并行算法對該算法的并行化是很簡單的，假設對一個長為n的輸入序列使用n個處理器進行排序，只需每個處理器負責完成對其中一個元素的定位，然后將所有的定位信息集中到主進程中，由主進程負責完成所有元素的最終排位。 12枚舉排序并行算法輸入：無序數(shù)組a1an輸出：有序數(shù)組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）；步驟中主進程完成的數(shù)組元素重定位操作的時間復雜度為O（n），通信復雜度分別為O（n）；同時中的通信復雜度為O（n2）；所以總的計算復雜度為O（n），總的通信復雜度為O（n2）。13快速排序（Quick Sort）快速排序（Quick Sort）是一種最基本的排序算法基本思想：在當前無序區(qū)R1,n中取一個記錄作為比較的“基準”，用此基準將當前的無序區(qū)R1,n劃分成左右兩個無序的子區(qū)R1

6、,i-1和Ri,n(1in)，且左邊的無序子區(qū)中記錄的所有關鍵字均小于等于基準的關鍵字，右邊的無序子區(qū)中記錄的所有關鍵字均大于等于基準的關鍵字?？焖倥判蛩惴ǖ男阅苤饕獩Q定于輸入數(shù)組的劃分是否均衡，而這與基準元素的選擇密切相關。在最壞情況下，劃分的結(jié)果是一邊有n-1個元素，而另一邊有0個元素。如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個算法的復雜度將是（n2）。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復雜度為O（nlogn）。在一般的情況下該算法仍能保持O（nlogn）的復雜度，只不過其具有更高的常數(shù)因子。 14 快速排序算法的串行實現(xiàn)SISD上的快排序算法 輸

7、入：無序序列(Aq,Ar) 輸出：有序序列(Aq,Ar) Procedure QUICKSORT（A, q, r） Begin if q 8 then OutputResult(chessboard)/* 結(jié)束遞歸并輸出結(jié)果 */ 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發(fā)送NewTask信號 ()向從進程i發(fā)送一個新棋盤 else ()向從進程i發(fā)送Terminate信號 ()active_slaves = active_slaves - 1 end if end whileEnd /* EightQueensMaster */36從進程算法procedure EightQueenSlaveBegin（1）向主進程發(fā)送Ready信號（2）finished = false（3）while not finished do （）從主進程接收信號signal （）if signal = NewTask the

9、n ()從主進程接收新棋盤 ()if 新棋盤合法 then 在新棋盤的基礎上找出所有合法的解，并將解發(fā)送 給主進程 end if else /* signal = Terminate */finished = true end ifend whileEnd /* EightQueenSlave */37附2：單源最短路徑問題單源最短路徑(Single Source Shortest Path)問題是指求從一個指定頂點s到其它所有頂點i之間的距離，因為是單一頂點到其它頂點的距離，所以稱為單源。設圖G(V,E)是一個有向加權網(wǎng)絡，其中V和E分別為頂點集合和邊集合，其邊權鄰接矩陣為W，邊上權值w(i

10、,j) 0，i,jV，V=0,1,N-1。設dist( i )為最短的路徑長度，即距離，其中sV且is。這里采用著名的Dijkstra算法，并將其并行化。38最短路徑問題用帶權的有向圖表示一個交通運輸網(wǎng)，圖中：頂點表示城市邊表示城市間的交通聯(lián)系權表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖中的邊是否有路可達另一頂點？若有多條路徑可達，則在所經(jīng)過的路徑中，各邊上權值之和最小的一條路徑最短路徑。這就是路由選擇。如：郵政自動分揀機的路選裝置、計算機網(wǎng)絡中的路由選擇等。問題提出39單源最短路徑：指的是對已知圖G=(V,E)，給定源點sV，找出s到圖中其它各頂點的最短路徑。每

11、對結(jié)點間的最短路徑指的是對已知圖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、到其他各頂點的最短路徑長度的從小到大的次序逐一產(chǎn)生最短路徑。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迪杰斯特拉算法求單源最短路徑步驟：首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有頂點之間的最短路徑都已求得為止。初始狀態(tài)下集合S中只有源點v0，即： S=v0，T=其余頂點。T中頂點vi對應的當前最短路徑長度： 若存在，為弧上的權值w(v0,vi) 若不存在 ，為50從T中選取一個當前最短路徑長度最小的頂點vk加入S。對T中剩余頂點vi的當前最短路徑長度進行修改：若加進vk作中間頂點，從v0到vi的距離值比不加vk的路徑要短，則修改此距離值。重復上述步驟，按照當前最短路徑長度的非

15、減次序產(chǎn)生下一條最短路徑，并將該路徑的終點tT加入S中，并更新T中剩余頂點的當前最短路徑長度。直到SV時（即從源點v0到其他所有結(jié)點之間的最短路徑都已求得為止），算法結(jié)束。51選擇數(shù)據(jù)結(jié)構 一維數(shù)組d di中存放從源點v0到vi的當前最短路徑長度，該路徑上除頂點vi自身外，其余頂點都屬于S，并且是所有這些路徑中的最短者。 一維整型數(shù)組path pathi給出從v0到頂點vi的最短路徑上，位于頂點vi前面的那個頂點。例如：從v0到v1的最短路徑為（v0,v2,v3,v1）則有path1=3，path3=2，path2=0一維布爾數(shù)組s 若si為true，表示頂點vi在S中；否則表示vi在V-S中

16、。52Sd0path0d1path1d2path2d3path3d4path4d5path500，-1 初始狀態(tài)S=v0，T=其余頂點。024170535010353031520101520源點v0到自身的路徑長度為0，路徑上0前面的頂點不存在因此為-1。初始狀態(tài)下T中頂點vi對應的當前最短路徑長度di和該路徑上i前面的結(jié)點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時算法結(jié)束。（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)是單源最短路徑問題的經(jīng)典解法之一，基本思想如下：假定有一個待搜索的頂點表VL，初始化時做： dist(s)0，dist(i)=(is)，VL=V。每次從VL（非空集）中選取這樣的一個頂點u，它的dist(u)最小。將選出的u點作為搜索頂點，對于其它還在VL內(nèi)的頂點v，若E,而且dist(u)+w(u,v)dist(v)，則