分布式系統(tǒng)中的負載分配

1、分布式系統(tǒng)中的負載分配第1頁，共39頁，2022年，5月20日，10點11分，星期一負載分配的分類（1） 通常，負載分配方法可做如下分類：局部和全局 局部負載分配處理單個處理器上的進程對時間片(單元)的分配。全局負載分配首先進行進程對處理器的分配，然后完成每個處理器內這些進程的局部調度。靜態(tài)和動態(tài)(在全局類中) 靜態(tài)負載分配中，進程對處理器的分配是在進程執(zhí)行以前的編譯階段完成的，而動態(tài)負載分配要到進程在系統(tǒng)中執(zhí)行時才做出分配。靜態(tài)方法又叫做確定性調度，而動態(tài)方法叫做負載平衡。第2頁，共39頁，2022年，5月20日，10點11分，星期一負載分配的分類（2）最優(yōu)和次優(yōu)(在靜態(tài)和動態(tài)兩種類型中)

2、如果根據(jù)標準，比如最小執(zhí)行時間和最大系統(tǒng)輸出，可以取得最優(yōu)分配，那么就可以認為這種負載分配方法是最優(yōu)的。一般地，負載分配問題是NP完全問題。某些情況下，次優(yōu)方案也是可以接受的。有四類算法(對于最優(yōu)的和次優(yōu)的)被使用：解空間枚舉搜索、圖模型、數(shù)學編程(例如01編程)和隊列模型。近似和啟發(fā)式(在次優(yōu)類型中) 在近似方法中，負載分配算法僅搜索一個解空間的子集，當尋找到一個好的解時，終止執(zhí)行。在啟發(fā)式方法中，調度算法使用某些特殊參數(shù)，能夠近似地對真實系統(tǒng)建模。第3頁，共39頁，2022年，5月20日，10點11分，星期一負載分配的分類（3）集中控制的和分散控制的(在動態(tài)類型中) 在分散控制中，決策工作

3、被分配給不同的處理器。在集中控制中，這些工作是由一個處理器完成的。協(xié)作的和非協(xié)作的(對分散控制) 動態(tài)負載分配機制可以分成：協(xié)作的分布式對象間有協(xié)同操作，非協(xié)作的處理器獨立做出決策。第4頁，共39頁，2022年，5月20日，10點11分，星期一負載分配的分類（4） 下面是另一種負載分配算法的分類方法，包括一些不能直接歸人上面分類的負載分配類型：單個和多個應用程序 多數(shù)負載分配算法是針對單個應用程序。多應用程序情況可以轉換成單個應用程序情況。然而，多應用程序情況下的進程分配遠復雜于單個應用程序的情況。非搶占式的和搶占式的 對非搶占式的負載分配算法，一個任務(進程)開始執(zhí)行后就不能中斷。在搶占式負

4、載分配算法中，進程可以中斷，并從處理器上移走，過后繼續(xù)執(zhí)行。 第5頁，共39頁，2022年，5月20日，10點11分，星期一負載分配的分類（5）非自適應的和自適應的 非自適應負載分配只使用一種負載分配算法，不會依據(jù)系統(tǒng)反饋而改變自己的行為。自適應負載分配能夠根據(jù)系統(tǒng)反饋調整分配算法。典型地，一個自適應負載分配算法是許多負載分配算法的集合，依據(jù)系統(tǒng)的各種參數(shù)來選擇一個合適的算法。第6頁，共39頁，2022年，5月20日，10點11分，星期一靜態(tài)負載分配靜態(tài)負載分配算法根據(jù)系統(tǒng)的先驗知識做出決策。運行時負載不能夠重新分配。靜態(tài)負載分配算法的目標是調度一個任務集合，使它們在各個目標PE上有最小的執(zhí)行

