吉林大學研究所課程-并行計算課件-第5章-分布式調度

1、第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的分類調度算法的分類 調度算法 局部調度 全局調度 靜態(tài)調度 動態(tài)調度 分散式調度 集中式調度 協(xié)作式調度 非協(xié)作式調度 優(yōu)化調度 次優(yōu)化調度 近似調度 啟發(fā)式調度 優(yōu)化調度 次優(yōu)化調度 近似調度 啟發(fā)式調度 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的分類調度算法的分類 其他一些分類方法其他一些分類方法 ：(1) 非搶先式的(non-preemptive)和搶先式的(preemptive)。對非搶先式的調度算法，一個進程開始執(zhí)行后就不能中斷。在搶先式調度算

2、法中，進程可以中斷，從一個處理機上移走，到另一個處理機上繼續(xù)執(zhí)行。 (2) 適應性(adaptive)和非適應性的(non-adaptive)。非適應性調度算法只使用一種負載分配策略，不會根據(jù)系統(tǒng)的反饋而改變自己的行為。適應性調度算法能夠根據(jù)系統(tǒng)的反饋調整自己的行為，采用不同的負載分配策略。典型地，一個適應性調度算法是許多種調度算法的集合，根據(jù)系統(tǒng)的各種參數(shù)來選擇一種合適的算法。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 分布式調度的基本目標分布式調度的基本目標是盡快得到計算結果和有效地利用資源。具體

3、來說，調度算法的目標有兩個：一個目標是負載平衡(load balancing)，它的努力目標是維持整個分布式系統(tǒng)中各個資源上的負載大致相同。另一種目標是負載共享(load sharing)，它的目標僅僅是防止某個處理機上的負載過重。相對來說負載共享的目標要比負載平衡的目標容易達到。負載平衡的主要目的是提高整個系統(tǒng)的流量，而負載共享的主要目標是縮短特定程序的執(zhí)行時間。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 從調度算法的有效性來看，調度算法分為最優(yōu)調度算法和次優(yōu)調度算法。為了實現(xiàn)最優(yōu)調度算法，調度者必

4、須獲得所有進程的狀態(tài)信息和系統(tǒng)中所有相關的可用信息。最優(yōu)性常用執(zhí)行時間、資源利用率、系統(tǒng)流量以及這些參數(shù)的某種綜合來進行評價。一般來說最優(yōu)調度是一個NP完全性問題。所以在實際的系統(tǒng)中，常采用次優(yōu)的調度算法。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 有許多參數(shù)用于確定或測量一個調度算法的有效性：有許多參數(shù)用于確定或測量一個調度算法的有效性：通信代價：通信代價：使用這個參數(shù)的調度算法可能要考慮到向一個給定的節(jié)點傳送或者從一個給定節(jié)點接收一個報文花費的時間，更為重要的是必須考慮到為一個進程分配一個執(zhí)行地點

5、而引起的通信代價。 執(zhí)行代價：執(zhí)行代價：這個參數(shù)反映的是將一個進程分配到一個指定的執(zhí)行節(jié)點，在這個節(jié)點的執(zhí)行環(huán)境下，執(zhí)行這個程序所需的額外開銷。資源利用率：資源利用率：常用來表明基于分布式系統(tǒng)當前各個節(jié)點的負載情況，給一個進程分配的執(zhí)行節(jié)點是否是合適的。資源利用率參數(shù)常用負載狀態(tài)來表示，常用的負載參數(shù)有資源的隊列長度、內(nèi)存的使用等等。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 次優(yōu)的調度算法分為兩類：近似的次優(yōu)調度算法和啟發(fā)式的次次優(yōu)的調度算法分為兩類：近似的次優(yōu)調度算法和啟發(fā)式的次優(yōu)調度算法：優(yōu)調度

6、算法：近似的次優(yōu)調度常和最優(yōu)調度使用相同的算法，但是近似的次優(yōu)調度不搜索這個算法的所有解空間，而是在這個算法的解空間中的一個子集中搜索，目的是盡快地找到一個較好的解。而最優(yōu)調度則是搜索這個算法的整個解空間，目的是獲得最好的解。使用近似的次優(yōu)調度算法必須能夠判定所得到的解是否是可以被接受的，也就是說，必須能夠確定最優(yōu)解和次優(yōu)解之間的近似程度。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 次優(yōu)的調度算法分為兩類：近似的次優(yōu)調度算法和啟發(fā)式的次次優(yōu)的調度算法分為兩類：近似的次優(yōu)調度算法和啟發(fā)式的次優(yōu)調度算法：

