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

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

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

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-treebased 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.