GIS中8種圖層級多核并行多邊形疊置分析工具的實現及優化方法

作者：范俊甫,馬廷,季民,周玉科,許濤

摘要：GIS中基于簡單要素模型的非加權多邊形疊置分析有交、差、并、交集取反、聯合、更新、標識和空間連接8個基本工具。明確目標圖層與疊加圖層間多邊形的數量對應關系，是實現圖層級別并行多邊形疊置工具集的首要前提。多邊形差、交、標識、更新和空間連接操作需要處理目標多邊形到疊加多邊形問“一對多”的映射關系；合并、交集取反和聯合操作需要處理“多對多”的映射關系。本文從多核數據并行角度，分析了8種多邊形疊加分析工具并行實現方法的異同，提出基于改進的分組關聯最小化方法實現數據劃分，基于頂點數量作為指標的負載平衡計算策略和多種并行優化方法和策略，實現了包含8種操作的并行多邊形疊置分析工具集。實驗結果表明，改進的分組關聯最小化數據劃分方法能為多邊形聯合操作帶來約92％的并行加速性能和更魯棒的并行性；以頂點數量作為負載平衡指標，能以極小的代價為并行求差算法獲得約21％的性能提升；二路歸并能有效解決多邊形并行合并過程中潛在的性能瓶頸；動態調度策略下多邊形求交與合并工具具有更高的加速比；使用R樹進行要素預過濾能為并行求差獲得超過20倍的加速；結構化存儲的矢量數據批量加載策略能有效降低因磁盤I／O帶來的性能損失。

發文機構：中國科學院地理科學與資源研究所資源與環境信息系統國家重點實驗室 中國科學院大學 山東科技大學測繪學院

關鍵詞：OPENMP多邊形并行疊置數據劃分負載平衡任務調度并行優化OpenMPparallel polygon overlappingdata partitionload balancetask scheduleparallel optimi-zation

分類號： TP312[自動化與計算機技術—計算機軟件與理論][自動化與計算機技術—計算機科學與技術]