EN中文

Journal of Geo-information Science >

2014 , Vol. 16 >Issue 4: 517 - 523

DOI: https://doi.org/10.3724/SP.J.1047.2014.00517

Orginal Article

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

  • FAN Junfu , 1, 2* ,
  • MA Ting 1 ,
  • ZHOU Chenghu 1 ,
  • JI Min 3 ,
  • ZHOU Yuke 1, 2 ,
  • XU Tao 1, 2
Expand
  • 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
*Corresponding author: FAN Junfu, E-mail:

Received date: 2013-08-13

  Request revised date: 2013-09-17

  Online published: 2014-07-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

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

Cite this article

FAN Junfu , MA Ting , ZHOU Chenghu , JI Min , ZHOU Yuke , XU Tao . Implementation of Cluster MPI-Based Parallel Polygon Union Algorithm at the Feature Layer Level[J]. Journal of Geo-information Science, 2014 , 16(4) : 517 -523 . DOI: 10.3724/SP.J.1047.2014.00517

1 引言

矢量数据叠加分析将原始要素分割生成新的要素,新要素综合了原来两层或多层要素所具有的属性[1-2]。其中,多边形叠加分析包括差、交、并、异4种基本操作和交集取反、更新、标识、空间连接等衍生操作,具有高算法复杂度和计算时间密集性的特点[3],是矢量数据叠加分析的核心问题[4-6]。多边形叠加合并在GIS分析矢量缓冲区合并计算、制图综合中并非多边形的简化合并,其在土地利用分析、地籍管理等诸多空间分析工具、制图以及行业应用中使用广泛。随着空间数据获取能力的提高,数据规模的快速增长给传统的串行多边形叠加分析算法带来了严峻挑战,而基于集群MPI的并行计算为解决大数据量条件下的高性能叠加分析问题提供了有效手段[6]。
经典的多边形叠加分析基于拓扑数据模型实现,如Mineter基于NTF拓扑数据结构实现的并行矢量叠加分析算法[7]和王少华等人基于非均匀多级网格索引实现的矢量地图叠加分析算法[8]。虽然拓扑叠加能保证结果数据与输入数据的拓扑一致性,但是为较大的数据集建立拓扑关系的过程本身较为耗时,而图层级矢量拓扑数据的划分和并行计算结果的拓扑缝合操作更是非常复杂[7],且在很多应用中拓扑关系并不为用户所关心[9]。近年来,以Shapefile[10]为代表的符合OGC简单要素规范的数据格式发展迅速,获得了商业和开源GIS厂商的广泛支持,已成为矢量空间数据交换的事实标准。符合简单要素规范的非拓扑矢量数据结构不需要预先建立拓扑关系,且冗余存储的几何对象为并行数据划分提供了便利,在实际应用中面临着更为迫切的高性能计算需求。
矢量多边形数据的非拓扑叠加分析,利用计算几何中的多边形裁剪算法实现,如Sutherland- Hodgman算法[11]、Weiler-Atherton算法[12]、Vatti算法[13-14]、Greiner-Hormann算法[15]及其优化算法[16]、基于扫描线和梯形分割思想的多边形裁剪算法[17],及基于交点排序思想的多边形裁剪算法[18]等。上述算法所支持的多边形叠加操作类型的完善程度并不相同,其中,Vatti算法和Greiner-Hormann算法支持多种叠加计算类型和任意形状的多边形输入,是公认的能在有限时间内获得正确计算结果的多边形裁剪算法[16]。本文以Vatti算法来实现多边形合并。目前,已有学者对多边形并行合并方法展开了研究,如陈占龙等在多核环境下实现了基于Hilbert曲线空间划分的多边形并行合并,达到了一定的加速效果[19],但是,对集群MPI环境下如何实现多边形并行合并尚未有深入研究。
本文基于OGC简单要素模型和Vatti算法,在集群MPI环境下对图层级多边形叠加合并算法的并行实现开展研究,对分布式内存模型下图层级多边形叠加过程中要素间“多对多”的映射关系给并行任务映射带来的影响进行分析,提出了6种可行的叠加合并算法并行实现策略。分析说明：在集群MPI环境下基于R树和MySQL精确空间查询的预筛选策略是解决并行任务映射难题及实现图层级多边形并行合并算法的有效途径。