5、時間。靜態(tài)負載分配因此又稱做調度問題?？傮w上，處理器互連、任務劃分(粒度決策)和任務分配是設計調度策略時的三個主要因素。如前所述，通常的調度問題即使在簡單地對計算開銷和通信開銷做某種假設以后，依然是一個NP完全問題。因此，許多方法利用數(shù)學工具如圖、啟發(fā)式規(guī)則來得到次優(yōu)的解。 第7頁，共39頁，2022年，5月20日，10點11分，星期一任務圖模型通常，用圖模型表示任務和PE結構。我們可以用任務優(yōu)先圖或者任務交互作用圖對任務集合建模。任務優(yōu)先圖又稱為有向無環(huán)圖(DAG)，每個鏈接定義了任務間的優(yōu)先關系。節(jié)點和鏈接上的標記表示任務執(zhí)行時間和任務完成后啟動后續(xù)任務所需的時間間隔。任務交互作用圖中，鏈

6、接定義了兩個任務間的相互關系。每個鏈接賦予一對數(shù)，表示這兩個任務在同一個PE上時的通信開銷和在不同PE上時的通信開銷。第8頁，共39頁，2022年，5月20日，10點11分，星期一處理機互連（1）互連網(wǎng)絡的拓撲可以分為靜態(tài)的和動態(tài)的。靜態(tài)網(wǎng)絡由固定的點到點直接連接組成，并且進程執(zhí)行過程中不能改變。動態(tài)網(wǎng)絡利用交換機實現(xiàn)動態(tài)配置來滿足用戶程序的通信要求。 靜態(tài)互連網(wǎng)絡：16節(jié)點系統(tǒng)的不同連接方案（每個節(jié)點四個雙向鏈接）a) 依里?？司W(wǎng)格( Illiac Mesh) b) 圓環(huán)網(wǎng)第9頁，共39頁，2022年，5月20日，10點11分，星期一處理機互連（2）c) 超 立 方 體（4維立方體由兩個3維

7、立方體節(jié)點互連而成，每維兩個節(jié)點）d) WK層次網(wǎng)絡（n層網(wǎng)絡由四個（n-1）層網(wǎng)絡組成，每個子網(wǎng)絡是一個虛擬節(jié)點，1層WK網(wǎng)絡是基元） 第10頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)互連網(wǎng)絡（1）有三種類型的動態(tài)拓撲：單級、多級和縱橫制(見圖1-8)。通常，處理機位于網(wǎng)絡的兩側。一個單級網(wǎng)絡由一級交換單元組成。每個交換單元是一個帶兩個輸入和兩個輸出的2x2的開關，輸入和輸出的連接可以是直連或交叉，這由一個布爾變量控制。圖1-8a表示了一個完全混洗連接的例子。一個多級網(wǎng)絡包含多級的交換單元并支持從任意數(shù)量的輸入處理機到任意數(shù)量的輸出處理機的連接。在一些網(wǎng)絡中，輸入和輸出處

8、理機的同時連接可能導致使用網(wǎng)絡通信鏈路的沖突。這種網(wǎng)絡叫做阻塞式網(wǎng)絡(見圖1-8c所示的基線制網(wǎng)絡)；否則，就叫做可重新安排的非阻塞式網(wǎng)絡(見圖1-8d所示的Benes網(wǎng)絡)。在縱橫制交換機中，每個輸入可以無阻塞地和一個空閑的輸出相連(見圖1-8b)。第11頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)互連網(wǎng)絡（2）圖1-8 a) 8 8混洗交換b) 4 4縱橫制第12頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)互連網(wǎng)絡（3）c) 8 8基線制d) 8 8 Benes第13頁，共39頁，2022年，5月20日，10點11分，星期一任務劃分一個給定任務劃分的粒度

9、定義是任務分解中影響通信開銷的所有單元的平均尺度。算法可以分成細粒度、中粒度和粗粒度。如果數(shù)據(jù)單元(即粒度)小，這種算法就是細粒度。如果數(shù)據(jù)單元大，算法就是粗粒度。介于細粒度和粗粒度之間的就是中粒度。粒度太大，就會降低并行度，因為潛在并行任務可能被劃分進同一個任務而分配給一個處理器。粒度太小，進程切換和通信的開銷就會增加。任務劃分的一個主要目標就是盡可能消除處理器間通信引起的開銷。第14頁，共39頁，2022年，5月20日，10點11分，星期一任務劃分的方法水平或者垂直劃分。主要思想是在給定的任務優(yōu)先圖中垂直或者水平劃分。關鍵路徑(最長路徑)的概念常常在垂直劃分中使用。水平劃分把給定的任務分成

