[發明專利]面向并行數字地形分析海量DEM部署與調度方法

有效

• 申請號: 201210321151.8
• 申請日: 2012-09-03
• 公開（公告）號: CN102902590A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 劉學軍;湯國安;宋效東;江嶺
• 申請（專利權）人: 南京師范大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 南京知識律師事務所 32207
• 代理人: 李媛媛

技術領域

本發明涉及一種海量數字高程模型數據管理與調度的方法，具體說，是一種基于分布式并行數字地形分析技術與數據并行計算模型的動態數據分配部署方法。?

背景技術

數字地形分析是在數字高程模型（DEM）上進行地形屬性計算和特征提取的數字信息處理技術。自上世紀60年代以來，數字地形分析已在制圖、土木、水利、交通、水文、農業、規劃等地學領域得到廣泛應用。隨著研究的深入和應用領域的擴展，各應用領域給數字地形分析提出了新的要求。同時，各種新型傳感器，如LiDAR、InSAR、SAR等的出現，使DEM在數據獲取上更加靈活和迅速，網絡通訊技術使得各類DEM，如SRTM?DEM、USGS?DEM得以共享，特別是空間數據基礎設施的興起，區域級DEM的建庫工作已相繼完成，DEM呈現多比例尺、多分辨率的系列化的特征。面對如此浩瀚的、多元化的DEM數據，如何將其轉化為能在社會經濟過程中直接應用的地學信息，并將這些地學信息轉化為地學知識，從而推動地學研究和應用的發展，已經成為國內外相關領域研究的主題。這也迫切要求解決在面對如此海量DEM數據時，現有分析方法及硬件資源在計算能力上嚴重不足甚至是無能為力的問題。并行計算技術為解決這一問題提供了新的思路。并行計算在空間信息科學領域中的應用由來已久，并取得了一些重要成果。但是，人們對DEM數字地形分析的并行處理模式還沒有形成統一而有效的認識，沒有完整的數字地形分析并行軟件；如何運用統一的模式和方法移植和并行化既有的串行DEM數字地形分析算法，傳統的分析算法是否都能夠進行并行化，如何在并行的環境中實現并行與串行算法與處理模式共用與互操作，這都是擺在眾多研究者面前迫切需要解決的問題。?

數字地形分析是地理信息系統（GIS）軟件必備的功能之一，地形因子算法的并行化也是所有與地形相關的復雜地理計算必須考慮的基礎要素。數字地形分析并行計算的有效實現是與地形相關的地理建模及復雜地理計算的基礎與關鍵技術問題。目前，眾多應用領域對DEM數據分辨率及數字地形分析效率的要求越來越高，相應的研究規模也不斷增大，計算資源低利用率和海量數據高分析效率要求之間的矛盾日益突出，歸納起來有以下幾點局限性：?

（1）數字地形分析并行計算要解決的關鍵技術問題包括算法的任務分解、數據的有效拆分及高效融合等。現有數字地形分析的并行處理模式多從單一視角出發，未從整體上對數據、任務、計算環境進行綜合考量，也未見有全面探討三者之間相互關系及量化模型的研究成果，這就使得研究者很難把握處理器負載均衡策略并達到并行效率最大化的目的，也在一定程度上制約了數字地形分析并行技術的發展和應用。?

（2）數字地形分析算法的特點是計算密集和數據密集兼而有之，已有并行計算環境支持下的研究，多集中在某一個方面處理方法，孤立了I/O密集和計算密集問題，并未對任務依賴關系、DEM數據塊和CPU/GPU處理能力匹配做深入研究。現有的串行算法的并行化需要重點考慮算法依賴關系，由于地形數據的非結構化和計算密集特征，使得任務調度、數據并行平臺的搭建等處理相對于結構化數據來說困難得多。?

（3）在目前基于“數據分塊→并行計算→結果合并”的并行計算實施策略中，因為其數據調度模式和計算方法，在計算單元內和基于單一數據集的計算方法并沒有本質差異，尚未形成高效、成熟、穩健的CPU/GPU任務分配機制，尤其是在計算過程中，還較少有針對動態數據分塊的自適應任務、數據調度策略的研究，包括動態地任務加載、任務計算、任務數量預測等。因此，研究適合不同數字地形分析內容的自適應任務分配策略和動態管理機制將是一個新的挑戰。?

發明內容

本發明針對以上缺陷，設計了一套新的并行數字高程模型部署與調度的工業技術方案。該技術流程涵蓋了具有自適應計算節點性能數據分配技術和負載均衡可達的格網DEM數據調度技術兩大關鍵技術環節，該技術方案能夠解決現有并行地形分析算法中DEM低效率管理與調度的問題。?

本發明的基本思想是在并行程序初始化與并行程序執行的過程中，完成不同性質算法數據的統一部署與調度，實現格網DEM數據在并行程序的整個過程中有效地減少通信次數并能夠滿足各類地形分析算法的數據約數關系。在保證并行程序高效率執行的同時，通過最優并行粒度量化體系的相關指標，實現并行粒度的動態控制，從而挖掘并行應用的潛在計算效率。?

為實現上述發明目的，本發明采用的技術方案如下：?

面向并行數字地形分析海量DEM部署與調度方法，其步驟如下：?

步驟1，初始化并行應用系統的信息；?