任務調(diào)度、負載平衡技術應用和停機準則_第1頁
任務調(diào)度、負載平衡技術應用和停機準則_第2頁
任務調(diào)度、負載平衡技術應用和停機準則_第3頁
任務調(diào)度、負載平衡技術應用和停機準則_第4頁
任務調(diào)度、負載平衡技術應用和停機準則_第5頁
已閱讀5頁,還剩35頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、任務調(diào)度、負載平衡技術應用和停機準則2022-3-142任務調(diào)度、負載平衡技術與停機準則任務調(diào)度、負載平衡技術與停機準則(續(xù)續(xù))n負載平衡是減少進程空閑的必要條件,但并非充負載平衡是減少進程空閑的必要條件,但并非充分條件分條件123456789101112P0P1P2P3開始 同步 結束t=0 t=2 t=32022-3-143任務調(diào)度、負載平衡技術與停機準則任務調(diào)度、負載平衡技術與停機準則(續(xù)續(xù))n負載平衡是減少進程空閑的必要條件,但并非充負載平衡是減少進程空閑的必要條件,但并非充分條件分條件147102581136912P0P1P2P3開始開始 同步同步 結束結束t = 0 t = 3 t

2、 = 0 t = 3 t=6t=62022-3-144任務調(diào)度、負載平衡技術與停機準則任務調(diào)度、負載平衡技術與停機準則(續(xù)續(xù))n靜態(tài)調(diào)度靜態(tài)調(diào)度v在算法執(zhí)行之前事先進行任務分配在算法執(zhí)行之前事先進行任務分配 v對靜態(tài)生成的任務,可用靜態(tài)調(diào)度,也可用動態(tài)調(diào)度對靜態(tài)生成的任務,可用靜態(tài)調(diào)度,也可用動態(tài)調(diào)度v采用靜態(tài)調(diào)度時,并行算法的設計與編程比較容易采用靜態(tài)調(diào)度時,并行算法的設計與編程比較容易n動態(tài)調(diào)度動態(tài)調(diào)度v程序執(zhí)行過程中在進程間分配任務程序執(zhí)行過程中在進程間分配任務v不知道任務的計算量,靜態(tài)調(diào)度有可能引起嚴重的負不知道任務的計算量,靜態(tài)調(diào)度有可能引起嚴重的負載不平衡,或者任務是動態(tài)生成的載不

3、平衡,或者任務是動態(tài)生成的 v采用動態(tài)調(diào)度時,并行算法的設計與編程比較復雜采用動態(tài)調(diào)度時,并行算法的設計與編程比較復雜2022-3-145靜態(tài)調(diào)度策略靜態(tài)調(diào)度策略n基于數(shù)據(jù)劃分的靜態(tài)調(diào)度基于數(shù)據(jù)劃分的靜態(tài)調(diào)度n基于任務分解的靜態(tài)調(diào)度基于任務分解的靜態(tài)調(diào)度n混合調(diào)度混合調(diào)度2022-3-146基于數(shù)據(jù)劃分的靜態(tài)調(diào)度基于數(shù)據(jù)劃分的靜態(tài)調(diào)度n數(shù)組分布方法數(shù)組分布方法v塊分布:將數(shù)組中連續(xù)的部分數(shù)據(jù)分布塊分布:將數(shù)組中連續(xù)的部分數(shù)據(jù)分布到進程上到進程上v循環(huán)塊分布與循環(huán)分布循環(huán)塊分布與循環(huán)分布v隨機塊分布隨機塊分布n圖劃分方法圖劃分方法2022-3-147塊分布塊分布n一個一個d d維數(shù)組通過沿某幾個

4、具體的維數(shù)組通過沿某幾個具體的維,將一個數(shù)據(jù)塊分布到進程上維,將一個數(shù)據(jù)塊分布到進程上n當交互具有局部性時,塊分布十當交互具有局部性時,塊分布十分有效分有效n可以分為一維塊分布與多維塊分可以分為一維塊分布與多維塊分布兩類布兩類2022-3-148塊分布塊分布(續(xù)續(xù))n一維塊分布示例一維塊分布示例按行塊分布按行塊分布P0P2P3P1按列塊分布按列塊分布P0 P1P2 P32022-3-149塊分布塊分布(續(xù)續(xù))n二維塊分布示例二維塊分布示例4 4 4 4塊分布塊分布P0P8P12P4P1P9P13P5P2P10P14P6P3P11P15P72 2 4 4塊分布塊分布P0P1P2P3P4P5P6P