2 叠加分析中的要素映射关系

2.1 “一对多”映射

2个多边形图层叠置时,目标图层中的多边形可能与叠加图层中多个多边形相交,便自然地建立了目标图层到叠加图层“一对多”的映射关系。以多边形叠加求差工具为例,最终计算结果仅包含目标图层要素的几何部分,因此,只需要考虑从目标图层到叠加图层的“一对多”的映射关系,而不需要考虑从叠加图层到目标图层的类似映射关系。

2.2 “多对多”映射

同样,从叠加图层到目标图层存在“一对多”的映射关系,2个图层间不同方向的“一对多”的映射关系构成了复杂的“多对多”映射关系。以多边形合并为例,将叠加图层中要素的几何形状向结果集合输出时,不仅需要处理从目标图层到叠加图层的“一对多”的映射关系,还必须考虑从叠加图层到目标图层的“一对多”的映射关系。因此,问题转变为处理2个图层间要素的“多对多”的映射。

2.3 并行多边形合并算法设计

本文采用Foster提出的PCAM并行算法[20]设计并实现了矢量多边形并行叠加合并算法。该算法的流程如图1所示,包括数据划分、任务映射、并行计算和结果收集输出4个步骤。数据划分以序列划分、空间数据库精确几何搜索功能[20]和R树[22]搜索3种不同策略实现。
Fig.1 Logical flow of MPI-based parallel union algorithm of polygon layers

图1 基于MPI的多边形图层并行合并算法流程

对于上述仅需处理“一对多”映射关系的叠加分析工具实现并行化,基于数据并行思想的要素序列划分方法是简单有效的途径。所谓序列划分是由主节点按照一定指标计算子节点任务量,以要素数量指标为例,假设共有n个计算节点,目标图层共有F个要素,按照要素序列划分后分配到每个计算节点上的任务量f为：
f = F n （1）
节点1负责目标图层第1-f个要素的叠加求差计算,节点2负责第f+1-2f个要素,依次类推。因此,序列划分保证了计算节点操作要素在存储序列上的连续性,主节点仅需要通知子节点计算的起止要素ID编号,每个子节点以单次MPI_Send/MPI_Recv通信即可实现并行任务映射,每次通信的数据包构成如图2所示。
Fig.2 Contents of MPI data package of feature sequence-based data partition strategy

图2 序列划分策略下MPI通信数据包内容

对于叠加的2个图层要素间“多对多”的映射关系,基于R树或者空间数据库的精确几何搜索功能可以实现叠加图层相交多边形的搜索,且搜索结果可作为并行合并算法数据划分的依据。但是,由于空间上相交或相邻的多边形在存储序列上并不一定连续,且可能来自于不同图层,无法与采用序列划分的方法实现任务映射,因此,必须结合数据划分结果和多边形合并算法自身的特点,设计新的并行任务映射方法。

3 并行多边形合并任务映射策略

3.1 隐式数据同步策略（S1）

对同一数据集执行相同条件的R树搜索或精确几何搜索得到的空间查询结果完全相同,因此,主节点与子节点可通过分别执行相同的数据分解过程来实现非连续数据划分结果的多节点“同步”,这种数据同步不同于单机多核并行环境下的内存共享机制或数据通信,称之为“隐式数据同步”,其流程为：
（1）主节点执行R树搜索或基于MySQL的精确空间搜索的数据划分过程,并统计多边形顶点数量作为负载平衡指标进行并行任务分配,每个分组内的多边形可能来自于2个图层;
（2）主节点确定出所有的数据分组后,按照多边形顶点数量进行数据分配,假设有n组数据,可能将第1、2组分配给子节点1,将2、3、4组分配给子节点2,依次类推,直到所有数据分组分配完毕;
（3）主节点将划分好的数据分组起止编号通过单次MPI_Send发送到子节点,同时主节点也执行部分多边形合并工作,主节点到子节点每次通信的数据包内容如图3所示;
（4）子节点接收到主节点下发的任务后,执行与主节点相同的数据分组过程,仅对主节点指定编号的分组所包含的多边形执行合并过程并输出结果,所有节点计算完毕后,算法结束。
Fig.3 Contents of MPI data package of implicit data synchronization strategy

