《并行計算負載平衡和終止檢測》由會員分享，可在線閱讀，更多相關(guān)《并行計算負載平衡和終止檢測（64頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,,,,*,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,第七章 負載平衡和終止檢測,Load Balancing and Termination Detection,負載平衡,----,在并行系統(tǒng)中，使各個節(jié)點盡量均衡地分配工作任務(wù)的技術(shù)。通過在處理機之間均衡地、合理地分配計算任務(wù)，以獲得最大可能的執(zhí)行速度。,,終止檢測,----,檢測一個計算任務(wù)何時已經(jīng)結(jié)束。當(dāng)計算是分布式時，檢測計算的終止是一件困難的、且重要的問題。,主要內(nèi)容,負載平衡,,靜態(tài)負載平衡,,確定模式與非確定模式,,動態(tài)負載平衡,,集中式與分散式,,分布式終止檢測方法,,終止

2、條件,,幾個終止檢測算法,,負載平衡和終止檢測實例,主要內(nèi)容,負載平衡,,靜態(tài)負載平衡,,確定模式與非確定模式,,動態(tài)負載平衡,,集中式與分散式,,分布式終止檢測方法,,終止條件,,幾個終止檢測算法,,負載平衡和終止檢測實例,P,1,P,0,P,2,P,3,P,4,P,5,處理機,,,,,,,,time,一、負載平衡,,靜態(tài)負載平衡,,動態(tài)負載平衡,負載平衡,,time,處理機,,P,1,P,0,P,2,P,3,P,4,P,5,,,,,,,負載平衡是利用調(diào)度程序?qū)崿F(xiàn)的。,,調(diào)度的目的是通過將任務(wù)正確分配給各處理機，并使得任務(wù)按照一定的順序執(zhí)行，,以盡可能少的時間完成并行應(yīng)用任務(wù)。,,在靜態(tài)調(diào)度

3、中，調(diào)度通常是在編譯時進行的。并行程序的特點（如：任務(wù)的執(zhí)行時間、通信、數(shù)據(jù)的相互關(guān)聯(lián)和同步等）在程序執(zhí)行之前都是已知的。,,在動態(tài)調(diào)度中，并行程序的特點在執(zhí)行之前往往知道得很少，因此，調(diào)度是在程序執(zhí)行時進行的。它使程序的執(zhí)行時間和調(diào)度時間盡可能最小。,1.,,靜態(tài)負載平衡,在任何進程執(zhí)行之前進行的負載平衡稱為靜態(tài)負載平衡。,,靜態(tài)負載平衡的優(yōu)點：,,一般情況下比動態(tài)負載平衡省時；,,一般情況下，靜態(tài)負載平衡在每個處理機上僅生成一個進程，從而減少了進程建立、同步和終止的開銷；,,可用來評估并行算法的加速比和性能,。,有向無回路圖,(,directed acyclic graph,),利用靜態(tài)調(diào)

4、度的并行程序可由一個有向無回路圖,G=(V,E),來表示，其中：,,V—,節(jié)點的有限集合，一個節(jié)點表示一個子任務(wù),,E—,有向邊的有限集合，一個邊表示相連的節(jié)點的前驅(qū)限制,,節(jié)點的權(quán)值,—,計算開銷,,有向邊的權(quán)值,—,該邊相連的節(jié)點間的通信開銷,T1,,2,,T2,,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,10,5,10,15,4,6,7,8,2,靜態(tài)負載平衡,,確定模式：在此模式下，每個子任務(wù)所需的執(zhí)行時間和它們之間執(zhí)行的先后次序在任務(wù)運行前就已確定。,,非確定模式：在此模式下，每個子任務(wù)所需的執(zhí)行時間可表示為一個隨機變量。,任務(wù)圖,T1,,2,,T2,

5、,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,10,5,10,15,4,6,7,8,2,靜態(tài)負載平衡,—,確定模式,一種簡化的情況：任務(wù)間沒有通信開銷，其調(diào)度可利用甘特圖,(Gantt chart),來表示，它表示每個子任務(wù)的執(zhí)行時間和其執(zhí)行所在的處理機。,,該方法也稱為,表調(diào)度,，它生成一個調(diào)度列表。,T1,,2,,T2,,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,T7,T5,T2,T1,,T6,,T3,,,T4,,,,,,,,,,,8,7,5,4,2,9,6,3,1,time,處 理 機,靜態(tài)負載平衡,—,確定模式,最優(yōu)