7、優(yōu)調度算法：啟發(fā)式的次優(yōu)調度算法常使用比較簡明的規(guī)則和一些直覺的規(guī)則來進行調度。這些啟發(fā)式的規(guī)則往往是不能證明其正確性，在特定情況下可能還是錯誤的，但是在絕大多數(shù)的情況下是能夠被接受的。 第第5 5章章 分布式調度分布式調度 5.1 5.1 調度算法概述調度算法概述 v調度算法的目標和有效性評價調度算法的目標和有效性評價 啟發(fā)式調度算法中常采用的一些啟發(fā)式規(guī)則：啟發(fā)式調度算法中常采用的一些啟發(fā)式規(guī)則： 相互依賴性較大的進程，由于它們之間常有比較多的進程通信應該分配到比較接近的執(zhí)行節(jié)點上，可能的話，應該在同一個節(jié)點上。 訪問共享文件的進程應該分配到比較接近的執(zhí)行節(jié)點上，可能的話，應該分配在文件服

8、務員節(jié)點上。 很少有內(nèi)在關系的進程可以分布在不同的機器上。 如果一個節(jié)點已經(jīng)是重負載的，不應該向該節(jié)點分配另外一個進程。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 設計調度策略時要考慮的三個主要因素：設計調度策略時要考慮的三個主要因素：靜態(tài)調度算法的目標是調度一個任務集合，使它們在各個目標節(jié)點上有最短的執(zhí)行時間?？傮w上來說，設計調度策略時要考慮的三個主要因素是處理機的互連、任務的劃分和任務的分配。通常用圖模型表示任務和處理機的結構。我們可以用任務優(yōu)先圖和任務交互作用圖對任務集合建模。 任務優(yōu)先圖任務優(yōu)先圖是一個有向無環(huán)圖(DAG)，圖中每個鏈接定義了任務間的優(yōu)先關

9、系，節(jié)點和鏈接上的標記表示任務的執(zhí)行時間和任務完成后啟動后續(xù)任務所需的時間間隔。任務交互作用圖任務交互作用圖中，鏈接定義了兩個任務間的相互關系，每個鏈接賦予一對數(shù)，分別表示這兩個任務在同一個處理機上時的通信開銷和在不同處理機上時的通信開銷。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5 (a) 任務優(yōu)先圖 2 3 4 2 3 T1 T2 T3 T4 T5 1,4 1,5 1,4 1,3 1,5 1,4 (b) 任務相互作用圖 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v

10、任務劃分與分配任務劃分與分配 任務劃分的粒度：任務劃分的粒度：一個給定任務劃分的粒度被定義為任務的計算量與通信量的比值。如果粒度太大，就會限制并行性，因為潛在的并行任務可能被劃分進同一個任務而分配給一個處理器。粒度太小，進程切換和通信的開銷就會增加，從而降低性能。 任務聚類：任務聚類：在圖模型中，任務的劃分被稱作任務聚類，即在給定的圖模型中對小任務進行分類。任務劃分把任務圖當作一個整體，將圖中的小任務(節(jié)點)劃分成不同的聚類，聚類中的小任務串行執(zhí)行，不同的聚類之間并行執(zhí)行。任務聚類中可以使用兩種策略： (1) 將不相關的任務映射到一個聚類中； (2) 將DAG中一條優(yōu)先路徑上的任務映射到一個聚

11、類中。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v任務劃分與分配任務劃分與分配 一些劃分算法 ：(1) (1) 關鍵路徑劃分。關鍵路徑劃分。關鍵路徑(最長路徑)的概念常常在垂直劃分中使用，即用在線性聚類中。應該清楚的是，依賴于任務優(yōu)先圖中關鍵路徑的細粒度任務必須串行執(zhí)行。(2) (2) 消除通信延遲的劃分。消除通信延遲的劃分。這個方法的關鍵之處在于消除通信的額外開銷，所以要把通信頻繁的節(jié)點聚集成一類。通常的方法是將一個節(jié)點的后繼節(jié)點與節(jié)點自身聚集成一類，只要總的執(zhí)行時間不會被延長。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v任務劃