图3 隐式数据同步策略下MPI通信数据包内容

3.2 基于空间范围的轮询通信策略（S2）

考虑R树搜索策略进行数据划分的数据分组间要素彼此必无相交的特点,可通过提取数据分组中要素总体外包矩形并发送给子节点,在子节点进行空间查询的方法实现并行计算的任务映射。该策略避免了在子节点重复执行数据划分过程,其流程为：
（1）主节点执行R树搜索进行数据划分,并统计多边形顶点数量作为负载平衡指标进行并行任务分配,每个分组内多边形可能来自2个图层;
（2）主节点进行循环,每次给某一个计算结点下发一个分组的空间范围,每次通信的数据包内容如图4所示;
Fig.4 Contents of MPI data package of spatial extent-based polling communicating strategy

图4 基于空间范围的轮询通信策略下MPI通信数据包内容

（3）子节点循环接收主节点下发的任务,解析出外包矩形后作为查询条件分别在叠加的2个图层中进行空间搜索,将搜索到的多边形合并,输出结果,等待接收下一个任务或终止指令;
（4）主节点发送完所有的任务后,为每一个进程下发终止指令,主节点不参与多边形合并。

3.3 基于空间范围的打包通信策略（S3）

考虑MPI并行程序多计算少通信的设计原则[23],可将多个数据分组的空间范围数据打包后,采用上述单次MPI_Send发送给各个子节点,子节点接收到数据包后进行解析,遍历每一个外包矩形范围并执行前述的空间查询和多边形合并过程,实现任务映射和并行计算,主节点承担部分多边形合并计算任务,每次MPI通信数据包的内容如图5所示。
Fig.5 Contents of MPI data package of spatial extent-based message packaging communicating strategy

图5 基于空间范围的打包通信策略下MPI通信数据包内容

3.4 直接合并策略（S4）

考虑属性信息在多边形合并过程中被边缘化甚至丢弃的特征,笔者认为可不必拘泥于数据分解的套路实现多边形并行合并。跨过数据划分过程,先将所有多边形要素合并掉,再通过多部分几何对象拆分实现图形分解,达到快速多边形合并的目的,该策略流程为：
（1）主节点统计输入的2个图层的总数据量,依照要素顶点数量进行序列划分;
（2）为每个节点发送起止要素ID值,每次MPI通信数据包内容如图2所示;
（3）子节点接收数据后,在2个图层内读取指定的部分多边形,合并后输出结果;
（4）所有子节点执行完毕后,主节点进行结果后处理：从结果图层取出所有结果并合并后,将初始结果删除,并将合并后的最终结果打散为简单多边形并输出。

3.5 基于MySQL精确空间查询预筛选的直接合并策略（S5）

在直接合并过程中,可通过MySQL空间数据库插件提供的精确几何搜索功能实现要素对象的预筛选,以提高多边形合并操作的命中率。该策略的流程为：
（1）主节点统计输入数据数量,仅对目标图层按照要素顶点数量进行序列划分,每个分组内多边形仅来自目标图层,将目标图层分组信息分发到各个子节点,每次MPI通信数据包内容如图3所示;
（2）子节点接收到消息并加载指定的数据后,在叠加图层内部进行基于几何对象的精确空间搜索,将分组数据与搜索到的多边形全部合并,输出结果;
（3）主节点对各个子节点的计算结果进行后处理（流程同3.4节步骤（4））;
（4）主节点统计叠加图层中未被合并的多边形,将其单独输出到结果集合。

3.6 基于R树搜索预筛选的直接合并策略（S6）

在直接合并过程中,可使用R树进行预筛选代替较为耗时的精确空间搜索过程进行预筛选,既能保持一定的多边形合并命中率,又能避免频繁的数据库IO操作,有望获得更高的计算效率,其流程与3.5节所述类似,唯一区别是在子节点接收到消息并加载指定的数据后,统计每个分组空间范围大小,并在每个计算节点上为叠加图层要素建立内存式R树索引代替MySQL的精确空间搜索。