6、調(diào)度,—,對給定一個任務(wù)圖和處理機數(shù)，使任務(wù)總的執(zhí)行時間最小化的調(diào)度。,,與最優(yōu)調(diào)度有關(guān)的一些結(jié)論：,,如果所有的子任務(wù)都需要一個單位時間，且任務(wù)圖是一個森林，則算法可在多項式時間內(nèi)找到最優(yōu)調(diào)度。,,如果子任務(wù)的執(zhí)行時間是不同的，或有兩個以上的處理機，則找最優(yōu)調(diào)度的問題是,NP,難的。這就意味著在最壞情況下，尋找最優(yōu)調(diào)度的已知的最好的算法需要指數(shù)時間。,確定模式中要求被調(diào)度的任務(wù)中任何特點都不允許再改變，但在實際的任務(wù)調(diào)度過程中，某些任務(wù)的,調(diào)度,往往會影響到后繼任務(wù)的執(zhí)行時間的變化，使后繼任務(wù)的執(zhí)行和通信等產(chǎn)生一些變化。,,目前有很多,基于動態(tài)列表調(diào)度方法,的調(diào)度算法。與傳統(tǒng)方法相比，它們在

7、每次分配任務(wù)之后都要重新計算所有未被調(diào)度節(jié)點的屬性，并利用這些新信息重新安排列表中節(jié)點的順序。,靜態(tài)負載平衡,—,確定模式,靜態(tài)負載平衡,—,確定模式,基于動態(tài)列表調(diào)度方法的調(diào)度算法采用以下三個步驟：,,確定所有未被調(diào)度節(jié)點的新屬性；,,選擇具有最高優(yōu)先級的節(jié)點進行調(diào)度；,,將節(jié)點分配到使它的通信啟動時間,最早的,處理機上。,在動態(tài)列表調(diào)度算法中“確定未被調(diào)度節(jié)點的新屬性”是計算這些節(jié)點的,t-level,和,b-level,值：,,節(jié)點,Ti,的,t-level,：從入口節(jié)點到,Ti,的一條最長的路徑；,,節(jié)點,Ti,的,b-level,：從,Ti,到出口節(jié)點的一條最長的路徑。,,T1,,2

8、,,T5,,4,,T4,,3,,T3,,4,,T2,,3,,T6,,4,,T7,,3,,T8,,1,4,1,10,1,1,1,1,1,6,5,5,,T1,,2,,T5,,4,,T4,,3,,T3,,4,,T2,,3,,T6,,4,,T7,,3,,T8,,1,4,1,10,1,1,1,1,1,6,5,5,節(jié)點,t-level,b-level,T1,0,23,T2,6,15,T3,12,11,T4,3,13,T5,3,14,T6,10,10,T7,8,9,T8,22,1,動態(tài)列表調(diào)度算法實現(xiàn)思想,只用,t-level,的值的意義解釋算法,,在調(diào)度過程中，節(jié)點被調(diào)度之前，它的,t-level,是不斷

9、變化的。,,t-level,值之所以會發(fā)生變化是因為當(dāng)一條邊所連接的兩個節(jié)點恰被分配到同一個處理機上時，這條邊的權(quán)值就會變?yōu)?0,。從而使這條路徑可能不是最長的結(jié)果。,靜態(tài)負載平衡,—,非確定模式,常用的靜態(tài)負載平衡技術(shù)還有：,,循環(huán)算法,,—,按進程順序分配任務(wù)，當(dāng)所有的進程都得到了一個任務(wù)后，再從頭開始分配。,,隨機算法,,—,隨機地選擇進程并分配任務(wù)。,,遞歸二分法,,—,遞歸地將問題分為相等計算量的兩個子問題，并使其通信量最少。,,模擬退火,(,Simulated annealing),—,一種優(yōu)化技術(shù),,遺傳算法,(,Genetic algorithm),—,一種優(yōu)化技術(shù),2.,,動

