GIS中8种图层级多核并行多边形叠置分析工具的实现及优化方法

作者：范俊甫,马廷,季民,周玉科,许涛

摘要：GIS中基于简单要素模型的非加权多边形叠置分析有交、差、并、交集取反、联合、更新、标识和空间连接8个基本工具。明确目标图层与叠加图层间多边形的数量对应关系，是实现图层级别并行多边形叠置工具集的首要前提。多边形差、交、标识、更新和空间连接操作需要处理目标多边形到叠加多边形问“一对多”的映射关系；合并、交集取反和联合操作需要处理“多对多”的映射关系。本文从多核数据并行角度，分析了8种多边形叠加分析工具并行实现方法的异同，提出基于改进的分组关联最小化方法实现数据划分，基于顶点数量作为指标的负载平衡计算策略和多种并行优化方法和策略，实现了包含8种操作的并行多边形叠置分析工具集。实验结果表明，改进的分组关联最小化数据划分方法能为多边形联合操作带来约92％的并行加速性能和更鲁棒的并行性；以顶点数量作为负载平衡指标，能以极小的代价为并行求差算法获得约21％的性能提升；二路归并能有效解决多边形并行合并过程中潜在的性能瓶颈；动态调度策略下多边形求交与合并工具具有更高的加速比；使用R树进行要素预过滤能为并行求差获得超过20倍的加速；结构化存储的矢量数据批量加载策略能有效降低因磁盘I／O带来的性能损失。

发文机构：中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室 中国科学院大学 山东科技大学测绘学院

关键词：OPENMP多边形并行叠置数据划分负载平衡任务调度并行优化OpenMPparallel polygon overlappingdata partitionload balancetask scheduleparallel optimi-zation

分类号： TP312[自动化与计算机技术—计算机软件与理论][自动化与计算机技术—计算机科学与技术]