GPU加速的多边形叠加分析
Accelerating polygon overlay analysis by GPU
查看参考文献20篇
|
文摘
|
叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。 |
|
其他语种文摘
|
Overlay analysis is one of the most important analysis capabilities of geographic information systems. Overlay analysis with polygon layers is a time-intensive process. To improve time efficiency, modern approaches of overlay analysis are generally divided into two stages, filtering and refinement (also known as polygon clipping). A great deal of effort has been taken to significantly reduce the number of candidates in the first stage (filtering) in order to alleviate the workload of the second stage (refinement). However, the second stage is still the most time-consuming part of the process. In this paper we applied GPGPU (General-purpose Graphics Processing Unit) computing to the two key stages of overlay analysis: MBR filtering (part of the filtering) and polygon clipping, and restricted the search area to polygon intersection analysis. We proposed GPU-based MBR filtering algorithm by combining histogram and parallel prefix-sum algorithms, and introduced GPU-based polygon clipping algorithm by improving Weiler-Atherton algorithm. There are two differences between our algorithm and Weiler-Atherton algorithm: First, it adopts a new method to insert intersecting points which reduces computing workload, making it more suitable to be implemented on GPU. Second, it simplifies the algorithm used to mark entry and exit points. Furthermore, based on dynamic programming, we provided a solution to avoid load imbalance caused by spatial data skew. The improved algorithms and the solution have been applied to filtering stage and refinement stage to achieve better performance. The experimental results show that the speedup ratio between GPU-based MBR filtering implementation and CPU implementation is 3.8. The GPU-based polygon clipping implementation runs 3.4 times faster than the CPU's. Overall, GPU-accelerated polygon intersection implementation achieves performance that is up to three times faster than CPU implementation. Accelerating other types of overlay analyses, such as union, difference, etc., by GPU needs to be studied and implemented in the future. |
|
来源
|
地理科学进展
,2013,32(1):114-120 【核心库】
|
|
关键词
|
叠加分析
;
图形处理单元
;
多边形剪裁
;
并行计算
;
空间分析
|
|
地址
|
中国科学院地理科学与资源研究所, 资源与环境信息系统国家重点实验室, 北京, 100101
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1007-6301 |
|
学科
|
测绘学 |
|
基金
|
国家自然科学基金
;
国家863计划
|
|
文献收藏号
|
CSCD:4756500
|
参考文献 共
20
共1页
|
|
1.
Brinkhoff T. Efficient processing of spatial joins using R-trees.
Proceedings of ACM SIGMOD International Conference on Management of Data,1993:237-246
|
CSCD被引
1
次
|
|
|
|
|
2.
陈述彭.
地理信息系统导论,1999:125-126
|
CSCD被引
1
次
|
|
|
|
|
3.
Garcia V. Fast k-nearest neighbor search using GPU.
Proceedings of the Workshop on Computer Vision on GPU,2008:1-6
|
CSCD被引
1
次
|
|
|
|
|
4.
Greiner G. Efficient clipping of arbitrary polygons.
Journal of ACM Transactions of Graphics,1998,17(2):71-83
|
CSCD被引
38
次
|
|
|
|
|
5.
Harish P. Accelerating large graph algorithms on the GPU using CUDA.
Proceedings High Performance Computing, 4873,2007:197-208
|
CSCD被引
1
次
|
|
|
|
|
6.
Harris M. Parallel prefix sum (scan) with CUDA.
GPU Gems 3,2007:851-876
|
CSCD被引
5
次
|
|
|
|
|
7.
Hillis W D. Data parallel algorithms.
Communications of the ACM,1986,92(2):1170-1183
|
CSCD被引
13
次
|
|
|
|
|
8.
Horn D. Stream reduction operations for GPGPU Applications.
2005. GPU Gems 2,1992:573-589
|
CSCD被引
1
次
|
|
|
|
|
9.
李丹. GPU-CA 模型及大尺度土地利用变化模拟.
科学通报,2011,57(11):959-969
|
CSCD被引
1
次
|
|
|
|
|
10.
刘勇奎. 一个有效的多边形裁剪算法.
软件学报,2003,14(4):845-856
|
CSCD被引
35
次
|
|
|
|
|
11.
张晶(译).
地理信息系统与科学. (2版),2007:208-282
|
CSCD被引
1
次
|
|
|
|
|
12.
Simion B. Speeding up spatial database query execution using GPUs.
Procedia Computer Science,2012,9:1870-1979
|
CSCD被引
3
次
|
|
|
|
|
13.
Sutherland I. Reentrant polygon clipping.
Communications of the ACM,1974,17(1):32-42
|
CSCD被引
41
次
|
|
|
|
|
14.
Vatti B R. A generic solution to polygon clipping.
Communications of the ACM,1992,35(7):56-63
|
CSCD被引
54
次
|
|
|
|
|
15.
Walsh S D C. Accelerating geoscience and engineering system simulations on graphics hardware.
Computers & Geosciences,2009,35(12):2353-2364
|
CSCD被引
2
次
|
|
|
|
|
16.
Weiler K. Hidden surface removal using polygon area sorting.
Computer Graphics,1977,11(2):214-222
|
CSCD被引
21
次
|
|
|
|
|
17.
闫长青. 基于GPU的HASM动态模拟与实时渲染方法.
地球信息科学学报,2012,14(2):149-157
|
CSCD被引
4
次
|
|
|
|
|
18.
Zhao S. Accelerating spatial clustering detection of epidemic disease with graphics processing unit.
Proceedings of Geoinformatics 2010,2010:1-6
|
CSCD被引
1
次
|
|
|
|
|
19.
Zhou X. Data partitioning for parallel spatial join processing.
Geoinformatica,1998,2(2):175-204
|
CSCD被引
5
次
|
|
|
|
|
20.
朱欣焰. 分布式空间数据分片与跨边界拓扑连接优化方法.
软件学报,2011,22(2):269-284
|
CSCD被引
7
次
|
|
|
|
|
了解气象卫星更多信息，请访问