10、態(tài)負載平衡,在進程的執(zhí)行過程中完成的負載平衡。,,它是在應(yīng)用程序運行期間對各節(jié)點間負載進行平衡的調(diào)度算法，它通過分析并行系統(tǒng)的實時負載信息，動態(tài)地將任務(wù)在各處理機之間進行分配和調(diào)整，以消除系統(tǒng)中負載分布的不均勻性。如：前面講的,Mandelbrot,集、熱分布問題等。,,雖然動態(tài)負載平衡會產(chǎn)生在執(zhí)行期間的額外開銷，但在負載不易均衡的情況下它比靜態(tài)負載平衡往往更有效。,動態(tài)負載平衡,,集中式,—,任務(wù)是從一個中心位置分發(fā)的，通常是主從結(jié)構(gòu)。,,分散式,—,任務(wù)通常在任意進程間進行傳遞。,,一組“工作者”進程根據(jù)問題進行操作，并彼此間進行交互，最后報告給一個單獨的進程。,,一個“工作者”進程可以從

11、其它“工作者”進程接收任務(wù)，也可以將任務(wù)發(fā)給其它“工作者”進程，這些工作都由他們自己來決定。,集中式動態(tài)負載平衡,主進程擁有要被執(zhí)行的任務(wù)集。,,當(dāng)從進程完成一個任務(wù)，向主進程請求另一個任務(wù)時，任務(wù)就由主進程發(fā)給從進程。如：工作池、處理機農(nóng)莊等。,,工作池,主進程,,任務(wù)隊列,,,,從進程,請求任務(wù),(,可能提交一些新任務(wù),),發(fā)送任務(wù),當(dāng)下列條件滿足時計算終止：,,任務(wù)隊列為空，且每個從進程都請求得到新的任務(wù)，但沒有被產(chǎn)生的新任務(wù)。,,當(dāng)任務(wù)隊列為空時，且如果仍有進程運行，則此時終止條件不充分，這是因為運行的進程還可能產(chǎn)生新任務(wù)并放到任務(wù)隊列中。,集中式動態(tài)負載平衡的計算終止,分散式動態(tài)負載

12、平衡,分布式工作池,進程,M,0,主進程,,,初始任務(wù)隊列,,,,,,任務(wù)子隊列,,,,,,任務(wù)子隊列,進程,M,n-1,進程,M,0,主進程,,,初始任務(wù)隊列,,,,,,任務(wù)子隊列,,,,,,任務(wù)子隊列,進程,M,n-1,分散式動態(tài)負載平衡,全分布式工作池,,由接收者啟動方式,—,適合于高系統(tǒng)負載時,,由發(fā)送者啟動方式,—,適合于低系統(tǒng)負載時,,進程,,進程,,進程,,進程,請求,/,任務(wù),使用線性結(jié)構(gòu)實現(xiàn)動態(tài)負載平衡,每個處理機上運行兩個進程,,用于左右兩邊的通信進程,,用于執(zhí)行當(dāng)前任務(wù)的進程,,主進程,P,0,,,,P,1,,,,P,2,,,,P,3,,,,P,n,任務(wù),,,P,comm

13、,,P,task,若緩沖區(qū)為空，則產(chǎn)生請求信號,接收請求的任務(wù),如果,P,task,空閑，則請求任務(wù),接收請求的任務(wù),,請求任務(wù),若緩沖區(qū)滿，則發(fā)送任務(wù),實現(xiàn)通信和計算間的時間共享的代碼,主進程,P,0,：,,,for (i = 0; i < no_tasks; i++) {,,recv(P,1,, request_tag);,/* request for task */,,,/* send tasks into queue */,,send(&task, P,1,, task_tag);,,},,recv(P,1,, request_tag);,/* request for task */,

