吉林大學(xué)研究所課程-并行計(jì)算課件-第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)度 動(dòng)態(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)。對(duì)非搶先式的調(diào)度算法，一個(gè)進(jìn)程開(kāi)始執(zhí)行后就不能中斷。在搶先式調(diào)度算

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

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

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

5、而引起的通信代價(jià)。 執(zhí)行代價(jià)：執(zhí)行代價(jià)：這個(gè)參數(shù)反映的是將一個(gè)進(jìn)程分配到一個(gè)指定的執(zhí)行節(jié)點(diǎn)，在這個(gè)節(jié)點(diǎn)的執(zhí)行環(huán)境下，執(zhí)行這個(gè)程序所需的額外開(kāi)銷(xiāo)。資源利用率：資源利用率：常用來(lái)表明基于分布式系統(tǒng)當(dāng)前各個(gè)節(jié)點(diǎn)的負(fù)載情況，給一個(gè)進(jìn)程分配的執(zhí)行節(jié)點(diǎn)是否是合適的。資源利用率參數(shù)常用負(fù)載狀態(tài)來(lái)表示，常用的負(fù)載參數(shù)有資源的隊(duì)列長(zhǎng)度、內(nèi)存的使用等等。 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.1 5.1 調(diào)度算法概述調(diào)度算法概述 v調(diào)度算法的目標(biāo)和有效性評(píng)價(jià)調(diào)度算法的目標(biāo)和有效性評(píng)價(jià) 次優(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)度不搜索這個(gè)算法的所有解空間，而是在這個(gè)算法的解空間中的一個(gè)子集中搜索，目的是盡快地找到一個(gè)較好的解。而最優(yōu)調(diào)度則是搜索這個(gè)算法的整個(gè)解空間，目的是獲得最好的解。使用近似的次優(yōu)調(diào)度算法必須能夠判定所得到的解是否是可以被接受的，也就是說(shuō)，必須能夠確定最優(yōu)解和次優(yōu)解之間的近似程度。 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.1 5.1 調(diào)度算法概述調(diào)度算法概述 v調(diào)度算法的目標(biāo)和有效性評(píng)價(jià)調(diào)度算法的目標(biāo)和有效性評(píng)價(jià) 次優(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)度算法：?jiǎn)l(fā)式的次優(yōu)調(diào)度算法常使用比較簡(jiǎn)明的規(guī)則和一些直覺(jué)的規(guī)則來(lái)進(jìn)行調(diào)度。這些啟發(fā)式的規(guī)則往往是不能證明其正確性，在特定情況下可能還是錯(cuò)誤的，但是在絕大多數(shù)的情況下是能夠被接受的。 第第5 5章章 分布式調(diào)度分布式調(diào)度 5.1 5.1 調(diào)度算法概述調(diào)度算法概述 v調(diào)度算法的目標(biāo)和有效性評(píng)價(jià)調(diào)度算法的目標(biāo)和有效性評(píng)價(jià) 啟發(fā)式調(diào)度算法中常采用的一些啟發(fā)式規(guī)則：?jiǎn)l(fā)式調(diào)度算法中常采用的一些啟發(fā)式規(guī)則： 相互依賴性較大的進(jìn)程，由于它們之間常有比較多的進(jìn)程通信應(yīng)該分配到比較接近的執(zhí)行節(jié)點(diǎn)上，可能的話，應(yīng)該在同一個(gè)節(jié)點(diǎn)上。 訪問(wèn)共享文件的進(jìn)程應(yīng)該分配到比較接近的執(zhí)行節(jié)點(diǎn)上，可能的話，應(yīng)該分配在文件服

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