5、72022-3-1410塊分布塊分布(續(xù)續(xù))n一般高維分布下可以利用更多的進程一般高維分布下可以利用更多的進程來并行計算來并行計算v矩陣乘法就是典型例子矩陣乘法就是典型例子n對許多問題,高維分布除了提供更高對許多問題,高維分布除了提供更高的并發(fā)度外,也有助于減少進程交互的并發(fā)度外,也有助于減少進程交互v矩陣乘法的例子矩陣乘法的例子2022-3-1411塊分布塊分布(續(xù)續(xù))n二維分布有利于減少矩陣乘法中的進程交互開銷二維分布有利于減少矩陣乘法中的進程交互開銷ACBP0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10

6、P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15AP0P2P3P1CP0P2P3P1BP0P2P3P12022-3-1412循環(huán)塊分布循環(huán)塊分布n當對每個矩陣元素,其計算量相差比較大當對每個矩陣元素,其計算量相差比較大時,采用塊分布將引起嚴重的負載不平衡。時,采用塊分布將引起嚴重的負載不平衡。例如,稠密矩陣的例如,稠密矩陣的LULU分解分解Col_LU(A, n)For k = 1 to n do For j = k to n do A(j,k) := A(j,k) / A(k,k); For j = k+1 to n do For i = k+1

7、 to n do A(i,j) := A(i,j) A(i,k) A(k,j); EndforEndfor2022-3-1413循環(huán)塊分布循環(huán)塊分布(續(xù))續(xù))n采用采用3 3 3 3塊分布時形成的塊分布時形成的1414個任務個任務 2022-3-1414循環(huán)塊分布循環(huán)塊分布(續(xù))續(xù))n循環(huán)塊分布是塊分布的一種變種,它有利循環(huán)塊分布是塊分布的一種變種,它有利于減輕負載不平衡程度與減少進程空閑于減輕負載不平衡程度與減少進程空閑n將數(shù)組劃分為多個塊,使塊的數(shù)量遠大于將數(shù)組劃分為多個塊,使塊的數(shù)量遠大于進程數(shù),再將塊以循環(huán)方式分布到進程進程數(shù),再將塊以循環(huán)方式分布到進程n當每個塊只有一個單位時,稱為循

8、環(huán)分布當每個塊只有一個單位時,稱為循環(huán)分布n塊分布也是循環(huán)分布的特例塊分布也是循環(huán)分布的特例2022-3-1415循環(huán)塊分布循環(huán)塊分布(續(xù))續(xù))n一維循環(huán)塊分布與二維循環(huán)塊分布的例子一維循環(huán)塊分布與二維循環(huán)塊分布的例子一維循環(huán)塊分布一維循環(huán)塊分布P0P1P2P3P0P1P2P3P0P1P2P32 2循環(huán)塊分布循環(huán)塊分布P0P0P2P2P1P1P3P3P0P0P2P2P1P1P3P32022-3-1416隨機塊分布隨機塊分布 n當任務分布具有一些特殊模式時,塊循環(huán)分布可能也不當任務分布具有一些特殊模式時,塊循環(huán)分布可能也不能使得負載平衡,例如能使得負載平衡,例如08124191352101463

9、111570812419135210146311157081241913521014631115708124191352101463111572022-3-1417隨機塊分布隨機塊分布(續(xù)續(xù))n引入長度為引入長度為 p p的數(shù)組的數(shù)組V V,對對0 0 j j =k)(i=k)向某向某個進程個進程P Pj j(j k)(j k)發(fā)送消息發(fā)送消息,則將進程則將進程P Pi i標志標志為黑色,否則為白色;為黑色,否則為白色;v如果令牌傳輸時遇到黑色進程,則將令牌變?yōu)槿绻钆苽鬏敃r遇到黑色進程,則將令牌變?yōu)楹谏谏? ,令牌傳出后,進程變?yōu)榘咨钆苽鞒龊螅M程變?yōu)榘咨?;v如果如果P P0 0接收到白

10、色令牌,則所有進程都已經(jīng)終接收到白色令牌,則所有進程都已經(jīng)終止,如果接收到黑色令牌,則繼續(xù)傳遞。止,如果接收到黑色令牌,則繼續(xù)傳遞。2022-3-1440固定能量檢測算法固定能量檢測算法n能量的意義與令牌的意義很相似,但這里的能量有一個能量的意義與令牌的意義很相似,但這里的能量有一個具體的數(shù)值具體的數(shù)值n任務開始執(zhí)行之前,所有能量都在主進程中,它將部分任務開始執(zhí)行之前,所有能量都在主進程中,它將部分任務以及與任務對應的能量傳給請求任務的進程任務以及與任務對應的能量傳給請求任務的進程n進程收到任務請求,也將其上的部分任務和對應的能量進程收到任務請求,也將其上的部分任務和對應的能量傳給請求進程傳給請求進程n一個進程完成當前任務后,需要將其上的能量傳給主進一個進程完成當前任務后,需要將其上的能量傳給主進程或任務的來源進程。對后一種情

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論