14、,send(&empty, P,1,, task_tag);,/* end of tasks */,從進程,P,i,(1,?,,i,<,n,),：,,if (buffer == empty) {,,send(P,i-1,, request_tag);,/* request new task */,,recv(&buffer, P,i-1,, task_tag);,/* task from left proc */,,},,if ((buffer == full) && (!busy)) {,/* get next task */,,task = buffer;,/* get task*/,,b

15、uffer = empty;,/* set buffer empty */,,busy = TRUE;,/* set process busy */,,},,nrecv,(P,i+1,, request_tag, request);,/* check msg from right */,,if (request && (buffer == full)) {,,send(&buffer, P,i+1,);,/* shift task forward */,,buffer = empty;,,},,if (busy) {,/* continue on current task */,,Do som

16、e work on task.,,If task finished, set busy to false.,,},必須對右邊接收的請求使用非阻塞,recv — nrecv,，當(dāng),nrecv,收到了請求消息后，會將參數(shù),request,置為,TRUE,。,,MPI,中非阻塞接收例程,MPI_Irecv( ),，,這個函數(shù)比阻塞操作只多一個參數(shù)：,,,MPI_Request *request,,這個函數(shù)的調(diào)用將分配一個通信請求對象，把它和參數(shù),request,連接。之后，,request,能被用于查尋這個通信的狀態(tài)或等待它的完成。,,函數(shù),MPI_WAIT,和,MPI_TEST,用于完成和查詢一

17、個非阻塞通信。,二、 分布式終止檢測算法,終止條件,,使用消息應(yīng)答實現(xiàn)終止檢測,,環(huán)形終止算法,,固定能量分布式終止算法,終止條件,,在時間,t,時需要滿足下列條件：,,在時間,t,時，對所有的進程滿足局部應(yīng)用終止的條件；,,在時間,t,時，沒有消息在進程間傳遞。,,分布式終止條件,與,集中式終止條件,之間存在著一些差別：需要考慮被傳遞的消息。,,考察是否還有被傳遞的消息不是一件容易的事情，因為消息在進程間傳送的時間預(yù)先是不知道的。,一個常見的分布式終止算法,—,,使用消息應(yīng)答實現(xiàn)終止檢測,每個進程處于下面兩種狀態(tài)之一：,,非活動的,(inactive) –,沒有任何任務(wù)要執(zhí)行,,活動的,(a

18、ctive),,發(fā)送一個任務(wù)使某個進程處于活動狀態(tài)的進程稱為被激活進程的“父親”進程。,,當(dāng)進程收到一個任務(wù)（未必是其父親發(fā)來的任務(wù)）時，除了進程接收的任務(wù)來自其父親進程外，它必須馬上發(fā)送一個確認消息。,,每個進程有唯一的父親進程。,當(dāng)進程即將成為非活動狀態(tài)時，則發(fā)送一個確認消息給其父親進程。即當(dāng)：,,其局部終止條件滿足（即所有的任務(wù)被完成）,,它對已收到的任務(wù)都發(fā)送了確認消息,,對發(fā)出的任務(wù)都收到了確認消息,,一個進程必須在其父親進程之前成為非活動狀態(tài)；當(dāng)?shù)谝粋€進程成為空閑時，計算就終止了。,,進程,,非活動的,,活動的,,父親進程,第一個任務(wù),最后的確認,發(fā)送任務(wù),接收確認,用消息應(yīng)答實現(xiàn)

19、終止檢測,單環(huán)終止算法,,當(dāng),P0,已經(jīng)終止，它就發(fā)送一個標(biāo)記,(,令牌,token),給,P1,。,,當(dāng),Pi (1 .. i < n),收到發(fā)來的標(biāo)記，并且自己也已終止，則向,Pi+1,傳送一個標(biāo)記；否則，就等待局部終止條件滿足再向,Pi+1,傳送標(biāo)記。直到,Pn-1,將標(biāo)記發(fā)給,P0.,,當(dāng),P0,收到一個標(biāo)記時，它確信環(huán)上的所有進程已經(jīng)終止。如果必要的話，它向所有的進程發(fā)送一個消息通知他們?nèi)纸K止。,,該算法假設(shè)進程滿足局部終止條件后不會在被激活。它,不適合于,工作池的情況,—,即：一個進程可以將一個新任務(wù)傳送給一個處于空閑的進程。,環(huán)形終止算法,,P,0,,P,1,,P,2,,P,n