12、分與分配任務劃分與分配 關鍵路徑劃分的例子關鍵路徑劃分的例子132457964252472T1T2T5T3T6T4T7消除通信延遲的劃分消除通信延遲的劃分133112T2T3T4T5T63133312T1第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v任務劃分與分配任務劃分與分配 一些劃分算法 ：(3) (3) 任務復制。任務復制。為了消除任務間的通信開銷，將任務在處理機上進行復制有時是最有效的方法。它是任務劃分的一個可選方法。任務復制不僅能保留程序最初的并行性，同時也能減少通信開銷。 (4) (4) 其他技術。其他技術。Kim和Browne的線性聚類技術，在每一步，

13、計算量和通信量最大的有向路徑上的節(jié)點聚集成一個單獨的線性聚類，并且這些節(jié)點被從圖中除去。對圖中剩余的節(jié)點迭代執(zhí)行這個過程，直到整個任務圖已經(jīng)全部被劃分成一些聚類。Sarkar的內(nèi)在化聚類方案，將每個節(jié)點最初放在一個單獨的聚類中，并且以弧上通信開銷的下降順序考慮將圖中的節(jié)點劃分成一些聚類。這個算法不斷地將兩個聚類合并成一個更大的聚類，如果在合并過程中生成的更大聚類不會增加這個圖的估計并行執(zhí)行時間，那么這個合并過程就被接受。這個過程一直進行下去，直到不再需要合并為止。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v任務劃分與分配任務劃分與分配 1 3 2 4 5 7 9

14、 6 4 2 5 2 4 7 2 T1 T2 T5 T3 T6 T4 T7 時間 處理機 1 處理機 2 處理機 3 1 T1 T1 T1 2 T2 T3 T4 4 T2 T2 T4 5 T3 T2 T4 6 T3 T2 T2 7 T5 T6 T2 9 T5 T6 T7 任務復制：第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 甘特圖甘特圖(gantt chart)能夠最有效描述進程對處理器的分配情況。甘特圖以處理器為縱坐標，以時間為橫坐標。圖中的每個方塊表示進程在某個系統(tǒng)中的開始時間、持續(xù)時間和結束時間。處理器內(nèi)的時

15、間延遲和處理器間的時間延遲都能夠在圖中體現(xiàn)。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5 (a) 任務優(yōu)先圖 (b) 甘特圖 時間 處理器 P1 P2 T1 0 2 T2 3 T3 T4 7 T5 12 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 通信延遲和任務復制對調度的影響： T1 T2 T3 d d 時間 處理器 P1 P2 T1 T1 T2 T3 時間 處理器

16、 P1 P2 T1 T2 T3 時間 P1 P2 處理器 T1 T2 T3 d (a) 任務優(yōu)先圖 (b) 使用任務復制的調度 (c) 任務分配在一個處理器上 (d) 通信延遲對調度的影響 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 線性聚類與非線性聚類：線性聚類與非線性聚類：如果至少有一個聚類中包含兩個獨立的任務，則聚類是非線性的；否則，聚類就是線性的。 4 3 2 T1 T2 T3 1 1 4 3 2 T1 T2 T3 1 1 (a) 線性聚類 (b) 非線性聚類 第第5 5章章 分布式調度分布式調度 5.2

