GIS中8种图层级多核并行多边形叠置分析工具的实现及优化方法
Implementation and optimization of eight parallel polygon overlapping tools with OpenMP at the feature layer level in GIS
查看参考文献21篇
|
文摘
|
GIS中基于简单要素模型的非加权多边形叠置分析有交、差、并、交集取反、联合、更新、标识和空间连接8个基本工具。明确目标图层与叠加图层间多边形的数量对应关系,是实现图层级别并行多边形叠置工具集的首要前提。多边形差、交、标识、更新和空间连接操作需要处理目标多边形到叠加多边形间“一对多”的映射关系;合并、交集取反和联合操作需要处理“多对多”的映射关系。本文从多核数据并行角度,分析了8种多边形叠加分析工具并行实现方法的异同,提出基于改进的分组关联最小化方法实现数据划分,基于顶点数量作为指标的负载平衡计算策略和多种并行优化方法和策略,实现了包含8种操作的并行多边形叠置分析工具集。实验结果表明,改进的分组关联最小化数据划分方法能为多边形联合操作带来约92%的并行加速性能和更鲁棒的并行性;以顶点数量作为负载平衡指标,能以极小的代价为并行求差算法获得约21%的性能提升;二路归并能有效解决多边形并行合并过程中潜在的性能瓶颈;动态调度策略下多边形求交与合并工具具有更高的加速比;使用R树进行要素预过滤能为并行求差获得超过20倍的加速;结构化存储的矢量数据批量加载策略能有效降低因磁盘I/O带来的性能损失。 |
|
其他语种文摘
|
Simple feature model-based non-weighted polygon overlapping analysis operations include eight basic tools: intersection, difference, merge, symmetrical difference, union, update, identity, and spatial join. It is assumed that the determination of the "one-to-many" or "many-to-many" mapping relationships between polygons of the two overlapping layers is the primary prerequisite to the implementation of parallel polygon overlay toolset at the feature layer level. Polygon difference, intersection, identity, update, and spatial join algorithms must address the "one-to-many" mapping relationships between polygons of the overlapping layers. However, the "many-to-many" relationships must be handled by polygon merge, symmetrical difference, and union algorithms. In this research, we analyzed the differences and similarities among the parallel implementation approaches and optimization methods of the eight polygon overlapping tools from the perspective of data parallelism with the OpenMP parallel programming model. We proposed an improved group-relation-minimizing data partition method to realize complex data decomposition without geometry cutting and sewing, and adopted a vertex number indicator-based strategy for load balancing, and several optimization approaches, including the method of avoiding potential bottleneck in polygon merging, strategy for addressing the defect in polygon symmetrical differencing using the XOR operator of the Vatti polygon clipping algorithm, and the strategies of pre-filtering of features with R-tree and bulk loading of structural stored vector data in MySQL. We developed and implemented the parallel polygon overlapping toolset by systematically summarizing the applicative data decomposition method, characters of overlay operations, the Vatti polygon clipping algorithm, load balancing and parallel schedule strategies. The logical flow of parallel polygon union algorithm was introduced as an example to describe the general process of designing parallel polygon overlapping tools. Parallel overlapping case study was also conducted to analyze the effectiveness of the implementation and optimization methods. The experimental results show that the improved group-relation-minimizing data partition method can bring approximately 92% parallel acceleration and more parallel robustness for polygon union; different expected group size specified in the data division method proposed in this research can lead to different parallel speedup benchmarks; the vertex-number based load balancing strategy can give the parallel difference tool about 21% performance improvement; the two-way merge algorithm applied in the parallel merge tool can address the potential performance bottleneck; the dynamic schedule strategy of OpenMP can bring higher speedup than the static and guided schedule strategies; the pre-filtering approach can bring more than 20-fold acceleration for parallel polygon difference; the bulk loading strategy of structural stored vector data can effectively reduce the performance loss due to the disk I/O. The implementation approaches and optimization methods introduced in this study show different applicable features on the developing of the eight overlapping tools. The methods and strategies introduced above can be potential alternatives when launching similar parallelization tasks of other spatial analysis algorithms. This research not only provided theoretical basis and guidance of methodologies for the design and development of parallel polygon overlapping tools at the feature layer level in the multi-core environment, but also presented important practical significance in improving the system resource utilization and computational efficiency of spatial analyses for massive personal and low-cost GIS applications. |
|
来源
|
地理科学进展
,2013,32(12):1835-1844 【核心库】
|
|
关键词
|
OpenMP
;
多边形并行叠置
;
数据划分
;
负载平衡
;
任务调度
;
并行优化
|
|
地址
|
1.
中国科学院地理科学与资源研究所, 资源与环境信息系统国家重点实验室, 北京, 100101
2.
山东科技大学测绘学院, 青岛, 266590
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1007-6301 |
|
基金
|
国家科技支撑计划项目
;
中国科学院重点部署项目
|
|
文献收藏号
|
CSCD:5022637
|
参考文献 共
21
共2页
|
|
1.
Agarwal D. A system for GIS polygonal overlay computation on Linux Cluster: An experience and performance report.
Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International,2012
|
被引
1
次
|
|
|
|
|
2.
Breshears C.
The art of concurrency: A thread monkey's guide to writing parallel applications,2009
|
被引
1
次
|
|
|
|
|
3.
陈述彭.
地理信息系统导论,1999
|
被引
234
次
|
|
|
|
|
4.
Clarke K. Geocomputation's future at the extremes: High performance computing and nanoclients.
Parallel Computing,2003,29(10):1281-1295
|
被引
12
次
|
|
|
|
|
5.
Cramer T. OpenMP programming on intel Xeon Phi coprocessors: An early performance comparison.
Many-core Applications Research Community(MARC) Symposium,2012
|
被引
1
次
|
|
|
|
|
6.
Foster I.
Designing and building parallel programs,1995:27-28
|
被引
1
次
|
|
|
|
|
7.
Geer D. Chip makers turn to multicore processors.
Computer,2005,38(5):11-13
|
被引
13
次
|
|
|
|
|
8.
Goodchild M F. Statistical aspects of the polygon overlay problem.
Harvard papers on geographic information systems,1978:1-29
|
被引
2
次
|
|
|
|
|
9.
Greiner G. Efficient clipping of arbitrary polygons.
ACM Transactions on Graphics,1998,17(2):71-83
|
被引
37
次
|
|
|
|
|
10.
Leonov M.
Comparison of the different algorithms for Polygon Boolean operations,1998
|
被引
1
次
|
|
|
|
|
11.
陆鑫达(译).
并行程序设计原理,2009
|
被引
3
次
|
|
|
|
|
12.
Mineter M J. Parallel processing for geographical applications: A layered approach.
Journal of Geographical Systems,1999,1(1):61-74
|
被引
4
次
|
|
|
|
|
13.
Mineter M J. A software framework to create vector-topology in parallel GIS operations.
International Journal of Geographical Information Science,2003,17(3):203-222
|
被引
9
次
|
|
|
|
|
14.
Ramsey P.
(Much) Faster Unions in PostGIS 1.4,2009
|
被引
1
次
|
|
|
|
|
15.
Shi X.
System and methods for parallelizing polygon overlay computation in multiprocessing environment. US Patent Application NO.: 20120320087 A1,2012
|
被引
1
次
|
|
|
|
|
16.
Turton I. High-performance computing and geography: Developments, issues, and case studies.
Environment and Planning A,1998,30(10):1839-1856
|
被引
5
次
|
|
|
|
|
17.
Vatti B R. A generic solution to polygon clipping.
Communications of the ACM,1992,35(7):56-63
|
被引
51
次
|
|
|
|
|
18.
Wang F. A parallel intersection algorithm for vector polygon overlay.
Computer Graphics and Applications, IEEE,1993,13(2):74-81
|
被引
1
次
|
|
|
|
|
19.
王结臣. 并行空间分析算法研究进展及评述.
地理与地理信息科学,2011,27(6):1-5
|
被引
21
次
|
|
|
|
|
20.
Waugh T C. An algorithm for polygon overlay using cooperative parallel processing.
International Journal of Geographical Information Systems,1992,6(6):457-467
|
被引
4
次
|
|
|
|
|
了解气象卫星更多信息，请访问