10、若干層，任務的優(yōu)先級由它們所在的層次決定。通信延遲最小劃分。 主要思想是把通信頻繁的節(jié)點歸成一類。然而，這些需要通信的任務分配在一個處理器上會喪失任務間的并發(fā)性。如果減小通信延遲的好處抵銷了并行任務串行化的損失，就采用通信延遲最小劃分。任務復制。這是任務劃分的一個可選方法。主要思想是通過在PE上復制任務來降低通信開銷。這個方法保留了任務原有的并行性；但是存儲空間要求和同步開銷增加了?？梢岳萌蝿諒椭苼磉_到容錯性。任務復制也被用來實現(xiàn)無錯調度，以保證處理器出現(xiàn)錯誤時最后計算結果正確。第15頁，共39頁，2022年，5月20日，10點11分，星期一任務分配（1）任務分配是指在多處理機系統(tǒng)中，針對某

11、一目標，按照一定的策略，將規(guī)模為N的任務劃分并映射到P臺處理機上。在多處理機系統(tǒng)中，一個任務的執(zhí)行時間為 T f ( tcomp，tcomm，te ) 其中，tcomp為子任務的最大執(zhí)行時間，tcomm為完成子任務所需的通信時間，而te為其它開銷。一個問題劃分的子任務越多，tcomp就越小，而tcomm和te可能很大。tcomm和te的增大不僅可能抵消tcomp的減小，甚至可能使并行處理所得到的效益完全喪失。任務分配的主要目標是尋找一種合適的算法，使T降到最低程度。任務的靜態(tài)分配又稱確定性調度，指任務在運行前就指定運行的處理機，并在其生命周期內一直駐留在該處理機上。第16頁，共39頁，2022

12、年，5月20日，10點11分，星期一任務分配（2）任務分配就是在給定了互連網(wǎng)絡的并行系統(tǒng)或者分布式系統(tǒng)中分配顆粒(顆粒是任務劃分的結果)。如果任務圖和處理器圖的節(jié)點數(shù)目都是n，那么就有n!種不同的分配方法把任務圖Gt里的節(jié)點分配到處理器圖Gp的節(jié)點上。我們把每種方法稱做Gt到Gp的一個映射。在總執(zhí)行時間概念下，有些映射比較好。下面是關于Gp的典型假設： 存儲器容量無限。 每個PE有相同的處理能力。 忽略網(wǎng)絡擁塞，雖然通信進程間的距離是影響通 信延遲的因素。 注意，任務調度不必要一定分兩個步驟做，即任務劃分和任務分配。分兩步的方法只是為了簡化原本是NP完全的調度過程。第17頁，共39頁，2022

13、年，5月20日，10點11分，星期一調度模型前面提到，絕大多數(shù)最優(yōu)調度問題是NP完全的。主要的研究努力集中在下面的方法： 對特殊情況的最優(yōu)調度，比如，帶特殊約 束的模型。 非最優(yōu)調度，可以分成局部最優(yōu)方案和次 優(yōu)方案。局部最優(yōu)方法使用有效的搜索技術確定問題解空間中的(局部)最優(yōu)調度方案。這些方案可以進一步分成下面四種：第18頁，共39頁，2022年，5月20日，10點11分，星期一局部最優(yōu)方案（1） 解空間枚舉和搜索。首先構建狀態(tài)空間，其中每個狀態(tài)對應一個可能的調度方案。它依靠各種搜索技巧如分支搜索和邊界搜索在解空間中尋找解。 數(shù)學編程。一個給定的調度問題轉換成一個整數(shù)、線性或者非線性編程問題

