并行計算負載平衡和終止檢測

并行計算負載平衡和終止檢測第1頁，課件共64頁，創(chuàng)作于2023年2月主要內(nèi)容負載平衡靜態(tài)負載平衡確定模式與非確定模式動態(tài)負載平衡集中式與分散式分布式終止檢測方法終止條件幾個終止檢測算法負載平衡和終止檢測實例第2頁，課件共64頁，創(chuàng)作于2023年2月主要內(nèi)容負載平衡靜態(tài)負載平衡確定模式與非確定模式動態(tài)負載平衡集中式與分散式分布式終止檢測方法終止條件幾個終止檢測算法負載平衡和終止檢測實例第3頁，課件共64頁，創(chuàng)作于2023年2月P1P0P2P3P4P5處理機time一、負載平衡靜態(tài)負載平衡動態(tài)負載平衡負載平衡time處理機P1P0P2P3P4P5第4頁，課件共64頁，創(chuàng)作于2023年2月負載平衡是利用調度程序實現(xiàn)的。調度的目的是通過將任務正確分配給各處理機，并使得任務按照一定的順序執(zhí)行，以盡可能少的時間完成并行應用任務。在靜態(tài)調度中，調度通常是在編譯時進行的。并行程序的特點（如：任務的執(zhí)行時間、通信、數(shù)據(jù)的相互關聯(lián)和同步等）在程序執(zhí)行之前都是已知的。在動態(tài)調度中，并行程序的特點在執(zhí)行之前往往知道得很少，因此，調度是在程序執(zhí)行時進行的。它使程序的執(zhí)行時間和調度時間盡可能最小。第5頁，課件共64頁，創(chuàng)作于2023年2月1.靜態(tài)負載平衡在任何進程執(zhí)行之前進行的負載平衡稱為靜態(tài)負載平衡。靜態(tài)負載平衡的優(yōu)點：一般情況下比動態(tài)負載平衡省時；一般情況下，靜態(tài)負載平衡在每個處理機上僅生成一個進程，從而減少了進程建立、同步和終止的開銷；可用來評估并行算法的加速比和性能。第6頁，課件共64頁，創(chuàng)作于2023年2月有向無回路圖(directedacyclicgraph)利用靜態(tài)調度的并行程序可由一個有向無回路圖G=(V,E)來表示，其中：V—節(jié)點的有限集合，一個節(jié)點表示一個子任務E—有向邊的有限集合，一個邊表示相連的節(jié)點的前驅限制節(jié)點的權值—計算開銷有向邊的權值—該邊相連的節(jié)點間的通信開銷T12T23T31T42T53T63T71105101546782第7頁，課件共64頁，創(chuàng)作于2023年2月靜態(tài)負載平衡確定模式：在此模式下，每個子任務所需的執(zhí)行時間和它們之間執(zhí)行的先后次序在任務運行前就已確定。非確定模式：在此模式下，每個子任務所需的執(zhí)行時間可表示為一個隨機變量。任務圖T12T23T31T42T53T63T71105101546782第8頁，課件共64頁，創(chuàng)作于2023年2月靜態(tài)負載平衡—確定模式一種簡化的情況：任務間沒有通信開銷，其調度可利用甘特圖(Ganttchart)來表示，它表示每個子任務的執(zhí)行時間和其執(zhí)行所在的處理機。該方法也稱為表調度，它生成一個調度列表。T12T23T31T42T53T63T71T7T5T2T1T6T3T4875429631time處理機第9頁，課件共64頁，創(chuàng)作于2023年2月靜態(tài)負載平衡—確定模式最優(yōu)調度—對給定一個任務圖和處理機數(shù)，使任務總的執(zhí)行時間最小化的調度。與最優(yōu)調度有關的一些結論：如果所有的子任務都需要一個單位時間，且任務圖是一個森林，則算法可在多項式時間內(nèi)找到最優(yōu)調度。如果子任務的執(zhí)行時間是不同的，或有兩個以上的處理機，則找最優(yōu)調度的問題是NP難的。這就意味著在最壞情況下，尋找最優(yōu)調度的已知的最好的算法需要指數(shù)時間。第10頁，課件共64頁，創(chuàng)作于2023年2月確定模式中要求被調度的任務中任何特點都不允許再改變，但在實際的任務調度過程中，某些任務的調度往往會影響到后繼任務的執(zhí)行時間的變化，使后繼任務的執(zhí)行和通信等產(chǎn)生一些變化。目前有很多基于動態(tài)列表調度方法的調度算法。與傳統(tǒng)方法相比，它們在每次分配任務之后都要重新計算所有未被調度節(jié)點的屬性，并利用這些新信息重新安排列表中節(jié)點的順序。靜態(tài)負載平衡—確定模式第11頁，課件共64頁，創(chuàng)作于2023年2月靜態(tài)負載平衡—確定模式基于動態(tài)列表調度方法的調度算法采用以下三個步驟：確定所有未被調度節(jié)點的新屬性；選擇具有最高優(yōu)先級的節(jié)點進行調度；將節(jié)點分配到使它的通信啟動時間最早的處理機上。第12頁，課件共64頁，創(chuàng)作于2023年2月在動態(tài)列表調度算法中“確定未被調度節(jié)點的新屬性”是計算這些節(jié)點的t-level和b-level值：節(jié)點Ti的t-level：從入口節(jié)點到Ti的一條最長的路徑；節(jié)點Ti的b-level：從Ti到出口節(jié)點的一條最長的路徑。T12T54T43T34T23T64T73T81411011111655第13頁，課件共64頁，創(chuàng)作于2023年2月T12T54T43T34T23T64T73T81411011111655節(jié)點t-levelb-levelT1023T2615T31211T4313T5314T61010T789T8221第14頁，課件共64頁，創(chuàng)作于2023年2月動態(tài)列表調度算法實現(xiàn)思想只用t-level的值的意義解釋算法在調度過程中，節(jié)點被調度之前，它的t-level是不斷變化的。t-level值之所以會發(fā)生變化是因為當一條邊所連接的兩個節(jié)點恰被分配到同一個處理機上時，這條邊的權值就會變?yōu)?。從而使這條路徑可能不是最長的結果。第15頁，課件共64頁，創(chuàng)作于2023年2月靜態(tài)負載平衡—非確定模式常用的靜態(tài)負載平衡技術還有：循環(huán)算法