9、系，節(jié)點(diǎn)和鏈接上的標(biāo)記表示任務(wù)的執(zhí)行時(shí)間和任務(wù)完成后啟動(dòng)后續(xù)任務(wù)所需的時(shí)間間隔。任務(wù)交互作用圖任務(wù)交互作用圖中，鏈接定義了兩個(gè)任務(wù)間的相互關(guān)系，每個(gè)鏈接賦予一對(duì)數(shù)，分別表示這兩個(gè)任務(wù)在同一個(gè)處理機(jī)上時(shí)的通信開(kāi)銷(xiāo)和在不同處理機(jī)上時(shí)的通信開(kāi)銷(xiāo)。 第第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ù)劃分的粒度：一個(gè)給定任務(wù)劃分的粒度被定義為任務(wù)的計(jì)算量與通信量的比值。如果粒度太大，就會(huì)限制并行性，因?yàn)闈撛诘牟⑿腥蝿?wù)可能被劃分進(jìn)同一個(gè)任務(wù)而分配給一個(gè)處理器。粒度太小，進(jìn)程切換和通信的開(kāi)銷(xiāo)就會(huì)增加，從而降低性能。 任務(wù)聚類：任務(wù)聚類：在圖模型中，任務(wù)的劃分被稱作任務(wù)聚類，即在給定的圖模型中對(duì)小任務(wù)進(jìn)行分類。任務(wù)劃分把任務(wù)圖當(dāng)作一個(gè)整體，將圖中的小任務(wù)(節(jié)點(diǎn))劃分成不同的聚類，聚類中的小任務(wù)串行執(zhí)行，不同的聚類之間并行執(zhí)行。任務(wù)聚類中可以使用兩種策略： (1) 將不相關(guān)的任務(wù)映射到一個(gè)聚類中； (2) 將DAG中一條優(yōu)先路徑上的任務(wù)映射到一個(gè)聚

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)鍵路徑(最長(zhǎng)路徑)的概念常常在垂直劃分中使用，即用在線性聚類中。應(yīng)該清楚的是，依賴于任務(wù)優(yōu)先圖中關(guān)鍵路徑的細(xì)粒度任務(wù)必須串行執(zhí)行。(2) (2) 消除通信延遲的劃分。消除通信延遲的劃分。這個(gè)方法的關(guān)鍵之處在于消除通信的額外開(kāi)銷(xiāo)，所以要把通信頻繁的節(jié)點(diǎn)聚集成一類。通常的方法是將一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)與節(jié)點(diǎn)自身聚集成一類，只要總的執(zhí)行時(shí)間不會(huì)被延長(zhǎng)。 第第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ù)間的通信開(kāi)銷(xiāo)，將任務(wù)在處理機(jī)上進(jìn)行復(fù)制有時(shí)是最有效的方法。它是任務(wù)劃分的一個(gè)可選方法。任務(wù)復(fù)制不僅能保留程序最初的并行性，同時(shí)也能減少通信開(kāi)銷(xiāo)。 (4) (4) 其他技術(shù)。其他技術(shù)。Kim和Browne的線性聚類技術(shù)，在每一步，

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

15、間延遲和處理器間的時(shí)間延遲都能夠在圖中體現(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) 甘特圖 時(shí)間 處理器 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ù)制對(duì)調(diào)度的影響： T1 T2 T3 d d 時(shí)間 處理器 P1 P2 T1 T1 T2 T3 時(shí)間 處理器

16、 P1 P2 T1 T2 T3 時(shí)間 P1 P2 處理器 T1 T2 T3 d (a) 任務(wù)優(yōu)先圖 (b) 使用任務(wù)復(fù)制的調(diào)度 (c) 任務(wù)分配在一個(gè)處理器上 (d) 通信延遲對(duì)調(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)度 線性聚類與非線性聚類：線性聚類與非線性聚類：如果至少有一個(gè)聚類中包含兩個(gè)獨(dú)立的任務(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)度 一個(gè)任務(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、就是細(xì)粒度。同樣如果g(G)1，圖G就是粗粒度，否則就是細(xì)粒度。當(dāng)表示一個(gè)應(yīng)用程序的給定的有向無(wú)環(huán)圖DAG(任務(wù)優(yōu)先圖)是粗粒度時(shí)，也就是它的一個(gè)鏈接上的通信代價(jià)小于分叉或者合并操作連接的相鄰節(jié)點(diǎn)的計(jì)算代價(jià)，任何非線性聚類可以被轉(zhuǎn)換成具有更少或相等執(zhí)行時(shí)間的線性聚類。注意，上面的結(jié)論暗示了一個(gè)粗粒度程序的線性聚類性能優(yōu)于任何非線性聚類。然而，對(duì)細(xì)粒度程序而言，可能存在也可能不存在一個(gè)非線性聚類優(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è)通信代價(jià)可以忽略，優(yōu)先圖中每個(gè)節(jié)點(diǎn)的執(zhí)行時(shí)間是一樣的，即一個(gè)時(shí)間單

19、元。具體限制如下：(1) 在第一個(gè)有約束的調(diào)度問(wèn)題中，優(yōu)先圖是一棵樹(shù)。(2) 在第二個(gè)有約束的調(diào)度問(wèn)題中，只有兩個(gè)處理器可用。 兩種調(diào)度算法都是最高層優(yōu)先(highest-level-first)方法，也就是說(shuō)，通過(guò)節(jié)點(diǎn)的優(yōu)先級(jí)來(lái)選擇節(jié)點(diǎn)。 第第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ù)結(jié)構(gòu)的優(yōu)先圖和這個(gè)圖在三個(gè)處理器上的最優(yōu)調(diào)度 ： T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 時(shí)間 處理器 P1 P2 P3 0 T1 T2 T3 T4 T5 T7 T6 T9 T10 T8 T12 T11

