并行計(jì)算負(fù)載平衡和終止檢測(cè)

《并行計(jì)算負(fù)載平衡和終止檢測(cè)》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算負(fù)載平衡和終止檢測(cè)（64頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

4、度的并行程序可由一個(gè)有向無(wú)回路圖,G=(V,E),來(lái)表示，其中：,,V—,節(jié)點(diǎn)的有限集合，一個(gè)節(jié)點(diǎn)表示一個(gè)子任務(wù),,E—,有向邊的有限集合，一個(gè)邊表示相連的節(jié)點(diǎn)的前驅(qū)限制,,節(jié)點(diǎn)的權(quán)值,—,計(jì)算開(kāi)銷,,有向邊的權(quán)值,—,該邊相連的節(jié)點(diǎn)間的通信開(kāi)銷,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)負(fù)載平衡,,確定模式：在此模式下，每個(gè)子任務(wù)所需的執(zhí)行時(shí)間和它們之間執(zhí)行的先后次序在任務(wù)運(yùn)行前就已確定。,,非確定模式：在此模式下，每個(gè)子任務(wù)所需的執(zhí)行時(shí)間可表示為一個(gè)隨機(jī)變量。,任務(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)負(fù)載平衡,—,確定模式,一種簡(jiǎn)化的情況：任務(wù)間沒(méi)有通信開(kāi)銷，其調(diào)度可利用甘特圖,(Gantt chart),來(lái)表示，它表示每個(gè)子任務(wù)的執(zhí)行時(shí)間和其執(zhí)行所在的處理機(jī)。,,該方法也稱為,表調(diào)度,，它生成一個(gè)調(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,處 理 機(jī),靜態(tài)負(fù)載平衡,—,確定模式,最優(yōu)

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

7、每次分配任務(wù)之后都要重新計(jì)算所有未被調(diào)度節(jié)點(diǎn)的屬性，并利用這些新信息重新安排列表中節(jié)點(diǎn)的順序。,靜態(tài)負(fù)載平衡,—,確定模式,靜態(tài)負(fù)載平衡,—,確定模式,基于動(dòng)態(tài)列表調(diào)度方法的調(diào)度算法采用以下三個(gè)步驟：,,確定所有未被調(diào)度節(jié)點(diǎn)的新屬性；,,選擇具有最高優(yōu)先級(jí)的節(jié)點(diǎn)進(jìn)行調(diào)度；,,將節(jié)點(diǎn)分配到使它的通信啟動(dòng)時(shí)間,最早的,處理機(jī)上。,在動(dòng)態(tài)列表調(diào)度算法中“確定未被調(diào)度節(jié)點(diǎn)的新屬性”是計(jì)算這些節(jié)點(diǎn)的,t-level,和,b-level,值：,,節(jié)點(diǎn),Ti,的,t-level,：從入口節(jié)點(diǎn)到,Ti,的一條最長(zhǎng)的路徑；,,節(jié)點(diǎn),Ti,的,b-level,：從,Ti,到出口節(jié)點(diǎn)的一條最長(zhǎng)的路徑。,,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é)點(diǎn),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,動(dòng)態(tài)列表調(diào)度算法實(shí)現(xiàn)思想,只用,t-level,的值的意義解釋算法,,在調(diào)度過(guò)程中，節(jié)點(diǎn)被調(diào)度之前，它的,t-level,是不斷

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

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

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

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

13、,,P,task,若緩沖區(qū)為空，則產(chǎn)生請(qǐng)求信號(hào),接收請(qǐng)求的任務(wù),如果,P,task,空閑，則請(qǐng)求任務(wù),接收請(qǐng)求的任務(wù),,請(qǐng)求任務(wù),若緩沖區(qū)滿，則發(fā)送任務(wù),實(shí)現(xiàn)通信和計(jì)算間的時(shí)間共享的代碼,主進(jì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 */,從進(jìn)程,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.,,},必須對(duì)右邊接收的請(qǐng)求使用非阻塞,recv — nrecv,，當(dāng),nrecv,收到了請(qǐng)求消息后，會(huì)將參數(shù),request,置為,TRUE,。,,MPI,中非阻塞接收例程,MPI_Irecv( ),，,這個(gè)函數(shù)比阻塞操作只多一個(gè)參數(shù)：,,,MPI_Request *request,,這個(gè)函數(shù)的調(diào)用將分配一個(gè)通信請(qǐng)求對(duì)象，把它和參數(shù),request,連接。之后，,request,能被用于查尋這個(gè)通信的狀態(tài)或等待它的完成。,,函數(shù),MPI_WAIT,和,MPI_TEST,用于完成和查詢一

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

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

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

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

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

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