—按進程順序分配任務，當所有的進程都得到了一個任務后，再從頭開始分配。隨機算法

—隨機地選擇進程并分配任務。遞歸二分法

—遞歸地將問題分為相等計算量的兩個子問題，并使其通信量最少。模擬退火(Simulatedannealing)—一種優(yōu)化技術遺傳算法(Geneticalgorithm)—一種優(yōu)化技術第16頁，課件共64頁，創(chuàng)作于2023年2月2.動態(tài)負載平衡在進程的執(zhí)行過程中完成的負載平衡。它是在應用程序運行期間對各節(jié)點間負載進行平衡的調度算法，它通過分析并行系統(tǒng)的實時負載信息，動態(tài)地將任務在各處理機之間進行分配和調整，以消除系統(tǒng)中負載分布的不均勻性。如：前面講的Mandelbrot集、熱分布問題等。雖然動態(tài)負載平衡會產(chǎn)生在執(zhí)行期間的額外開銷，但在負載不易均衡的情況下它比靜態(tài)負載平衡往往更有效。第17頁，課件共64頁，創(chuàng)作于2023年2月動態(tài)負載平衡集中式—任務是從一個中心位置分發(fā)的，通常是主從結構。分散式—任務通常在任意進程間進行傳遞。一組“工作者”進程根據(jù)問題進行操作，并彼此間進行交互，最后報告給一個單獨的進程。一個“工作者”進程可以從其它“工作者”進程接收任務，也可以將任務發(fā)給其它“工作者”進程，這些工作都由他們自己來決定。第18頁，課件共64頁，創(chuàng)作于2023年2月集中式動態(tài)負載平衡主進程擁有要被執(zhí)行的任務集。當從進程完成一個任務，向主進程請求另一個任務時，任務就由主進程發(fā)給從進程。如：工作池、處理機農(nóng)莊等。工作池主進程任務隊列從進程請求任務(可能提交一些新任務)發(fā)送任務第19頁，課件共64頁，創(chuàng)作于2023年2月當下列條件滿足時計算終止：任務隊列為空，且每個從進程都請求得到新的任務，但沒有被產(chǎn)生的新任務。當任務隊列為空時，且如果仍有進程運行，則此時終止條件不充分，這是因為運行的進程還可能產(chǎn)生新任務并放到任務隊列中。集中式動態(tài)負載平衡的計算終止第20頁，課件共64頁，創(chuàng)作于2023年2月分散式動態(tài)負載平衡分布式工作池進程M0主進程初始任務隊列任務子隊列任務子隊列進程Mn-1進程M0主進程初始任務隊列任務子隊列任務子隊列進程Mn-1第21頁，課件共64頁，創(chuàng)作于2023年2月分散式動態(tài)負載平衡全分布式工作池由接收者啟動方式—適合于高系統(tǒng)負載時由發(fā)送者啟動方式—適合于低系統(tǒng)負載時進程進程進程進程請求/任務第22頁，課件共64頁，創(chuàng)作于2023年2月使用線性結構實現(xiàn)動態(tài)負載平衡每個處理機上運行兩個進程用于左右兩邊的通信進程用于執(zhí)行當前任務的進程主進程P0P1P2P3Pn任務第23頁，課件共64頁，創(chuàng)作于2023年2月PcommPtask若緩沖區(qū)為空，則產(chǎn)生請求信號接收請求的任務如果Ptask空閑，則請求任務接收請求的任務請求任務若緩沖區(qū)滿，則發(fā)送任務第24頁，課件共64頁，創(chuàng)作于2023年2月實現(xiàn)通信和計算間的時間共享的代碼主進程P0：for(i=0;i<no_tasks;i++){recv(P1,request_tag);/*requestfortask*/

/*sendtasksintoqueue*/send(&task,P1,task_tag);}recv(P1,request_tag);/*requestfortask*/send(&empty,P1,task_tag);/*endoftasks*/第25頁，課件共64頁，創(chuàng)作于2023年2月從進程Pi(1

i<n)：if(buffer==empty){send(Pi-1,request_tag);/*requestnewtask*/recv(&buffer,Pi-1,task_tag);/*taskfromleftproc*/}if((buffer==full)&&(!busy)){/*getnexttask*/task=buffer;/*gettask*/buffer=empty;/*setbufferempty*/busy=TRUE;/*setprocessbusy*/}nrecv(Pi+1,request_tag,request);/*checkmsgfromright*/if(request&&(buffer==full)){send(&buffer,Pi+1);/*shifttaskforward*/buffer=empty;}if(busy){/*continueoncurrenttask*/Dosomeworkontask.Iftaskfinished,setbusytofalse.}第26頁，課件共64頁，創(chuàng)作于2023年2月必須對右邊接收的請求使用非阻塞recv—nrecv，當nrecv收到了請求消息后，會將參數(shù)request置為TRUE。MPI中非阻塞接收例程MPI_Irecv()，這個函數(shù)比阻塞操作只多一個參數(shù)：

