《面向多核異構並行系統的隨機調度策略與算法研究》是依託湖南大學，由李肯立擔任項目負責人的面上項目。
基本介紹
- 中文名：面向多核異構並行系統的隨機調度策略與算法研究
- 項目類別：面上項目
- 項目負責人：李肯立
- 依託單位：湖南大學
中文摘要,結題摘要,
中文摘要
並行分布計算是當前計算機科學與技術的研究熱點之一,是天氣預報、核爆炸模擬以及金融服務等的重要解決手段.調度策略是保證系統性能的關鍵因素.針對多核異構系統的隨機任務調度目前仍面臨挑戰.本課題擬採用多元線性回歸方法,從理論和實驗方面分析典型任務計算量的隨機分布，確定其機率分布模型，借鑑利用基於同構系統獨立任務隨機調度的最新理論成果,建立非獨立任務隨機調度數學模型,使用凸二次線性規劃或隨機多維背包最佳化方法對其求解,以獲得隨機調度的理論近似結果；據此研究基於隨機性的獨立和非獨立任務的調度策略與機制,提出基於任務執行時間的期望、方差與關鍵路徑的隨機調度算法,針對典型並行套用,構建多核異構系統隨機調度實驗平台對算法性能進行實驗驗證.本研究將不僅為隨機調度算法的設計提供新的嘗試,從而為並行系統套用效率的提高奠定基礎，還將推進並行處理的研究深度，推動計算機科學與其它學科的交叉研究與發展.
結題摘要
項目執行三年來，緊跟高性能計算最新發展趨勢，在隨機調度理論和套用上做了系統深入的研究工作，對基於隨機性的超級計算機調度器的構建進行了探索. （1） 在調度理論與方法研究方面： 系統深入地分析了大規模並行系統任務執行時間不確定性的原因，並用數學方法對其進行建模，從理論上研究了任務執行時間服從幾種典型機率分布的任務，並對其在並行系統的可調度性進行了分析，證明基於DAG模型隨機任務調度長度的下限是以任務期望構成的確定型任務調度長度。提出了一種基於博弈論的多項式時間近似調度算法，是目前近似程度最高的理論結果. 根據並行系統任務的可靠性和任務計算量隨機性，提出了考慮可信性的任務調度理論與方法，克服以任務執行平均值、中間值、最好值或最壞值等方法給任務調度帶來的不足，提出異構並行計算系統計算能力異構因子a，並依此實現任務優先權計算和處理機選擇。在此基礎上，提出基於任務複製的表調度算法(HEFD) 以及考慮任務執行行為安全開銷的調度模型和調度算法SDS。實驗結果表明所提出的算法一定程度上解決了系統可靠性條件下的隨機調度問題. 針對基於複製的調度算法造成的資源浪費和能耗開銷大的缺點，提出了一種冗餘副j本刪除調度算法。傳統的基於複製的調度算法普遍具有貪婪性，通過複製任務使當前任務最早完成，但某些任務的提前完成並不能減少整體的makepan，反而造成資源和能耗開銷。提出的冗餘副j本刪除調度算法可對所有基於複製的算法進行最佳化，減少其複製個數，從而達到節能的目的。 （2）在調度與理論的高性能計算套用方面 根據BEKELY大學並行計算中心的研究結果，對並行計算的13個典型計算模組中的FFT,矩陣稀疏線性代數、蒙特卡羅方法、分子動力學等4個數值計算模組和圖遍歷以及回溯和分支限界等2個非數值計算模組在CPU-GPU異構並行系統的並行計算性能及相應的調度分配方法以及高效並行實現進行了深入研究，取得了較高的加速比和可擴展性. 在上述模組的異構並行運算和調度理論成果基礎上，設計和實現了一系列典型高性能套用可擴展並行算法,順利完成了項目申請書的預期研究目標.
