集群系統(tǒng)的調(diào)度算法研究.pdf

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

2、意，且每個(gè)負(fù)載片都可以被獨(dú)立地處理。本文研究DAG和DLA在集群計(jì)算環(huán)境下的調(diào)度問題。
　　經(jīng)典的DAG調(diào)度模型是以傳統(tǒng)意義上的并行機(jī)為目標(biāo)平臺(tái)的，因此其一些基本假設(shè)不適合于基于消息傳遞的集群環(huán)境。例如獨(dú)立的通信子系統(tǒng)、異步且并發(fā)的通信等等。集群環(huán)境不象傳統(tǒng)意義上的并行機(jī)那樣可靠，而且有些集群系統(tǒng)沒有一個(gè)獨(dú)立的通信子系統(tǒng)。因此，有時(shí)需要用以同步模式進(jìn)行通信的高層接口來隱藏異構(gòu)性以及提高消息傳輸?shù)目煽啃浴Ｈ藗儗?duì)基于異步模式通信的經(jīng)典

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

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

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

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