17、5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 一個任務優(yōu)先圖可以認為是許多分叉和合并操作的集合，分叉x(合并x)的粒度是：max/min)(11knkknklCxg x C1 C2 Cn V1 V2 Vn l1 l2 ln x C1 C2 Cn V1 V2 Vn l1 l2 ln (a) 分叉操作 (b) 合并操作 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務優(yōu)先圖的任務調度基于任務優(yōu)先圖的任務調度 給定任務優(yōu)先圖給定任務優(yōu)先圖G G的粒度是的粒度是： )(min)(xgGgGx如果g(x)1，合并x或分叉x就是粗粒度；否則

18、就是細粒度。同樣如果g(G)1，圖G就是粗粒度，否則就是細粒度。當表示一個應用程序的給定的有向無環(huán)圖DAG(任務優(yōu)先圖)是粗粒度時，也就是它的一個鏈接上的通信代價小于分叉或者合并操作連接的相鄰節(jié)點的計算代價，任何非線性聚類可以被轉換成具有更少或相等執(zhí)行時間的線性聚類。注意，上面的結論暗示了一個粗粒度程序的線性聚類性能優(yōu)于任何非線性聚類。然而，對細粒度程序而言，可能存在也可能不存在一個非線性聚類優(yōu)于線性聚類。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v兩兩種最優(yōu)調度算法種最優(yōu)調度算法 兩種方法都假設通信代價可以忽略，優(yōu)先圖中每個節(jié)點的執(zhí)行時間是一樣的，即一個時間單

19、元。具體限制如下：(1) 在第一個有約束的調度問題中，優(yōu)先圖是一棵樹。(2) 在第二個有約束的調度問題中，只有兩個處理器可用。 兩種調度算法都是最高層優(yōu)先(highest-level-first)方法，也就是說，通過節(jié)點的優(yōu)先級來選擇節(jié)點。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v兩兩種最優(yōu)調度算法種最優(yōu)調度算法 樹結構的優(yōu)先圖和這個圖在三個處理器上的最優(yōu)調度 ： T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 時間 處理器 P1 P2 P3 0 T1 T2 T3 T4 T5 T7 T6 T9 T10 T8 T12 T11

20、 T13 (a) 樹結構的任務優(yōu)先圖 (b) 對三個處理器的調度 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v兩兩種最優(yōu)調度算法種最優(yōu)調度算法 只有兩個處理器可供使用的調度： T9 T10 T11 T7 T8 T6 T4 T5 T1 T2 T3 1 2 3 4 5 6 7 8 9 10 11 (a) 優(yōu)先級的標記 時間 處理器 P1 P2 T9 T10 T7 T8 T11 T6 T5 T4 T3 T2 T1 (b) 對雙處理器的調度 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度

21、任務相互關系圖由無向圖Gt(Vt,Et)表示，Vt是進程集合，Et是邊集合，每條邊用相關兩個進程的通信代價標記；處理器圖Gp(Vp,Ep)用頂點集Vp和邊集Ep表示，Vp中的每個元素是一個處理器，Ep中的每個元素是一個通信信道；然后進行分配M：進行VtVp的變換和執(zhí)行時間的估計。假設w(u)和w(u,v)分別表示節(jié)點u和鏈接(u,v)的代價。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度 對分配對分配MM的評估：的評估：處理器p的計算負載為： tVupuMuwpComp)(| )()(處理器p的通信負載為：

22、tEvuvMpuMvuwpCommp),()()(| ),()(整個應用程序中總的計算量是： pptVpVpVupuMuwpCompComp)(| )()(整個應用程序中總的通信量是： ptpVpEvuVpvMpuMvuwpCommpComm),(2121)()(| ),()(第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度 對分配對分配MM的評估：的評估：程序總的執(zhí)行時間大概是： pVppCommpCompT),()(max是依據(jù)處理器的執(zhí)行速度確定的值，是依據(jù)每個通信信道的通信速度和通信進程間的距離確定的值。

23、注意如果兩個進程u和v在Gt中鄰接，它們在Gp的映像(M的映像結果)可能鄰接也可能不鄰接。理想的情況下，所有通信進程被分配在鄰接的處理機上，以此減少處理器間通信。 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度 映射的勢：映射的勢：評估映射質量的一個指標是任務圖Gt中的邊映射到處理器圖Gp中的邊的數(shù)目。這個數(shù)目被稱作映射的勢(cardinality)，就是Gt中映射到Gp中鄰接處理器的通信進程對的數(shù)目。映射的勢不會超過Gt中的鏈接數(shù)目。如果一個映射的勢最大，它就是一個理想的映射。 第第5 5章章 分布式調度分布

24、式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度 圖中，映射的勢是8，任務關系圖中邊的為13條。 1 2 3 4 5 6 7 8 9 3 1 2 4 6 7 5 9 8 (a) 任務相互關系圖 (b) 任務到處理器的映射 第第5 5章章 分布式調度分布式調度 5.2 5.2 靜態(tài)調度靜態(tài)調度 v基于任務相互關系圖的任務調度基于任務相互關系圖的任務調度 嵌入：設想任務相互關系圖和處理器圖被各自看作Gt和Gp。為了通過Gt得到對Gp的有效模擬(emulation)，也就是在Gp中嵌入Gt。 嵌入的不同代價指標：(1) Gt的邊的膨脹。Gt的邊的膨

25、脹定義為被映射成Gt里的一條邊的Gp中對應的路徑的長度。嵌入的膨脹為Gt中的最大邊膨脹。 (2) 嵌入的擴大。嵌入的擴大定義為Gt里的節(jié)點數(shù)對Gp里的節(jié)點數(shù)的比率。 (3) 嵌入的擁塞。嵌入的擁塞定義為包含Gp中的一條邊的最大路徑數(shù)，Gp中的每條路徑表示Gt中的一條邊。 (4) 嵌入的負載。嵌入的負載是Gt分配給Gp中任意處理器的進程的最大數(shù)目。 第第5 5章章 分布式調度分布式調度 5.3 5.3 動態(tài)調度動態(tài)調度 v動態(tài)調度的組成要素動態(tài)調度的組成要素 動態(tài)調度算法有六個策略：啟動策略、轉移策略、選擇策略、收益性策略、定位策略和信息策略。 啟動策略啟動策略的責任是決定誰應該激活負載平衡活動

26、。 轉移策略轉移策略決定一個節(jié)點是否在合適的狀態(tài)參與負載轉移。 選擇策略選擇策略選擇最適合轉移最能起平衡作用的任務，并發(fā)送給合適的目標處理器。收益性策略收益性策略量化系統(tǒng)中負載不平衡程度，并且作為系統(tǒng)負載平衡潛在受益的估計，評估系統(tǒng)負載平衡是否是有收益的。定位策略定位策略是尋找合適的節(jié)點共享負載。 信息策略信息策略決定收集系統(tǒng)中其他節(jié)點狀態(tài)信息的時機、收集的方法和收集的信息。 第第5 5章章 分布式調度分布式調度 5.3 5.3 動態(tài)調度動態(tài)調度 v動態(tài)動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)負載平衡算法的分類、設計決策和使用的參數(shù) 動態(tài)負載平衡算法可以分成以下幾類： (1) 全局的和局部