14、。有三個步驟：(a)一個目標函數(shù)，以求目標函數(shù)最小化，常常定義成程序執(zhí)行時間。(b)一個約束集合，例如優(yōu)先關系和通信延遲。(c)使用動態(tài)編程技巧解決基于a和b的約束最優(yōu)問題。 模擬退火。模擬退火利用物理退火過程的特性構建一種局部最優(yōu)方案的搜索方法。通常這樣一個過程由三部分組成：(a)對初始非最優(yōu)調度方案做小幅度的隨機的變動。(b)評估新的調度方案。(c)繼續(xù)這一過程直到?jīng)]有更好的方案產(chǎn)生，也就是說得到了一個局部最優(yōu)方案。第19頁，共39頁，2022年，5月20日，10點11分，星期一局部最優(yōu)方案（2） 遺傳算法。遺傳算法是基于自然界遺傳和進化規(guī)律的搜索算法。它結合已有結果和搜索空間的新領域來產(chǎn)

15、生新的結果。Kwok和Ahmad提出了一個并行遺傳調度算法。和特殊情況的最優(yōu)解一樣，局部最優(yōu)解也有極大的計算量并且極端耗費時間。次優(yōu)解法依靠啟發(fā)式方法取得次優(yōu)解。第20頁，共39頁，2022年，5月20日，10點11分，星期一任務靜態(tài)分配算法第21頁，共39頁，2022年，5月20日，10點11分，星期一使用兩臺處理機的最佳調度圖8.3 任務圖和Gantt圖第22頁，共39頁，2022年，5月20日，10點11分，星期一性能分析第23頁，共39頁，2022年，5月20日，10點11分，星期一最早調度算法（1）最早調度算法ESA(Earliest Scheduling Algorithm)的基本

16、思想是，只要系統(tǒng)中有可用的處理機，便從任務系統(tǒng)中選出一個能滿足偏序限制條件的任務，并立即使其投入運行，當有多個能滿足偏序限制條件的任務時，選擇其中最早的一個任務。我們以圖8.3(a)中的任務圖為例，說明最早調度算法的調度過程。假定系統(tǒng)中有兩臺處理機，按ESA算法來分配處理機的步驟如下： (1)作業(yè)開始時，只有啟動任務T1能滿足偏序限制條件，故調度程序將處理機P1分配給T1 ，因無任務分配給P2，故P2空閑，用表示。 (2)執(zhí)行一個單位時間后， T1已完成，T2和T3能滿足偏序限制條件，于是調度程序將P2和P1分別分配給T2和T3 ，使它們并行執(zhí)行。 (3)T3運行一個單位時間后完成，調度程序立

17、即把P1分配給唯一能滿足偏序限制條件的任務T6，調度程序按ESA算法不斷地為任務分配處理機，直至該作業(yè)完成。圖84示出了按ESA算法進行調度產(chǎn)生的Gantt表格的時間圖。第24頁，共39頁，2022年，5月20日，10點11分，星期一最早調度算法（2）第25頁，共39頁，2022年，5月20日，10點11分，星期一最早調度算法（3）第26頁，共39頁，2022年，5月20日，10點11分，星期一考慮通信延遲的調度算法（1）第27頁，共39頁，2022年，5月20日，10點11分，星期一考慮通信延遲的調度算法（2）圖9-4a顯示了一個實例的任務優(yōu)先圖，給出了處理器間的通信延遲和任務執(zhí)行時間。圖9

18、-4b是根據(jù)圖9-4a的數(shù)據(jù)給出的對處理器P1、P2的調度結果。圓圈中的數(shù)對應任務的執(zhí)行時間。與每個鏈接相關的數(shù)對應于處理器間的通信時間。兩個連接任務分配在不同的處理器上時就會發(fā)生通信延遲。例如，w(T1)=2和w(T1,T2)=1表示T1的執(zhí)行時間是2， T1 T2間處理器間的通信代價是1（沒有給出處理器內的通信代價）。本例中，兩個處理器間的通信發(fā)生在有1個單位通信延遲的T2到T4和有2個單位通信延遲的T4到T5?？偟膱?zhí)行時間是12。第28頁，共39頁，2022年，5月20日，10點11分，星期一考慮通信延遲的調度算法（3）第29頁，共39頁，2022年，5月20日，10點11分，星期一考慮

