分布式系統(tǒng)中的調度算法研究.pdf

1、基于分布式系統(tǒng)的高性能并行計算是高性能并行計算的一種重要實現(xiàn)形式。而利用分布式系統(tǒng)進行并行計算，必然要涉及解決并行算法設計、任務劃分、通信的協(xié)調和同步、任務調度等難題，其中任務調度是重中之重。如果任務調度問題得不到解決，或解決得不合理，則有可能導致分布式并行計算效率低下，更有甚者，有可能造成其效率不如單機計算，乃至失敗。 本文全面系統(tǒng)地研究了基于任務復制和遺傳算法的調度算法研究現(xiàn)狀；聯(lián)合應用DAG圖和Gantt圖建立了調度算法模

2、型；針對現(xiàn)有算法存在的不足，提出了一系列相關優(yōu)化或改進算法。 本文的創(chuàng)新點及貢獻在于： 1．本文分析了影響任務調度的因素，在適當假設的前提下，聯(lián)合應用DAG圖和Gantt圖建立了調度算法模型，提出了一系列準確刻畫任務在調度前后狀態(tài)變化的參數(shù)，為提出新的算法打下了基礎。 2．本文分析了現(xiàn)有任務復制算法的不足，提出了適用于同構系統(tǒng)和異構系統(tǒng)的調度算法。本文定義了最大化的處理器空閑時間間隙，充分利用了處理器的能力，進而

3、改善調度性能。在同構系統(tǒng)算法中，本文動態(tài)地確定關鍵任務，克服了現(xiàn)有算法采用貪婪策略存在的不足；同時采用線性和非線性合并策略優(yōu)化處理器數(shù)目，占用了較少的處理器資源。 3．針對現(xiàn)有遺傳調度算法采用不變遺傳運算參數(shù)的不足，本文提出了自適應遺傳調度算法(SAGS)。SAGS算法利用種群關鍵特征的變化趨勢，設計了可變的適應值函數(shù)、交叉概率函數(shù)和變異概率函數(shù)。在迭代進化期間，算法自動調整適應值、交叉概率和變異概率。在不同的階段采用不同遺傳運

4、算參數(shù)，較好地改善了常規(guī)算法存在的在迭代進化過程易出現(xiàn)早熟和進化停滯的現(xiàn)象。 4．本文提出了基于知識的KGS和CPGS兩種遺傳調度算法。在KGS算法中，針對現(xiàn)有算法構造初始種群存在的不足，將關鍵路徑和主序列知識應用于初始種群的構造中，得到了質量優(yōu)良的初始種群，為遺傳算法提供了一個較好的迭代起點，獲得了較好的調度性能。在CPGS算法中，簡化了染色體編碼方案，使其更簡單明了，易于遺傳運算；并優(yōu)化了解碼算法，使其適應性更強，更好地解釋