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

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

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

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

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

6、P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15AP0P2P3P1CP0P2P3P1BP0P2P3P12022-3-1412循環塊分布循環塊分布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循環塊分布循環塊分布(續）續）n采用采用3 3 3 3塊分布時形成的塊分布時形成的1414個任務個任務 2022-3-1414循環塊分布循環塊分布(續）續）n循環塊分布是塊分布的一種變種，它有利循環塊分布是塊分布的一種變種，它有利于減輕負載不平衡程度與減少進程空閑于減輕負載不平衡程度與減少進程空閑n將數組劃分為多個塊，使塊的數量遠大于將數組劃分為多個塊，使塊的數量遠大于進程數，再將塊以循環方式分布到進程進程數，再將塊以循環方式分布到進程n當每個塊只有一個單位時，稱為循

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

9、111570812419135210146311157081241913521014631115708124191352101463111572022-3-1417隨機塊分布隨機塊分布(續續)n引入長度為引入長度為 p p的數組的數組V V，對對0 0 j j =k)(i=k)向某向某個進程個進程P Pj j(j k)(j k)發送消息發送消息，則將進程則將進程P Pi i標志標志為黑色，否則為白色；為黑色，否則為白色；v如果令牌傳輸時遇到黑色進程，則將令牌變為如果令牌傳輸時遇到黑色進程，則將令牌變為黑色黑色, ,令牌傳出后，進程變為白色令牌傳出后，進程變為白色；v如果如果P P0 0接收到白

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