19、通信延遲的調度算法（4）通信延遲使調度算法大大地變復雜。圖9-5a給出了三種不同調度的例子。如果通信延遲d大于任務T2的執(zhí)行時間，圖9-5c的調度就比圖9-5d的要好。可以說，若通信延遲太大的話，所有任務分配在一個處理器上是比較合適的。通常我們總是嘗試盡量增加并行度，同時盡可能降低通信延遲。然而在多數(shù)時間這兩個目標是互相矛盾的。因此需要某種程度折衷。有時可以使用任務復制的方法減少通信需求。顯然，由于通過任務復制而避免了處理器間的通信，圖9-5b的結果是最好的。第30頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)負載分配分布式系統(tǒng)中，許多算法包含不統(tǒng)一的計算和通信代價，它們不容易

20、事先確定。某些應用中，工作負載隨著計算進度而變化，這意味著初始好的映射可能會變壞。動態(tài)負載分配(又稱負載平衡、負載轉移或者負載共享)能夠用來恢復平衡。動態(tài)負載分配算法使用系統(tǒng)狀態(tài)信息(節(jié)點的負載信息)，至少部分使用，來做負載分配的決策，而靜態(tài)負載分配沒有使用這些信息。靜態(tài)負載分配的限制是以一種一勞永逸的方式把任務分配給處理器，而且要求預先知道程序狀態(tài)。包含通信進程的系統(tǒng)會產(chǎn)生沖突，同時計算進程也可能發(fā)生加速，但是多數(shù)方法忽略這兩種影響。相反地，動態(tài)負載平衡很少假設關于例如任務執(zhí)行時間或者通信延遲的運行時參數(shù)的先驗信息。動態(tài)負載平衡延遲在運行時重分配進程，以達到高性能目標。動態(tài)負載分配更好地動態(tài)

21、使用了全系統(tǒng)的所有資源，提高了系統(tǒng)的性能。第31頁，共39頁，2022年，5月20日，10點11分，星期一基本概念所謂負載是指處理機上的用戶進程尚未完成的工作量。主要包括進程的計算開銷和通信開銷。在多處理機系統(tǒng)中，對節(jié)點機上系統(tǒng)資源的負載度量，稱為負載指標。以向量形式表示的某一節(jié)點機的各項負載指標，稱為負載向量，它描述的是某一節(jié)點機的負載情況。以矩陣形式表示的各節(jié)點機負載向量的集合，稱為負載矩陣，用以描述整個系統(tǒng)的負載情況。負載向量所描述的內容，是任務分配的依據(jù)，其定義必須準確、完備和有效。負載向量可以包括多種負載指標，例如：節(jié)點機就緒隊列的長度，局部存儲器空閑空間的容量，單位時間內進行系統(tǒng)功

22、能調用的次數(shù)，單位時間內存儲器頁面的調入調出次數(shù)，單位時間內CPU被占用的百分比，單位時間內磁盤的讀寫次數(shù)等。大多數(shù)任務分配算法采用單個負載指標作為負載向量，其中選擇節(jié)點機就緒隊列長度的頗多。第32頁，共39頁，2022年，5月20日，10點11分，星期一負載平衡為了描述節(jié)點機上負載的輕重程度，我們使用負載閥值進行衡量。負載閥值是節(jié)點機負載的界限值，其下界為T1，上界為T2，且T1T2。我們有如下的定義。 輕載：當節(jié)點機的負載小于T1時，該節(jié)點機為輕載； 重載：當節(jié)點機的負載大于T2時，該節(jié)點機為重載； 適載：當節(jié)點機負載大于T1而小于T2時，該節(jié)點機為適載； 空載：當節(jié)點機負載為0時，該節(jié)點