4 多边形并行合并算法实验及结果分析

实验集群的软硬件配置如表1所示。实验数据（局部）及合并结果如图6所示,2个图层共包含7918个多边形。根据图6（a）中数据,采用策略S1-S6实现的并行多边形合并算法得到图6（b）结果的串行算法时间分别为8.536s、16.267s、16.613s、15.708s、27.168s、11.289s,因此,串行模式下策略S1和S6实现的多边形合并算法较为高效。为进一步分析各个策略的并行性能表现,本文对包含69 391个多边形的数据开展了合并实验,结果如图7所示,其中网络流量数据来自于Ganglia 3.1.7的实时统计数据。
Tab.1 Software and hardware parameters of our experimental cluster

表1 实验集群软硬件配置指标

项目 参数
制造商 IBM
CPU Intel Xeon X5650;2 *6核
内存 6*4GB
网络 千兆网络
磁盘阵列 IBM DS3512 (24*1TB);RAID5
节点数量 计算节点：6;存储节点：1
操作系统 RHEL Server release 6.2 (Santiago)
Fig.6 Experimental data and union results of polygon union algorithm

图6 多边形叠加合并实验数据及合并结果

图7中结果表明,基于策略S1的并行多边形合并算法在串行情形下具有较高的计算效率,但是,并行条件下并未获得相应的加速,并行的效果仅体现为主节点合并计算时间的下降,这对算法整体并无贡献,说明这种以计算换通信的策略难以获得理想的并行加速。以策略S2实现的并行多边形合并算法表现出了合理的并行计算效率,但是,该策略导致网络峰值流量平均增加了约23.0%（正常网络负载约为2.0M Bytes/s）,且频繁的进程间通信带来了大量的时间开销,使并行算法总体时间开销远高于策略S1。与S2类似,策略S3同样造成了约21.8%的网络负载增长,虽然串行多边形合并保持了正常的效率,但是并行算法却表现出了不稳定性,尽管随节点增加算法总时间呈下降趋势,但无法获得令人满意的加速比。基于策略S4实现的并行多边形合并算法的串行计算效率并不理想,主要原因是直接合并操作中包含了大量的无效操作,如不相交多边形的合并。该策略的一个显著优点是并行计算的能力得到了充分的展示,随着计算节点的增加,主进程所需的合并计算时间迅速降低,但不足之处是结果的后处理过程随着节点数增加所需的时间开销增长迅速,且易受数据空间分布的影响而带来严重的不稳定性。策略S5实现的多边形并行合并算法的实验结果显示了与策略S4类似的变化规律,所不同的是该策略性能表现更为稳定,但合并过程和后处理过程也更为耗时,且MySQL精确空间查询需要频繁的数据库IO,导致时间开销大为增长。该策略在处理较小规模的数据集时受数据库IO影响较小,有其应用价值。策略S6实现的多边形并行合并算法不仅具有较高的串行计算效率,且随计算节点的增加,并行计算过程、结果后处理过程,以及算法总时间都保持了合理的下降趋势,尽管仍旧具有一定的不稳定性,但已有明显的改善。
Fig.7 Experimental results of parallel polygon union algorithms based on different task mapping strategies

图7 不同任务映射策略下多边形并行合并实验结果

综上所述,串行前提下可采用策略S1和策略S6实现多边形合并。尽管图7中策略S5的效率低于S6,但MySQL精确空间查询能过滤掉比R树搜索更多的不相交多边形,从而避免过多的无效合并过程,这使得策略S5可能获得与S6类似甚至更高的计算效率。策略S6更适用于处理大数据集或叠加要素多为几何对象真正相交的情况,S5更适用于小数据集且叠加要素间仅外包矩形相交的情形。因此,我们认为策略S5和S6是在集群MPI环境下实现并行多边形合并的2种有效方法,策略S6具有更广泛的适用性。

5 结论

