《基於超圖分割的空間數據並行處理任務調度機制研究》是依託武漢大學，由關雪峰擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於超圖分割的空間數據並行處理任務調度機制研究
- 項目類別：青年科學基金項目
- 項目負責人：關雪峰
- 依託單位：武漢大學
項目摘要,結題摘要,
項目摘要
採用分散式計算平台來並行處理海量空間數據是當前的一個研究熱點。現有並行空間數據處理系統，還沒有成熟通用的任務調度模型和調度策略，多直接借用基於有向無環圖的調度手段，然而在模型上無法包容海量數據要素，在策略上忽略數據I/O成本，導致並行計算資源無法高效利用。本項目的研究將圍繞海量空間數據並行處理的任務調度機制展開，首先利用超圖理論建立任務、數據、平台一體化的調度模型，顧及數據的空間鄰近性及任務的層次性，以期解決調度模型完整性問題；進而提出實現任務負載均衡及傳輸數據量最小的調度目標，制定基於超圖分割的任務調度策略；同時利用處理算法的局部空間數據參與特徵對調度策略進行最佳化，簡化其時間複雜度；最後設計開發分散式的調度原型系統，對上述調度模型及策略進行驗證。該調度機制的研究與套用將大大最佳化空間數據處理過程中I/O傳輸成本，縮短整體處理時間，提高並行處理效率，實現數據到信息的快速轉化。
結題摘要
海量空間數據處理作為典型的數據密集型套用，採用分散式計算平台來並行處理海量空間數據是當前的一個研究熱點。目前在並行空間數據處理系統設計過程中，還沒有成熟通用的任務調度模型和調度策略可使用，大多直接借用傳統計算密集型套用的調度手段。傳統計算密集型套用，基於有向無環圖（Directed Acyclic Graph， DAG）的任務建模和調度方案已經比較成熟。但是直接將DAG方案套用到空間數據處理，調度模型上無法包容海量數據要素，調度策略的制定忽略空間數據I/O傳輸成本，進而無法實現處理任務的最優調度。因此在分散式計算平台如何實現海量空間數據並行處理任務的高效調度一個亟待解決的問題。 本項目研究：（1）首先利用超圖理論建立了全新的面向海量空間數據處理的任務調度模型，將任務和數據映射為超圖的超邊和數據節點，相較傳統基於有向無環圖的調度模型，涵蓋了海量空間數據要素，同時顧及數據的空間鄰近性及任務的層次性，解決了現有調度模型完整性問題；（2）以全新的超圖調度模型為基礎，提出了實現任務負載均衡及傳輸數據量最小的調度目標，制定基於超圖分割的任務調度策略；（3）考慮到單一超圖分割結果非最優，提出了疊代精化的Hypergraph+調度算法，超圖模型各參數通過疊代收斂精確，傳輸數據減少量最佳化至最大；（4）最後設計了分散式的調度原型系統，對上述調度模型及策略進行套用。 現有實驗結果顯示，與現有MinMin、XSufferage和Hypergraph算法相比， Hypergraph+算法makespan最低，即完成所有計算任務所需要的時間最少；隨著任務數量的增加，減少的傳輸數據量對比，MinMin算法達到輸入總數據量的40%，XSufferage算法為55%，Hypergraph算法為80%，而Hypergraph+算法縮減達到了輸入總數據量的85%，該算法傳輸的數據量最少，有效的解決了並行處理的瓶頸問題。 因此基於超圖分割的空間數據並行處理任務調度機制研究與套用，大大最佳化空間數據處理過程中I/O傳輸成本，縮短了整體處理時間，提高了並行處理效率，有助於實現數據到信息的快速轉化。