23、機為空載。 負載平衡：是指系統(tǒng)中的所有處理機均處于適載狀態(tài)。這是一種嚴格意義下的負載平衡。更廣泛意義下的負載平衡應是系統(tǒng)中每個節(jié)點機都不是空載，或者當某個節(jié)點機為空載時，其它節(jié)點機均為空載或輕載。第33頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)負載平衡負載分配算法可以分為靜態(tài)負載分配算法和動態(tài)負載分配算法。靜態(tài)負載分配算法是指在系統(tǒng)中進行任務分配時，根據(jù)各節(jié)點的負載情況決定給任務分配處理機。動態(tài)負載分配算法通過交換系統(tǒng)的狀態(tài)信息來決定系統(tǒng)負載的分配。動態(tài)負載分配算法能適應系統(tǒng)負載的變化，比靜態(tài)負載分配算法更靈活、更有效，但它以一定的系統(tǒng)開銷為代價。所謂動態(tài)負載平衡，是指系統(tǒng)

24、根據(jù)其負載變化和進程的執(zhí)行情況，自動實現(xiàn)進程從重載節(jié)點機到輕載節(jié)點機的遷移。重載節(jié)點機提供遷出進程，輕載節(jié)點機要求遷入進程。在分布存儲器結構多處理機系統(tǒng)中，各節(jié)點處理機缺乏對全局信息的了解，處理機間需要經(jīng)常交換進程狀態(tài)信息。這種交換可以按同步方式進行，也可以按異步方式進行。同步方式簡單，控制方便，但同步時間間隔難以確定。若間隔偏小，則節(jié)點之間信息交換頻繁，通信開銷大，因此可能會抵銷負載平衡所帶來的并行處理效益，若間隔偏大，則達不到動態(tài)平衡負載的目的，在異步方式下，系統(tǒng)只有在某一事件觸發(fā)下才能引起節(jié)點處理機間的信息交換。這里的觸發(fā)事件較典型的有兩種：某節(jié)點機負載過重和某節(jié)點機負載過輕。第34頁，

25、共39頁，2022年，5月20日，10點11分，星期一動態(tài)負載平衡的幾個策略（1）動態(tài)負載平衡算法由以下四個策略組成： (1)遷移策略。當一個新任務在一個節(jié)點上產(chǎn)生時，如果它所在的節(jié)點機的負載超過了負載閥值的上界，則該節(jié)點機就是一個發(fā)送者，另一方面，一個節(jié)點機上的負載降到了閥值Tl(T2)以下，那么該節(jié)點就被認為是一個接收者。 (2)選擇策略。一旦遷移策略確定了發(fā)送者和接收者之后，選擇策略將用于從發(fā)送者那里選擇哪些任務作為遷移對象。最簡單的選擇策略就是選擇一個最新產(chǎn)生的任務，在它未執(zhí)行之前就遷移到接收者那里。選擇一個遷移任務時，應考慮到由遷移所產(chǎn)生的開銷要小，被遷移的任務應具有較長的生命期，否

26、則遷移的開銷將抵消性能的提高。被遷移的任務可以是未被啟動執(zhí)行的任務，也可以是正在運行的任務。第35頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)負載平衡的幾個策略（2） (3)定位策略。一旦確定了一個節(jié)點機是發(fā)送者(或接收者)之后，定位策略負責為其尋找合適的搭檔節(jié)點機。定位策略可有分布式和集中式兩種。分布式定位策略采用輪詢(Polling)方式尋找一個搭檔機，也可以采用廣播查詢方式搜索任何可以進行分載的節(jié)點機。在集中式定位策略中，任何節(jié)點機都可向一個稱為管理者的特殊節(jié)點機發(fā)出請求，由管理者確定一個進行分載的合適的節(jié)點機。第36頁，共39頁，2022年，5月20日，10點11分，星期一動態(tài)負載平衡的幾個策略（3） (4)信息策略。它用于決定什么時候(When)，從什么地方