本文对集群MPI环境下,基于OGC简单要素模型的图层级多边形非拓扑并行叠加合并算法的实现方法开展研究,提出了6种并行任务映射策略并实现了对应的并行多边形合并算法,通过实验进行了相应的性能比较。实验结果显示：R树预筛选的直接合并策略具有最高的串行计算效率和优秀的并行性能表现;以MySQL精确空间查询的预筛选过程虽然较为耗时,但可有效地过滤非真正相交多边形的数量,从而提高合并操作的效率。因此,这2种实现策略能较好地解决了集群MPI环境下,多边形并行合并算法所面临的并行任务映射难题。其中,前者更适用于处理大数据集或叠加要素多为几何对象真正相交的情况,后者更适用于小数据集且叠加要素间仅外包矩形相交的情形,两者都是实现图层级多边形并行合并算法的有效途径,且前者具有更广泛的适用性。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
陈述彭,鲁学军,周成虎.地理信息系统导论[M].北京:科学出版社,1999.

[2]
吴信才. 地理信息系统原理、方法及应用[M].北京:电子工业出版社,2002.

[3]
Dowers S, Gittings B M, Mineter M J.Towards a framework for high-performance geocomputation: Handling vector-topology within a distributed service environment[J]. Environment Urban Systems, 2000(24):471-486.

[4]
Goodchild M.F. Statistical aspects of the polygon overlay problem[M]. // Harvard Papers on Geographic Information Systems.Reading, MA, USA: A ddison-Wesley Publishing Company, 1977.

[5]
Shi X.System and methods for parallelizing polygon overlay computation in multiprocessing environment[P]. US Patent, US20120320087A1.Dec. 20, 2012.

[6]
Agarwal D, Puri S, He X, et al.A system for GIS polygonal overlay computation on Linux cluster —— An experience and performance report[C]. // Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012,1433-1439.

[7]
Mineter M J.A software framework to create vector-topology in parallel GIS operations[J]. International Journal of Geographical Information Science, 2003,17(3):203-222.

[8]
王少华,钟耳顺,卢浩,等.基于非均匀多级网格索引的矢量地图叠加分析算法[J].地理与地理信息科学,2013,29(3):17-20.

[9]
陈占龙,吴信才,吴亮.基于单调链和STR树的简单要素模型多边形叠置分析算法[J].测绘学报,2010,39(1):102-108.

[10]
Environmental Systems Research Institute, Inc.. ESRI shapefile technical description[EB/OL]. Jul 1998. URL:

[11]
Sutherland I E, Hodgman G W.Reentrant polygon clipping[J]. Communications of the ACM, 1974(17):32-42.

[12]
Weiler K, Atherton P.Hidden surface removal using polygon area sorting[J]. Computer Graphics, 1977,11(2):214-222.

[13]
Vatti B R.A generic solution to polygon clipping[J]. Communications of the ACM, 1992,35(7):56-63.

[14]
Murta A. A generic polygon clipping library[EB/OL]. 1998. URL:2012-11-28].

[15]
Greiner G, Hormann K.Efficient clipping of arbitrary polygons[J]. ACM Transactions on Graphics, 1998,17(2):71-83.

[16]
刘勇奎,高云,黄有群.一个有效的多边形裁剪算法[J].软件学报,2003,14(4):845-856.

[17]
王结臣,沈定涛,陈焱明,等.一种有效的复杂多边形裁剪算法[J].武汉大学学报(信息科学版),2010,35(3):369-372.

[18]
彭杰,刘南,唐远彬,等.一种基于交点排序的高效多边形裁剪算法[J].浙江大学学报(理学版),2012,39(1):107-111.

[19]
陈占龙,吴亮,刘焕焕.多核环境下Hilbert曲线划分简单要素多边形合并算法[J].计算机应用研究,2012,29(7):2747-2750.

[20]
Foster I.Designing and building parallel programs[M]. Reading, MA, USA: Addison-Wesley Publishing Company, 1995.

[21]
Oracle Corporation and/or Its Affiliates. MySQL 5.6 Manual[EB\OL]. 2013. URL:

[22]
Guttman A.R-trees: A dynamic index structure for spatial searching[C]. // Proceedings of ACM SIGMOD Conference on Management of Data. New York: ACM Press, 1984:47-57.

[23]
张武生,薛巍,李建江,等.MPI并行程序设计实例教程[M].北京:清华大学出版社,2009.

Options
Outlines

/

〈 〉