20、,,當(dāng)滿足本地終止條件時，將標(biāo)記傳給下一個進程,,,局部終止,,,AND,P,j,環(huán)形終止算法,雙環(huán)終止算法,----,可以處理進程再次被激活的情況，但需要對環(huán)進行兩次掃描。,,當(dāng)進程,Pi,要將任務(wù)傳給,Pj,，其中,j < i,，且,Pj,的結(jié)束標(biāo)記已傳出時，在這種情況下結(jié)束標(biāo)記就必須在整個環(huán)上再循環(huán)傳送一次。,,為了區(qū)分在不同的情況下傳送的結(jié)束標(biāo)記，我們將標(biāo)記著為白色和黑色。,,進程收到黑色標(biāo)記時意味著全局終止可能還沒有出現(xiàn)，標(biāo)記必須沿環(huán)重新傳送。,雙環(huán)終止算法,,當(dāng),P0,已經(jīng)滿足局部終止時，它變?yōu)榘咨?，并?P1,發(fā)送一個白色標(biāo)記。,,當(dāng)環(huán)上的某個進程已終止時，標(biāo)記就在環(huán)上從一個進程

21、傳向下一個進程，但標(biāo)記的顏色可能會發(fā)生改變。,,如果,Pi,向,Pj,傳送一個任務(wù),( j < i) (,即： 在環(huán)上,Pj,在,Pi,的前面,),，,Pi,就變?yōu)楹谏M程；否則，它為白色進程。,,黑色進程將會把要傳送的標(biāo)記變?yōu)楹谏?，并將其傳給下一個進程。白色進程將接收到的標(biāo)記（白色或黑色）往下傳遞。在,Pi,傳出標(biāo)記后，進程的顏色將變?yōu)榘咨?Pn-1,傳遞標(biāo)記給,P0.,雙環(huán)終止算法,(,續(xù),),,當(dāng),P0,收到一個黑色標(biāo)記時，它將一個白色標(biāo)記再次傳遞下去；如果它收到一個白色標(biāo)記，則所有的進程已終止，即全局終止。,,在上述兩種終止算法中，,P0,為全局終止條件的中心點。且假設(shè)每個請求將產(chǎn)生

22、一個應(yīng)答。,,P,0,,P,j,,P,i,,P,n,,任務(wù),,,,,,雙環(huán)終止算法的執(zhí)行,,P,i,,P,i,固定能量分布式終止算法,計算開始時，所有的能量僅由一個進程（根進程）擁有；,,隨后，根進程在下發(fā)任務(wù)的同時將部分能量也分給相應(yīng)的進程。,,如果進程收到了請求的任務(wù)和能量，它可以繼續(xù)將任務(wù)和它擁有的能量繼續(xù)下發(fā)給其它進程。,,如果進程處于空閑，則在請求新任務(wù)之前將自己的能量返回。,,一個進程只有收回它分發(fā)出去的全部能量時才將自己的能量歸還給其能量的進程。,,當(dāng)所有的能量返回到根進程且該進程處于空閑時，所有的進程必定也處于空閑，且全局計算可以終止。,三、負載平衡和終止檢測實例,--,最短路

23、徑問題,問題的描述：,,在給定的一個連通加權(quán)圖中，找出任意給定兩點,a,，,b,之間的最短路徑。即，,a,到,b,的路徑經(jīng)過的各邊權(quán)值之和最小。,B,E,D,C,A,F,,,,,,,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,用圖表示如下：,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,圖的表示：常用的方法有鄰接矩陣和鄰接列表,,鄰接矩陣：一個,2,維數(shù)組,a,，,a

24、[i, j],表示為圖中頂點,i,和頂點,j,之間的邊的有關(guān)數(shù)值。,10,8,14,9,17,13,24,51,A,,B,,C,,D,,E,,F,源,A B C D E F,目標(biāo),∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,鄰接列表：圖中每個頂點擁有一個鏈表，鏈表中各項保存著該頂點與其它頂點之間的邊的有關(guān)數(shù)值。,A,,B,,C,,D,,E,,F,源,,B 10,╳,,C 8,,D 14,╳,,E

