吉林大學(xué)研究所課程-并行計算課件-第5章-分布式調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

13、計算量和通信量最大的有向路徑上的節(jié)點聚集成一個單獨的線性聚類，并且這些節(jié)點被從圖中除去。對圖中剩余的節(jié)點迭代執(zhí)行這個過程，直到整個任務(wù)圖已經(jīng)全部被劃分成一些聚類。Sarkar的內(nèi)在化聚類方案，將每個節(jié)點最初放在一個單獨的聚類中，并且以弧上通信開銷的下降順序考慮將圖中的節(jié)點劃分成一些聚類。這個算法不斷地將兩個聚類合并成一個更大的聚類，如果在合并過程中生成的更大聚類不會增加這個圖的估計并行執(zhí)行時間，那么這個合并過程就被接受。這個過程一直進行下去，直到不再需要合并為止。 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v任務(wù)劃分與分配任務(wù)劃分與分配 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 任務(wù)復(fù)制：第第5 5章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度 甘特圖甘特圖(gantt chart)能夠最有效描述進程對處理器的分配情況。甘特圖以處理器為縱坐標(biāo)，以時間為橫坐標(biāo)。圖中的每個方塊表示進程在某個系統(tǒng)中的開始時間、持續(xù)時間和結(jié)束時間。處理器內(nèi)的時

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

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

17、5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度 一個任務(wù)優(yōu)先圖可以認(rèn)為是許多分叉和合并操作的集合，分叉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章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度基于任務(wù)優(yōu)先圖的任務(wù)調(diào)度 給定任務(wù)優(yōu)先圖給定任務(wù)優(yōu)先圖G G的粒度是的粒度是： )(min)(xgGgGx如果g(x)1，合并x或分叉x就是粗粒度；否則

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

19、元。具體限制如下：(1) 在第一個有約束的調(diào)度問題中，優(yōu)先圖是一棵樹。(2) 在第二個有約束的調(diào)度問題中，只有兩個處理器可用。 兩種調(diào)度算法都是最高層優(yōu)先(highest-level-first)方法，也就是說，通過節(jié)點的優(yōu)先級來選擇節(jié)點。 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v兩兩種最優(yōu)調(diào)度算法種最優(yōu)調(diào)度算法 樹結(jié)構(gòu)的優(yōu)先圖和這個圖在三個處理器上的最優(yōu)調(diào)度 ： 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) 樹結(jié)構(gòu)的任務(wù)優(yōu)先圖 (b) 對三個處理器的調(diào)度 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v兩兩種最優(yōu)調(diào)度算法種最優(yōu)調(diào)度算法 只有兩個處理器可供使用的調(diào)度： 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)先級的標(biāo)記 時間 處理器 P1 P2 T9 T10 T7 T8 T11 T6 T5 T4 T3 T2 T1 (b) 對雙處理器的調(diào)度 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.2 5.2 靜態(tài)調(diào)度靜態(tài)調(diào)度 v基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度基于任務(wù)相互關(guān)系圖的任務(wù)調(diào)度

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

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

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

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

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

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

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