異構系統(tǒng)中基于元啟發(fā)方法的并行任務調度算法研究.pdf

1、隨著科學技術的快速發(fā)展，信息技術也飛速發(fā)展起來，超級計算機在工業(yè)、農業(yè)、軍事、航空航天、社會經濟和我們的日常生活的各個領域都扮演了重要的角色，并成為計算機科學和信息技術的一個重要發(fā)展方向。
　　資源管理模型和任務調度策略是異構高性能計算機系統(tǒng)的核心問題和關鍵技術。任務調度策略在滿足任務優(yōu)先級和資源約束的條件下，在可接受的性能指標范圍內，有效地減少了總的執(zhí)行時間并提高了資源的利用率。在過去幾十年，資源管理模型和任務調度策略已成為高性

2、能并行計算領域的重要熱點研究問題。
　　由于異構超級計算機的體系結構和應用程序軟件的復雜性，再加上應用程序對不同資源需要的差異性，使得異構高性能計算系統(tǒng)的并行任務調度變得極為復雜。很多學者的研究結果證明，即便是在化簡后的簡單模型下，在異構高性能計算系統(tǒng)中的并行任務調度問題是一個NP難問題。因此，并行任務調度問題是一個在高性能并行計算領域的具有挑戰(zhàn)性的研究問題。特別是針對現實世界問題的并行任務調度，在可接受的性能和計算復雜度下，要獲

3、得一個問題的最優(yōu)解是不現實的。
　　因此對于這類復雜的問題，往往采用啟發(fā)式算法，其中最最要的一類就是列表調度算法。列表調度的基本思想主要包括：
　　1)任務優(yōu)先隊列的生成。根據一些貪婪的啟發(fā)式方法給每個任務分配一個優(yōu)先級。
　　2)任務到處理機的映射。選擇任務優(yōu)先隊列中的最高優(yōu)先級的任務并將其分配給一個最合適的處理器上，使其完成時間最早。但是由于基于啟發(fā)式的算法的性能在很大程度上依賴啟發(fā)的貪婪方式，對于復雜問題的處理時

4、可能會產生不太理想的結果，特別是當任務調度問題的復雜性增加時。
　　與基于啟發(fā)式算法相反，基于指導的隨機搜索算法(元啟發(fā)式算法)，利用在前期搜索結果的基礎上尋找問題的解，能夠獲得比啟發(fā)式方法更好的解，但算法效率低。所以，在調度質量與收斂速度之間的權衡是必需的。在本文中，提出了一個混合的方式任務調度算法，集成了智能元啟發(fā)式和啟發(fā)式算法的優(yōu)點。所提出的混合方法的性能比啟發(fā)式的調度質量要好，同時比一般的元啟發(fā)式算法的時間開銷要小，收斂速

5、度更快。
　　本文的主要研究工作如下：
　　1.針對異構高性能計算系統(tǒng)中的復雜應用，提出一個有向無環(huán)圖(Directed Acyclic Graph,DAG)任務調度的雙螺旋結構的遺傳算法(Double Helix Structure Genetic Algorithm,DHSGA)，可以廣泛地用于DAG應用程序的調度，該方法將啟發(fā)式方法和元啟發(fā)式算法進行有機的結合，用啟發(fā)式的交叉算子和變異算子產生大量的任務優(yōu)先隊列。DHS

6、GA算法有效地避免了現有啟發(fā)式調度算法的缺點，具有較好的魯棒性和較好的調度質量。
　　2.為了進一步提高算法的性能，提出一個新的算法(Multiple Priority Queueing Genetic Algorithm,MPQGA)來生成初始種群。在算法中使用了三個評價標準：好的“種子”、均勻覆蓋和遺傳多樣性。與從一個隨機生成的解相比較，通過啟發(fā)式技術獲得一個高質量的解可以幫助MPQGA算法更愉快地找到目標的解。均勻覆蓋可以使

7、個體很均勻地分散并覆蓋整個可行解空間。種群的遺傳多樣性可以幫助的遺傳算法盡可能地達到所有的可行解空間。
　　3.為了進一步提高調度性能，基于正態(tài)分布的概率模型，提出了正態(tài)隨機步及正態(tài)分布選擇思想，同時使用在兩個分子之間進行異(XOR)操作來減少分子克隆的機會。最后通過一個偽隨機洗牌方法來生成新的分子，以保持分子多樣性，或消除近親的分子。該混合化學反應優(yōu)化(Hybrid Chemical Reaction Optimization,

8、HCRO)算法在DAG任務調度問題上實現了更好的性能和調度質量。
　　4.基于動態(tài)電壓調節(jié)技術(Dynamic voltage and frequency scaling,DVFS)，提出了具有回收機制的自底向上動態(tài)拉伸的節(jié)能任務再調度算法，用于解決DAG圖任務調度的節(jié)能問題，從而在不影響調度質量的情況下減小系統(tǒng)的能量消耗的目的。
　　5.如何在提升并行任務調度質量的同時，又降低系統(tǒng)能耗，是異構高性能計算系統(tǒng)性能評價體系中的