25、 9,╳,,F 17,╳,,,╳,,D 13,,E 24,,F 51,╳,圖的搜索,常用的最短路徑算法有：,,Moore,的單源最短路徑算法,,Dijkstra,的單源最短路徑算法,,,Moore,算法更易于并行化,,要求權(quán)值為正數(shù),Moore,最短路徑算法,由源頂點開始，在考察頂點,i,時，方法如下：,,找出從源點經(jīng)過頂點,i,的頂點,j,的距離，并與當(dāng)前到頂點,j,的距離比較，求其最小值作為到頂點,j,的距離。即：,,假設(shè),d,i,為由源點到頂點,i,的當(dāng)前最小距離，,w,ij,為頂點,i,到頂點,j,的邊的權(quán)值。那么為由源點到頂點,j,的當(dāng)前最小距離為：,

26、,d,j,= min(,d,j,,,d,i,,+,w,ij,),Moore,最短路徑算法,,頂點,i,,頂點,j,d,i,w,ij,d,j,數(shù)據(jù)結(jié)構(gòu),建立一個先進先出的頂點隊列，用來存放將要被考察的頂點鏈表。最初，只有源頂點存放在該隊列中；,,從源頂點到頂點,i,的當(dāng)前最短路徑存放在數(shù)組,dist[i],中。最初，,dist,數(shù)組中各元素的值被賦值為,∞,。,,假設(shè),w,ij,為頂點,i,到頂點,j,的邊的權(quán)值，若兩頂點無邊，則權(quán)值為 ∞。,求當(dāng)前最短路徑的代碼：,Newdist_ j = dist[i] + w[i][j];,,if (newdist_ j < dist[j]) di

27、st[j] = newdist_ j;,,,當(dāng)頂點,j,發(fā)現(xiàn)了更短的路徑后，且頂點,j,不在頂點隊列中，就將頂點,j,加入到頂點隊列中。這將使頂點,j,重新被考察。,圖搜索的過程,兩個關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的初始狀態(tài)：,,,頂點隊列表,dist[ ],A,,,,,,0,∞,∞,∞,∞,∞,A B C D E F,,各頂點當(dāng)前最小距離,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,圖搜索的過程,在測試頂點,A,后：,,,頂點隊列表,dist[ ],B,,,,,,0,10,∞,∞,∞,∞,A B C D

28、 E F,Moore,算法對測試頂點的順序沒有要求。,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,圖搜索的過程,在測試頂點,B,后：,,,頂點隊列表,dist[ ],D,E,C,,,,0,10,18,23,34,61,A B C D E F,因,F,為終點，故不需要加,F,到頂點隊列中。,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,測試頂點,D,后：,,頂點隊列表,dist[ ],,,,,C,E,61,32,23,18,10,0,A B C

29、 D E F,測試頂點,E,后：,,頂點隊列表,dist[ ],,,,,,C,49,32,23,18,10,0,A B C D E F,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,測試頂點,C,后：,,頂點隊列表,dist[ ],,,,,,,49,32,23,18,10,0,A B C D E F,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,頂點可能重復(fù)進入頂點隊列的情

30、況：,頂點隊列表,dist[ ],,,,,,B,∞,∞,∞,∞,10,0,A B C D E F,頂點隊列表,dist[ ],,,,C,D,E,61,34,23,18,10,0,A B C D E F,頂點隊列表,dist[ ],,,,,C,D,51,34,23,18,10,0,A B C D E F,,,,,,A,∞,∞,∞,∞,∞,0,A B C D E F,頂點隊列表,dist[ ],頂點可能重復(fù)進

31、入頂點隊列的情況：,頂點隊列表,dist[ ],,,,,,E,51,32,23,18,10,0,A B C D E F,頂點隊列表,dist[ ],,,,,,,49,32,23,18,10,0,A B C D E F,,,,,E,C,51,32,23,18,10,0,A B C D E F,頂點隊列表,dist[ ],在,dist[ ],數(shù)組中存放著從源點到各個頂點的最小距離。,順序代碼：,設(shè),next_vertex( ),,返回頂點隊列中的下一個頂點或,no_vertex,