MPI_Request*request這個函數(shù)的調用將分配一個通信請求對象，把它和參數(shù)request連接。之后，request能被用于查尋這個通信的狀態(tài)或等待它的完成。函數(shù)MPI_WAIT和MPI_TEST用于完成和查詢一個非阻塞通信。第27頁，課件共64頁，創(chuàng)作于2023年2月二、分布式終止檢測算法終止條件使用消息應答實現(xiàn)終止檢測環(huán)形終止算法固定能量分布式終止算法第28頁，課件共64頁，創(chuàng)作于2023年2月終止條件在時間t時需要滿足下列條件：在時間t時，對所有的進程滿足局部應用終止的條件；在時間t時，沒有消息在進程間傳遞。分布式終止條件與集中式終止條件之間存在著一些差別：需要考慮被傳遞的消息。考察是否還有被傳遞的消息不是一件容易的事情，因為消息在進程間傳送的時間預先是不知道的。第29頁，課件共64頁，創(chuàng)作于2023年2月一個常見的分布式終止算法—

使用消息應答實現(xiàn)終止檢測每個進程處于下面兩種狀態(tài)之一：非活動的(inactive)–沒有任何任務要執(zhí)行活動的(active)發(fā)送一個任務使某個進程處于活動狀態(tài)的進程稱為被激活進程的“父親”進程。當進程收到一個任務（未必是其父親發(fā)來的任務）時，除了進程接收的任務來自其父親進程外，它必須馬上發(fā)送一個確認消息。每個進程有唯一的父親進程。第30頁，課件共64頁，創(chuàng)作于2023年2月當進程即將成為非活動狀態(tài)時，則發(fā)送一個確認消息給其父親進程。即當：其局部終止條件滿足（即所有的任務被完成）它對已收到的任務都發(fā)送了確認消息對發(fā)出的任務都收到了確認消息一個進程必須在其父親進程之前成為非活動狀態(tài)；當?shù)谝粋€進程成為空閑時，計算就終止了。第31頁，課件共64頁，創(chuàng)作于2023年2月進程非活動的活動的父親進程第一個任務最后的確認發(fā)送任務接收確認用消息應答實現(xiàn)終止檢測第32頁，課件共64頁，創(chuàng)作于2023年2月單環(huán)終止算法當P0已經(jīng)終止，它就發(fā)送一個標記(令牌token)給P1。當Pi(1..i<n)收到發(fā)來的標記，并且自己也已終止，則向Pi+1傳送一個標記；否則，就等待局部終止條件滿足再向Pi+1傳送標記。直到Pn-1將標記發(fā)給P0.當P0收到一個標記時，它確信環(huán)上的所有進程已經(jīng)終止。如果必要的話，它向所有的進程發(fā)送一個消息通知他們?nèi)纸K止。該算法假設進程滿足局部終止條件后不會在被激活。它不適合于工作池的情況—即：一個進程可以將一個新任務傳送給一個處于空閑的進程。環(huán)形終止算法第33頁，課件共64頁，創(chuàng)作于2023年2月P0P1P2Pn當滿足本地終止條件時，將標記傳給下一個進程局部終止ANDPj第34頁，課件共64頁，創(chuàng)作于2023年2月環(huán)形終止算法雙環(huán)終止算法----可以處理進程再次被激活的情況，但需要對環(huán)進行兩次掃描。當進程Pi要將任務傳給Pj，其中j<i，且Pj的結束標記已傳出時，在這種情況下結束標記就必須在整個環(huán)上再循環(huán)傳送一次。為了區(qū)分在不同的情況下傳送的結束標記，我們將標記著為白色和黑色。進程收到黑色標記時意味著全局終止可能還沒有出現(xiàn)，標記必須沿環(huán)重新傳送。第35頁，課件共64頁，創(chuàng)作于2023年2月雙環(huán)終止算法當P0已經(jīng)滿足局部終止時，它變?yōu)榘咨?，并向P1發(fā)送一個白色標記。當環(huán)上的某個進程已終止時，標記就在環(huán)上從一個進程傳向下一個進程，但標記的顏色可能會發(fā)生改變。如果Pi向Pj傳送一個任務(j<i)(即：在環(huán)上Pj在Pi的前面)，Pi就變?yōu)楹谏M程；否則，它為白色進程。黑色進程將會把要傳送的標記變?yōu)楹谏?，并將其傳給下一個進程。白色進程將接收到的標記（白色或黑色）往下傳遞。在Pi傳出標記后，進程的顏色將變?yōu)榘咨?。Pn-1傳遞標記給P0.第36頁，課件共64頁，創(chuàng)作于2023年2月雙環(huán)終止算法(續(xù))當P0收到一個黑色標記時，它將一個白色標記再次傳遞下去；如果它收到一個白色標記，則所有的進程已終止，即全局終止。在上述兩種終止算法中，P0為全局終止條件的中心點。且假設每個請求將產(chǎn)生一個應答。第37頁，課件共64頁，創(chuàng)作于2023年2月P0PjPiPn任務雙環(huán)終止算法的執(zhí)行PiPi第38頁，課件共64頁，創(chuàng)作于2023年2月固定能量分布式終止算法計算開始時，所有的能量僅由一個進程（根進程）擁有；隨后，根進程在下發(fā)任務的同時將部分能量也分給相應的進程。如果進程收到了請求的任務和能量，它可以繼續(xù)將任務和它擁有的能量繼續(xù)下發(fā)給其它進程。如果進程處于空閑，則在請求新任務之前將自己的能量返回。一個進程只有收回它分發(fā)出去的全部能量時才將自己的能量歸還給其能量的進程。當所有的能量返回到根進程且該進程處于空閑時，所有的進程必定也處于空閑，且全局計算可以終止。第39頁，課件共64頁，創(chuàng)作于2023年2月三、負載平衡和終止檢測實例--