27、的。局部負載平衡算法在相鄰的節(jié)點間轉移工作負載。全局負載平衡算法不僅在相鄰節(jié)點間轉移負載，還在全系統(tǒng)內(nèi)計算負載，根據(jù)全局情況調整處理器負載。 (2) 集中控制的和分散控制的。在集中控制算法中，中心控制器收集狀態(tài)信息，做出負載平衡決策。分散控制算法把控制機制分散到全系統(tǒng)的各個節(jié)點?；旌鲜截撦d平衡算法是集中控制和分散控制算法的折衷。第第5 5章章 分布式調度分布式調度 5.3 5.3 動態(tài)調度動態(tài)調度 v動態(tài)動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)負載平衡算法的分類、設計決策和使用的參數(shù) 動態(tài)負載平衡算法可以分成以下幾類： (3) 不協(xié)作的和協(xié)作的。在不協(xié)作方法中，各個節(jié)點不知道系統(tǒng)中其他節(jié)點的狀態(tài)，獨立決定自己的定位和負載轉移規(guī)則。在協(xié)作算法中，節(jié)點間相互配合來決定負載平衡決策。(4) 適應性的和非適應性的。在適應性算法中，負載平衡策略根據(jù)系統(tǒng)狀態(tài)變化而改變；而非適應性方法中，這些策略是不變的。 第第5 5章章 分布式調度分布式調度 5.3 5.3 動態(tài)調度動態(tài)調度 v動態(tài)動態(tài)負載平衡算法的分類、設計決策和使用的參數(shù)負載平衡算法的分類、設計決策和使用的參數(shù) 動態(tài)負載平衡算法的設計決策包括如下一些內(nèi)容：(1)非搶先式的和搶先式的非搶先式的和搶先式的: :搶先式的主要目的是負載共享，節(jié)點只分配新到達的任務，又稱為任務放置(place