32、,假設(shè)利用名為,w[ ][ ],的相鄰矩陣,.,,while ((i = next_vertex()) != no_vertex) {,/*while a vertex*/,,for (j = 1; j < n; j++),/* get next edge */,,if (w[i][j] != infinity) {,/* if an edge */,,newdist_j = dist[i] + w[i][j];,,if (newdist_j < dist[j]) {,,dist[j] = newdist_j;,,append_queue(j);,/* add to queue if not

33、there */,,},,},,},/*no more to consider*/,集中式工作池,集中式工作池擁有頂點隊列,vertex_queue[ ],，其每個元素為一個任務(wù),,每個從進程從頂點隊列每次取一個頂點，并返回可能的新頂點,,由于相鄰矩陣的值始終不會改變，所以將相鄰矩陣拷貝給每一個從進程,,Dist[ ],存放在主進程的局部存儲器中,主進程代碼：,while (vertex_queue() != empty) {,,recv(P,ANY,, source = Pi);,/* request task from slave */,,v = get_vertex_queue();,,

34、send(,/* send next vertex and */,,send(,/* current dist array */,,recv(&j, &dist[j], P,ANY,, source = Pi);,/* new distance */,,append_queue(j, dist[j]);,/* append vertex to queue */,,},/* and update distance array */,,for (i=0; i

35、e */,,send(Pi, termination_tag);,/* termination message*/,,},從進程代碼：,send(P,master,);,/* send request for task */,recv(&v, P,master,, tag);,/* get vertex number */,if (tag != termination_tag) {,recv(&dist, &n, P,master,);,/* and dist array */,for (j = 1; j < n; j++),/* get next edge */,if (w[v][j] !=

36、 infinity) {,/* if an edge */,newdist_j = dist[v] + w[v][j];,if (newdist_j < dist[j]) {,dist[j] = newdist_j;,send(&j, &dist[j], P,master,);,/* add vertex to queue */,},/* send updated distance */,},},分散式工作池,從進程,P,i,僅圍繞頂點,v,i,搜索,,數(shù)組,dist[ ],將分散在各個從進程的局部存儲器中，它表示當(dāng)前從源點到頂點,v,i,的最小距離,,進程,P,i,也存放對頂點,v,i,的相

37、鄰矩陣（一行）,,搜索算法,頂點,A,是第一個被搜索的頂點，擁有頂點,A,的進程被激活；,,這個進程將搜索與其相連的頂點，尋找其距離；,,從頂點,A,到頂點,j,的距離將發(fā)給進程,j,，用來與進程,j,目前擁有的值進行比較和替換（如果當(dāng)前值較大）；,,以相同的方法，每個進程在搜索過程中最小距離在不斷被修改；,,如果,dist[i],的值被改變，進程,i,將再次被激活來重新搜索。,,主進程,,dist,,,w [ ],,,頂點,,進程,A,,dist,,,w [ ],,,頂點,,進程,B,源到,B,的新距離,,dist,,,w [ ],,,頂點,,進程,F,,dist,,,w [ ],,,頂點,

38、,進程,C,源到,C,的新距離,源到,F,的新距離,從源點開始,從進程,Pi,的代碼：,recv(newdist, P,ANY,);,if (newdist < dist) {,dist = newdist;,vertex_queue = TRUE;,/* add to queue */,} else vertex_queue == FALSE;,if (vertex_queue == TRUE),/*start searching around vertex*/,for (j = 1; j < n; j++),/* get next edge */,if (w[j] != infinity) {,d = dist + w[j];,send(,/* send distance to proc j */,},需考慮的具體問題：,進程收到消息后才有必要工作,----,使用同步消息傳遞；,,相應(yīng)的頂點被放到頂點隊列中后，進程才應(yīng)被激活，可能有許多進程處于未激活狀態(tài)，將導(dǎo)致算法低效的執(zhí)行；,,每個頂點對應(yīng)一個處理機不適應(yīng)頂點數(shù)目較大的情況,----,每個處理機分配一組頂點。,