帮助 关于我们

返回检索结果

GIS中8种图层级多核并行多边形叠置分析工具的实现及优化方法
Implementation and optimization of eight parallel polygon overlapping tools with OpenMP at the feature layer level in GIS

查看参考文献21篇

范俊甫 1   马廷 1   季民 2   周玉科 1   许涛 1  
文摘 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 CSCD被引 1 次    
2.  Breshears C. The art of concurrency: A thread monkey's guide to writing parallel applications,2009 CSCD被引 1 次    
3.  陈述彭. 地理信息系统导论,1999 CSCD被引 234 次    
4.  Clarke K. Geocomputation's future at the extremes: High performance computing and nanoclients. Parallel Computing,2003,29(10):1281-1295 CSCD被引 12 次    
5.  Cramer T. OpenMP programming on intel Xeon Phi coprocessors: An early performance comparison. Many-core Applications Research Community(MARC) Symposium,2012 CSCD被引 1 次    
6.  Foster I. Designing and building parallel programs,1995:27-28 CSCD被引 1 次    
7.  Geer D. Chip makers turn to multicore processors. Computer,2005,38(5):11-13 CSCD被引 13 次    
8.  Goodchild M F. Statistical aspects of the polygon overlay problem. Harvard papers on geographic information systems,1978:1-29 CSCD被引 2 次    
9.  Greiner G. Efficient clipping of arbitrary polygons. ACM Transactions on Graphics,1998,17(2):71-83 CSCD被引 38 次    
10.  Leonov M. Comparison of the different algorithms for Polygon Boolean operations,1998 CSCD被引 1 次    
11.  陆鑫达(译). 并行程序设计原理,2009 CSCD被引 3 次    
12.  Mineter M J. Parallel processing for geographical applications: A layered approach. Journal of Geographical Systems,1999,1(1):61-74 CSCD被引 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 CSCD被引 9 次    
14.  Ramsey P. (Much) Faster Unions in PostGIS 1.4,2009 CSCD被引 1 次    
15.  Shi X. System and methods for parallelizing polygon overlay computation in multiprocessing environment. US Patent Application NO.: 20120320087 A1,2012 CSCD被引 1 次    
16.  Turton I. High-performance computing and geography: Developments, issues, and case studies. Environment and Planning A,1998,30(10):1839-1856 CSCD被引 5 次    
17.  Vatti B R. A generic solution to polygon clipping. Communications of the ACM,1992,35(7):56-63 CSCD被引 54 次    
18.  Wang F. A parallel intersection algorithm for vector polygon overlay. Computer Graphics and Applications, IEEE,1993,13(2):74-81 CSCD被引 1 次    
19.  王结臣. 并行空间分析算法研究进展及评述. 地理与地理信息科学,2011,27(6):1-5 CSCD被引 22 次    
20.  Waugh T C. An algorithm for polygon overlay using cooperative parallel processing. International Journal of Geographical Information Systems,1992,6(6):457-467 CSCD被引 4 次    
引证文献 2 篇

1 范俊甫 RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析 测绘学报,2015,44(3):338-345
CSCD被引 6 次

2 高琪 多种数据划分方法下D8算法的多核并行化实验对比 地理与地理信息科学,2017,33(2):63-68
CSCD被引 1 次

显示所有2篇文献

论文科学数据集
PlumX Metrics
相关文献

 作者相关
 关键词相关
 参考文献相关

版权所有 ©2008 中国科学院文献情报中心 制作维护：中国科学院文献情报中心
地址：北京中关村北四环西路33号 邮政编码：100190 联系电话：(010)82627496 E-mail:cscd@mail.las.ac.cn 京ICP备05002861号-4 | 京公网安备11010802043238号