期刊文献+

GPU加速的多边形叠加分析 被引量:12

Accelerating polygon overlay analysis by GPU
原文传递
导出
摘要 叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将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.
出处 《地理科学进展》 CSCD 北大核心 2013年第1期114-120,共7页 Progress in Geography
基金 国家自然科学基金项目(40830529) 国家"863"计划项目(2011AA120305)
关键词 叠加分析 图形处理单元 多边形剪裁 并行计算 空间分析 overlay analysis GPGPU polygon clipping parallel computing spatial analysis
  • 相关文献

参考文献19

  • 1BrinkhofFT, Kriegel H P, Seeger B. 1993: Efficient processingof spatial joins using R-trees//Proceedings of ACM SIG-MOD International Conference on Management of Data.Washinton D.C.: ACM Press: 237-246.
  • 2Garcia V,Debreuve E,Barlaud M. 2008. Fast k-nearest neigh-bor search using GPU//Proceedings of the Workshop onComputer Vision on GPU. Alaska, USA: 1-6.
  • 3Greiner G, Hormann K. 1998. Efficient clipping of arbitrarypolygons. Journal of ACM Transactions of Graphics, 17(2): 71-83.
  • 4Harish P, Narayanan P. 2007. Accelerating large graph algo-rithms on the GPU using CUDA//Proceedings High Per-formance Computing, 4873: 197-208.
  • 5Harris M, Sengupta S, Owens J D. 2007. Parallel prefix sum(scan) with CUDA//Nguyen H. 2007. GPU Gems 3.New Jersey: Addison-Wesley Press: 851-876.
  • 6Hillis W D,Steele G L. 1986. Data parallel algorithms. Com-munications of the ACM, 92(2): 1170-1183.
  • 7Horn D. 1992. Stream reduction operations for GPGPU Appli-cations//Pharr M,Fernando R. 2005. GPU Gems 2. NewJersey: Addison-Wesley Press: 573-589.
  • 8李丹,黎夏,刘小平,陈逸敏,李少英,刘凯,乔纪纲,郑奕钟,张亦汉,劳春华.GPU-CA模型及大尺度土地利用变化模拟[J].科学通报,2012,57(11):959-969. 被引量:19
  • 9刘勇奎,高云,黄有群.一个有效的多边形裁剪算法[J].软件学报,2003,14(4):845-856. 被引量:74
  • 10Longley PA, Goodchild M F, Maguire D J, et al. 2007.地理信息系统与科学.2版.张晶,刘瑜,张洁,等,译.北京:机械工业出版社:208-282.

二级参考文献39

共引文献106

同被引文献194

引证文献12

二级引证文献52

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部