地球信息科学学报

地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (4): 517-523.doi: 10.3724/SP.J.1047.2014.00517

• •    下一篇

基于集群MPI的图层级多边形并行合并算法

范俊甫1,2(), 马廷1, 周成虎1, 季民3, 周玉科1, 许涛1,2   

  1. 1. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京 100101
    2. 中国科学院大学,北京 100049
    3. 山东科技大学测绘学院,青岛 266590
  • 收稿日期:2013-08-13 修回日期:2013-09-17 出版日期:2014-07-10 发布日期:2014-07-10
  • 作者简介:

    作者简介：范俊甫(1985-),男,山东聊城人,博士生,研究方向为并行空间分析算法和遥感信息提取等。E-mail：fanjf@lreis.ac.cn

  • 基金资助:
    国家科技支撑计划(2011BAH06B03、2011BAH24B10);中国科学院重点部署项目（KZZD-EW-07）

Implementation of Cluster MPI-Based Parallel Polygon Union Algorithm at the Feature Layer Level

FAN Junfu1,2*(), MA Ting1, ZHOU Chenghu1, JI Min3, ZHOU Yuke1,2, XU Tao1,2   

  1. 1. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
    2. University of Chinese Academy of Sciences, Beijing 100049, China
    3. College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China
  • Received:2013-08-13 Revised:2013-09-17 Online:2014-07-10 Published:2014-07-10

RichHTML

PDF (PC)

赞

被引次数

7 | 5

摘要：

在集群环境下,基于MPI并行编程模型和OGC简单要素规范进行并行多边形合并时,需要处理叠加图层间要素的“多对多”映射关系,由于空间上相邻的多边形在要素序列上并不一定连续,导致无法按要素序列为子节点分配任务,给并行任务映射带来了困难。本文以集群环境下的并行多边形合并算法为研究对象,通过比较叠加分析中两种多边形映射关系对算法并行化带来的影响,基于R树空间索引、MySQL精确空间查询,以及MPI通信机制,提出了6种不同的并行任务映射策略;通过实验分析和比较了6种策略的优劣。结果显示：基于R树预筛选的直接合并策略,在各算法中具有最高的串行计算效率和优秀的并行性能表现。虽然MySQL精确空间查询的预筛选过程较为耗时,但可有效地过滤掉不真正相交的多边形,从而提高合并操作的效率。因此,在集群MPI环境下,基于R树和MySQL精确空间查询的预筛选策略是解决并行任务映射难题,实现图层级多边形并行合并算法的有效途径。

关键词: 多边形合并, 预筛选, 任务映射, 并行计算, MPI通信

Abstract:

Under the environment of cluster, OGC simple feature specification and MPI parallel programming model-based parallel polygon union algorithm should address the “many-to-many” mapping relationships between features of overlapping layers. However, spatially adjacent features are not necessarily continuous in the storage sequence. It cannot assign parallel tasks to computational nodes of cluster according to feature sequences, which lead to an implementation dilemma on the task mapping procedure of parallel union algorithm. This research is focused on the design and implementation of parallel polygon union algorithm in the cluster parallel environment. We believe that to determine the “one-to-many” or “many-to-many” relationships between polygons of the two overlapping layers is the primary prerequisite to the implementation of parallel polygon overlay algorithms at the feature layer level. Therefore, firstly we analyzed the differences on parallelizing algorithms by comparing impacts brought by the two kinds of feature mapping relationships. Secondly, we proposed six different parallel task mapping strategies based on the R-tree spatial index data structure, the exactly spatial searching functionalities of MySQL and the MPI communication mechanism. Finally, we implemented six parallel polygon union algorithms based on the six task-mapping approaches and conducted experiments to compare the pros and cons of each strategy. The experimental results show that the parallel polygon union algorithm based on R-tree-based feature pre-screening strategy is the most efficient one in serial, which also demonstrates better parallel accelerating effects than others. Furthermore, the strategy of exactly spatial searching based on MySQL shows higher time costs on feature pre-screening, but it can filter out all polygons which do not intersected with geometries which can thereby reduce redundant union operations and improve the computational efficiency. Therefore, the R-tree-based and MySQL exactly spatial searching-based feature pre-screening strategies are effective approaches to solving the parallel task mapping problem and implementing the parallel polygon union algorithm using the MPI programming model under the cluster environment.

Key words: polygon union, pre-screening, task mapping, parallel computing, MPI communicating