最短路徑問題問題的描述：在給定的一個連通加權圖中，找出任意給定兩點a，b之間的最短路徑。即，a到b的路徑經(jīng)過的各邊權值之和最小。BEDCAF第40頁，課件共64頁，創(chuàng)作于2023年2月ABCDEF10179148512413ABCDEF10179148512413ABCDEF10179148512413用圖表示如下：ABCDEF10179148512413第41頁，課件共64頁，創(chuàng)作于2023年2月圖的表示：常用的方法有鄰接矩陣和鄰接列表鄰接矩陣：一個2維數(shù)組a，a[i,j]表示為圖中頂點i和頂點j之間的邊的有關數(shù)值。10814917132451ABCDEF源ABCDEF目標∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ABCDEF10179148512413第42頁，課件共64頁，創(chuàng)作于2023年2月鄰接列表：圖中每個頂點擁有一個鏈表，鏈表中各項保存著該頂點與其它頂點之間的邊的有關數(shù)值。ABCDEF源B10╳C8D14╳E9╳F17╳╳D13E24F51╳第43頁，課件共64頁，創(chuàng)作于2023年2月圖的搜索常用的最短路徑算法有：Moore的單源最短路徑算法Dijkstra的單源最短路徑算法Moore算法更易于并行化要求權值為正數(shù)第44頁，課件共64頁，創(chuàng)作于2023年2月Moore最短路徑算法由源頂點開始，在考察頂點i時，方法如下：找出從源點經(jīng)過頂點i的頂點j的距離，并與當前到頂點j的距離比較，求其最小值作為到頂點j的距離。即：假設di為由源點到頂點i的當前最小距離，wij為頂點i到頂點j的邊的權值。那么為由源點到頂點j的當前最小距離為：dj=min(dj,di

+wij)第45頁，課件共64頁，創(chuàng)作于2023年2月Moore最短路徑算法頂點i頂點jdiwijdj第46頁，課件共64頁，創(chuàng)作于2023年2月數(shù)據(jù)結構建立一個先進先出的頂點隊列，用來存放將要被考察的頂點鏈表。最初，只有源頂點存放在該隊列中；從源頂點到頂點i的當前最短路徑存放在數(shù)組dist[i]中。最初，dist數(shù)組中各元素的值被賦值為∞。假設wij為頂點i到頂點j的邊的權值，若兩頂點無邊，則權值為∞。第47頁，課件共64頁，創(chuàng)作于2023年2月求當前最短路徑的代碼：Newdist_j=dist[i]+w[i][j];if(newdist_j<dist[j])dist[j]=newdist_j;當頂點j發(fā)現(xiàn)了更短的路徑后，且頂點j不在頂點隊列中，就將頂點j加入到頂點隊列中。這將使頂點j重新被考察。第48頁，課件共64頁，創(chuàng)作于2023年2月圖搜索的過程兩個關鍵數(shù)據(jù)結構的初始狀態(tài)：頂點隊列表dist[]A0∞∞∞∞∞ABCDEF各頂點當前最小距離ABCDEF10179148512413第49頁，課件共64頁，創(chuàng)作于2023年2月圖搜索的過程在測試頂點A后：頂點隊列表dist[]B010∞∞∞∞ABCDEFMoore算法對測試頂點的順序沒有要求。ABCDEF10179148512413第50頁，課件共64頁，創(chuàng)作于2023年2月圖搜索的過程在測試頂點B后：頂點隊列表dist[]DEC01018233461ABCDEF因F為終點，故不需要加F到頂點隊列中。ABCDEF10179148512413第51頁，課件共64頁，創(chuàng)作于2023年2月測試頂點D后：頂點隊列表dist[]CE61322318100ABCDEF測試頂點E后：頂點隊列表dist[]C49322318100ABCDEFABCDEF10179148512413第52頁，課件共64頁，創(chuàng)作于2023年2月測試頂點C后：頂點隊列表dist[]49322318100ABCDEFABCDEF10179148512413第53頁，課件共64頁，創(chuàng)作于2023年2月頂點可能重復進入頂點隊列的情況：頂點隊列表dist[]B∞∞∞∞100ABCDEF頂點隊列表dist[]CDE61342318100ABCDEF頂點隊列表dist[]CD51342318100ABCDEFA∞∞∞∞∞0ABCDEF頂點隊列表dist[]第54頁，課件共64頁，創(chuàng)作于2023年2月頂點可能重復進入頂點隊列的情況：頂點隊列表dist[]E51322318100ABCDEF頂點隊列表dist[]49322318100ABCDEFEC51322318100ABCDEF頂點隊列表dist[]在dist[]數(shù)組中存放著從源點到各個頂點的最小距離。第55頁，課件共64頁，創(chuàng)作于2023年2月順序代碼：設next_vertex()返回頂點隊列中的下一個頂點或no_vertex假設利用名為w[][]的相鄰矩陣.while((i=next_vertex())!=no_vertex){/*whileavertex*/for(j=1;j<n;j++)/*getnextedge*/if(w[i][j]!=infinity){/*ifanedge*/newdist_j=dist[i]+w[i][j];if(newdist_j<dist[j]){dist[j]=newdist_j;append_queue(j);/*addtoqueueifnotthere*/}}}/*nomoretoconsider*/第56頁，課件共64頁，創(chuàng)作于2023年2月集中式工作池集中式工作池擁有頂點隊列vertex_queue[]，其每個元素為一個任務每個從進程從頂點隊列每次取一個頂點，并返回可能的新頂點由于相鄰矩陣的值始終不會改變，所以將相鄰矩陣拷貝給每一個從進程Dist[]存放在主進程的局部存儲器中第57頁，課件共64頁，創(chuàng)作于2023年2月主進程代碼：while(vertex_queue()!=empty){recv(PANY,source=Pi);/*requesttaskfromslave*/v=get_vertex_queue();send(&v,Pi);/*sendnextvertexand*/send(&dist,&n,Pi);/*currentdistarray*/recv(&j,&dist[j],PANY,source=Pi);/*newdistance*/append_queue(j,dist[j]);/*appendvertextoqueue*/}/*andupdatedistancearray*/for(i=0;i<slave-no;i++){recv(PANY,source=Pi);/*requesttaskfromslave*/send(Pi,termination_tag);/*terminationmessage*/}第58頁，課件共64頁，創(chuàng)作于2023年2月從進程代碼：send(Pmaster);/*sendrequestfortask*/recv(&v,Pmaster,tag);/*getvertexnumber*/if(tag!=termination_tag){recv(&dist,&n,Pmaster);/*anddistarray*/for(j=1;j<n;j++)/*getnextedge*/if(w[v][j]!=infinity){