集群系統的調度算法研究.pdf

1、性能是應用的關鍵問題，調度又是性能之根本所在。計算機系統體系結構的發(fā)展以及對計算需求的持續(xù)增長，也不斷給調度問題賦予新的內涵并且提出新的挑戰(zhàn)，調度一直是并行與分布式計算研究的熱點問題。按照劃分方式，大致上可以將并行應用分成任務并行和數據并行兩類。有向無環(huán)圖(DAG)是表達任務并行應用的最常用模型。在數據并行應用中有一種重要類型，稱為負載可任意劃分的應用(DLA)，這種應用所處理的負載可以被劃分成任意多個負載片，每個負載片的尺寸也可以是任

2、意，且每個負載片都可以被獨立地處理。本文研究DAG和DLA在集群計算環(huán)境下的調度問題。
　　經典的DAG調度模型是以傳統意義上的并行機為目標平臺的，因此其一些基本假設不適合于基于消息傳遞的集群環(huán)境。例如獨立的通信子系統、異步且并發(fā)的通信等等。集群環(huán)境不象傳統意義上的并行機那樣可靠，而且有些集群系統沒有一個獨立的通信子系統。因此，有時需要用以同步模式進行通信的高層接口來隱藏異構性以及提高消息傳輸的可靠性。人們對基于異步模式通信的經典

3、DAG調度問題進行了廣泛而深入的研究并且提出了很多啟發(fā)式算法，但是這些算法所產生的調度結果不能用于以同步模式通信的并行程序。本文分析了同步通信模式給DAG的調度帶來的問題，并提出了一個基于參數關系圖的調度算法PRGSC。該算法通過在調度的過程中維護任務的時間參數之間的關系來檢測死鎖，該方法不增加調度算法的復雜度并可以用于其他算法。PRGSC算法在調度一個節(jié)點時既考慮了對未調度部分的影響也考慮了對已調度部分的影響，因此能降低重要節(jié)點的運行

4、時間而降低整個應用的運行時間。實驗表明，本文所提出的PRGSC算法比以往的算法有更好的調度質量。
　　以往關于DLA調度的研究，都是基于應用對負載的劃分是沒有交叉的、完全的前提，但現實中的一些應用可能要求劃分是重疊的或者是每個處理器還需要一些輔助信息。本文用控制信息表示除了要處理的負載之外為了完成計算所必須的重疊的或輔助的信息。本文研究了這種有控制信息的DLA的調度問題，分別在主處理器（擁有負載的處理器）有前端和沒有前端兩種平臺上

5、，分析了平均劃分、LIFO和FIFO三種調度策略，得到了它們的解析解。討論了三種策略的可用處理器數目的范圍，并得到了使處理時間最小的最優(yōu)處理器數目?；谶@些解析解，分析了在這個新模型下三種策略各自所具有的性質，并在此基礎上對這三種策略的調度性能進行了嚴格的比較分析。我們的研究結果表明，與忽略控制信息的情況不同，無論主處理器是否有前端，在考慮控制信息的情況下，FIFO總是能獲得這三種調度策略中的最好解。這一結論也說明了在模型中引入控制信息

6、的重要性。
　　負載可任意劃分應用的調度問題中，有兩種分配負載的策略。一種是一個處理器在開始處理負載之前得到全部數據，被稱為一次分配策略。另外一種是分成多次向處理器發(fā)送負載。這種被稱為多次分配的調度策略能更好地重疊通信和計算而最終降低整個應用的響應時間?；诙啻畏峙涞恼{度比一次分配更難分析，以往的研究中忽略了對處理結果的傳輸。本文提出了一個基于多次通信策略的算法，稱為CAMR算法，它通過交替地傳輸輸入數據和接收處理結果，更好地重疊