23、徑問(wèn)題,問(wèn)題的描述：,,在給定的一個(gè)連通加權(quán)圖中，找出任意給定兩點(diǎn),a,，,b,之間的最短路徑。即，,a,到,b,的路徑經(jīng)過(guò)的各邊權(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,圖的表示：常用的方法有鄰接矩陣和鄰接列表,,鄰接矩陣：一個(gè),2,維數(shù)組,a,，,a

24、[i, j],表示為圖中頂點(diǎn),i,和頂點(diǎn),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,鄰接列表：圖中每個(gè)頂點(diǎn)擁有一個(gè)鏈表，鏈表中各項(xiàng)保存著該頂點(diǎn)與其它頂點(diǎn)之間的邊的有關(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,最短路徑算法,由源頂點(diǎn)開(kāi)始，在考察頂點(diǎn),i,時(shí)，方法如下：,,找出從源點(diǎn)經(jīng)過(guò)頂點(diǎn),i,的頂點(diǎn),j,的距離，并與當(dāng)前到頂點(diǎn),j,的距離比較，求其最小值作為到頂點(diǎn),j,的距離。即：,,假設(shè),d,i,為由源點(diǎn)到頂點(diǎn),i,的當(dāng)前最小距離，,w,ij,為頂點(diǎn),i,到頂點(diǎn),j,的邊的權(quán)值。那么為由源點(diǎn)到頂點(diǎn),j,的當(dāng)前最小距離為：,

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

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

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

29、 D E F,測(cè)試頂點(diǎn),E,后：,,頂點(diǎn)隊(duì)列表,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è)試頂點(diǎn),C,后：,,頂點(diǎn)隊(duì)列表,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,頂點(diǎn)可能重復(fù)進(jìn)入頂點(diǎn)隊(duì)列的情

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

31、入頂點(diǎn)隊(duì)列的情況：,頂點(diǎn)隊(duì)列表,dist[ ],,,,,,E,51,32,23,18,10,0,A B C D E F,頂點(diǎn)隊(duì)列表,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,頂點(diǎn)隊(duì)列表,dist[ ],在,dist[ ],數(shù)組中存放著從源點(diǎn)到各個(gè)頂點(diǎn)的最小距離。,順序代碼：,設(shè),next_vertex( ),,返回頂點(diǎn)隊(duì)列中的下一個(gè)頂點(diǎn)或,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*/,集中式工作池,集中式工作池?fù)碛许旤c(diǎn)隊(duì)列,vertex_queue[ ],，其每個(gè)元素為一個(gè)任務(wù),,每個(gè)從進(jìn)程從頂點(diǎn)隊(duì)列每次取一個(gè)頂點(diǎn)，并返回可能的新頂點(diǎn),,由于相鄰矩陣的值始終不會(huì)改變，所以將相鄰矩陣拷貝給每一個(gè)從進(jìn)程,,Dist[ ],存放在主進(jìn)程的局部存儲(chǔ)器中,主進(jìn)程代碼：,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*/,,},從進(jìn)程代碼：,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 */,},},分散式工作池,從進(jìn)程,P,i,僅圍繞頂點(diǎn),v,i,搜索,,數(shù)組,dist[ ],將分散在各個(gè)從進(jìn)程的局部存儲(chǔ)器中，它表示當(dāng)前從源點(diǎn)到頂點(diǎn),v,i,的最小距離,,進(jìn)程,P,i,也存放對(duì)頂點(diǎn),v,i,的相

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

38、,進(jìn)程,C,源到,C,的新距離,源到,F,的新距離,從源點(diǎn)開(kāi)始,從進(jìn)程,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 */,},需考慮的具體問(wèn)題：,進(jìn)程收到消息后才有必要工作,----,使用同步消息傳遞；,,相應(yīng)的頂點(diǎn)被放到頂點(diǎn)隊(duì)列中后，進(jìn)程才應(yīng)被激活，可能有許多進(jìn)程處于未激活狀態(tài)，將導(dǎo)致算法低效的執(zhí)行；,,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)處理機(jī)不適應(yīng)頂點(diǎn)數(shù)目較大的情況,----,每個(gè)處理機(jī)分配一組頂點(diǎn)。,