20、 T13 (a) 樹(shù)結(jié)構(gòu)的任務(wù)優(yōu)先圖 (b) 對(duì)三個(gè)處理器的調(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)度算法 只有兩個(gè)處理器可供使用的調(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)先級(jí)的標(biāo)記 時(shí)間 處理器 P1 P2 T9 T10 T7 T8 T11 T6 T5 T4 T3 T2 T1 (b) 對(duì)雙處理器的調(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)系圖由無(wú)向圖Gt(Vt,Et)表示，Vt是進(jìn)程集合，Et是邊集合，每條邊用相關(guān)兩個(gè)進(jìn)程的通信代價(jià)標(biāo)記；處理器圖Gp(Vp,Ep)用頂點(diǎn)集Vp和邊集Ep表示，Vp中的每個(gè)元素是一個(gè)處理器，Ep中的每個(gè)元素是一個(gè)通信信道；然后進(jìn)行分配M：進(jìn)行VtVp的變換和執(zhí)行時(shí)間的估計(jì)。假設(shè)w(u)和w(u,v)分別表示節(jié)點(diǎn)u和鏈接(u,v)的代價(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)度 對(duì)分配對(duì)分配MM的評(píng)估：的評(píng)估：處理器p的計(jì)算負(fù)載為： tVupuMuwpComp)(| )()(處理器p的通信負(fù)載為：

22、tEvuvMpuMvuwpCommp),()()(| ),()(整個(gè)應(yīng)用程序中總的計(jì)算量是： pptVpVpVupuMuwpCompComp)(| )()(整個(gè)應(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)度 對(duì)分配對(duì)分配MM的評(píng)估：的評(píng)估：程序總的執(zhí)行時(shí)間大概是： pVppCommpCompT),()(max是依據(jù)處理器的執(zhí)行速度確定的值，是依據(jù)每個(gè)通信信道的通信速度和通信進(jìn)程間的距離確定的值。

23、注意如果兩個(gè)進(jìn)程u和v在Gt中鄰接，它們?cè)贕p的映像(M的映像結(jié)果)可能鄰接也可能不鄰接。理想的情況下，所有通信進(jìn)程被分配在鄰接的處理機(jī)上，以此減少處理器間通信。 第第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ì)：映射的勢(shì)：評(píng)估映射質(zhì)量的一個(gè)指標(biāo)是任務(wù)圖Gt中的邊映射到處理器圖Gp中的邊的數(shù)目。這個(gè)數(shù)目被稱作映射的勢(shì)(cardinality)，就是Gt中映射到Gp中鄰接處理器的通信進(jìn)程對(duì)的數(shù)目。映射的勢(shì)不會(huì)超過(guò)Gt中的鏈接數(shù)目。如果一個(gè)映射的勢(shì)最大，它就是一個(gè)理想的映射。 第第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)度 圖中，映射的勢(shì)是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。為了通過(guò)Gt得到對(duì)Gp的有效模擬(emulation)，也就是在Gp中嵌入Gt。 嵌入的不同代價(jià)指標(biāo)：(1) Gt的邊的膨脹。Gt的邊的膨

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

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

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