基于計算智能的并行分布式系統(tǒng)任務調度算法研究.pdf

1、并行與分布式處理一直是當前科技研究、發(fā)展與應用的熱點領域，是天氣預報、核爆炸模擬、電子碰撞模擬、風洞雷諾數值計算以及金融服務等科學計算與數據服務處理領域的重要解決手段。資源共享與管理是并行分布式系統(tǒng)的核心和關鍵技術之一，任務調度對于資源的有效利用起到非常關鍵的作用，是幾十年來學術界研究的重點之一。
　　調度是一個NP難問題，目前的很多啟發(fā)式方法在尋優(yōu)能力等方面仍存在缺陷。隨著人工智能的發(fā)展和成熟，其中一個重要分支——計算智能理論得

2、到廣泛的應用。應用計算智能已解決了環(huán)境、經濟、管理等領域的諸多復雜問題，該方法模擬人類和生物智能行為的計算方法，為搜索、分類等提供了新的求解方式。本文將部分經典的計算智能方法引入到并行與分布式系統(tǒng)的調度策略設計中，以期突破傳統(tǒng)方法在自適應、組合優(yōu)化等方面的局限性，本文的主要研究工作如下:
　　(1)針對并行分布式系統(tǒng)中的多用戶網絡應用，將任務和資源動態(tài)性質轉化為隨機分布，基于排隊論將調度問題定義為一個非線性規(guī)劃問題。但是該方法只能

3、用于特定分布，缺乏適應性。因此引入機器學習方法到調度中，將調度定義為馬爾可夫決策過程，提出了一種能適應任務到達和資源性能動態(tài)性的調度算法。相比于第一種方法，此方法通過學習能夠主動適應分布式系統(tǒng)中存在的不確定性，從而提高調度性能。提出的算法具有較好的魯棒性，其較強的適應能力使得調度之后任務的平均響應時間較小。
　　(2)上述集中式調度方法適用于小規(guī)模的并行分布式系統(tǒng)，在大規(guī)模系統(tǒng)中，分布式調度更為普遍，根據資源特性建立了一個分層的多

4、角色的任務調度框架。在分布式調度中，調度器不僅需要適應任務到達的隨機性和系統(tǒng)負載的動態(tài)性，而且還需要適應其他調度器分配策略的影響。對于其中的合作型調度問題，基于任務流之間存在相互關系將其定義為馬爾可夫決策過程，并且基于強化學習提出了相應的調度算法，使得調度器能夠主動學習任務到達和執(zhí)行的相關知識，以及適應相鄰調度器分配策略。對于自利型調度問題，建立了一個非合作博弈模型，并提出了納什均衡聯合調度策略的分布式學習算法，該算法在任務的期望響應時

5、間和公平性方面均有較好的性能。
　　(3)上述兩個算法的調度模型中沒有考慮數據本地化對調度的影響，而網格中數據密集型應用在計算時需要頻繁地訪問存儲資源，計算和存儲資源調度的協(xié)同成為調度的關鍵。針對網格中數據密集型應用，提出了融合計算和存儲資源的調度模型。該模型將傳統(tǒng)的調度器分為三層，且在每一層扮演不同的角色:在第一層中，為一個總的調度器，它負責收集信息。第二層和第三層中各包含了多個小的調度單元，使得應用程序的調度能夠并行執(zhí)行。在此

6、調度模型基礎上，提出了并行的遺傳算法和并行的禁忌搜索算法用于解決分布式系統(tǒng)中任務調度和存儲資源選擇問題，從而達到減小應用完成總時間的目的。
　　(4)資源的異構性是調度模型中另一個不可忽視的元素，現有并行分布式系統(tǒng)中資源具有不同的可用性是一個重要的特點，在這種情況下，如何提升系統(tǒng)的可用性，滿足更多應用的可用性需求是調度面臨的新問題。針對可用性需求，提出了makespan（調度長度）和可用性雙目標優(yōu)化問題。首先，建立了系統(tǒng)的任務完成