全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

GPU加速的多边形叠加分析

DOI: 10.11820/dlkxjz.2013.01.012, PP. 114-120

Keywords: 并行计算,叠加分析,多边形剪裁,空间分析,图形处理单元

Full-Text   Cite this paper   Add to My Lib

Abstract:

叠加分析是地理信息系统最重要的分析功能之一,对多边形图层进行叠加分析要花费大量时间。为此,将GPU用于多边形叠加分析过程中的MBR过滤及多边形剪裁两个阶段。对MBR过滤阶段,提出了基于GPU的通过直方图及并行前置和实现的MBR过滤算法。对多边形剪裁阶段,通过改进Weiler-Atherton算法,使用新的焦点插入方法和简化的出入点标记算法,并结合并行前置和算法,提出了基于GPU的多边形剪裁算法。对实现过程中可能出现的负载不均衡情况,给出了基于动态规划的负载均衡方法。通过对这些算法的应用,实现对过滤阶段及精炼阶段的加速。实验结果表明,基于GPU的MBR过滤方法相对CPU实现的加速比为3.8,而基于GPU的多边形剪裁的速度比CPU实现快3.4倍。整体上,与CPU实现相比,GPU加速的多边形叠加提供了3倍以上的加速比。

References

[1]  Vatti B R. 1992. A generic solution to polygon clipping. Communications of the ACM, 35(7): 56-63.
[2]  Walsh S D C, Saar M O, Bailey P et al. 2009. Accelerating geoscience and engineering system simulations on graphics hardware. Computers & Geosciences, 35(12): 2353-2364.
[3]  Weiler K, Atherton P. 1977. Hidden surface removal using polygon area sorting. Computer Graphics, 11(2): 214-222.
[4]  Yan C Q, Yue T X. 2012. A novel method for Dynamic modeling and real-time rendering based on GPU. Geo-information Science, 14(2): 149-157. [闫长青, 岳天祥. 2012. 基于GPU的HASM动态模拟与实时渲染方法. 地球信息科学学报, 14(2): 149-157.]
[5]  Zhao S, Zhou C. 2010. Accelerating spatial clustering detection of epidemic disease with graphics processing unit// Proceedings of Geoinformatics 2010. Beijing, China: 1-6.
[6]  Zhou X, Abel D J, Truffet D. 1998. Data partitioning for parallel spatial join processing. Geoinformatica, 2(2): 175-204.
[7]  Zhu X Y, Zhou C H, Wo W, et al. 2011. Distributed spatial data fragmentation and cross-border topological join optimization. Journal of Software, 22(2): 269-284. [朱欣焰, 周春晖, 呙维, 等. 2011. 分布式空间数据分片与跨边界拓扑连接优化方法. 软件学报, 22(2): 269-284.]
[8]  李秀彬. 全球环境变化研究的核心领域: 土地利用/土地覆被变化的国际研究动向. 地理学报, 1996, 51(6):553-558.
[9]  葛全胜, 何凡能, 郑景云, 等. 21 世纪中国历史地理学发展的思考. 地理研究, 2004, 23(3): 374-384.
[10]  Brinkhoff T, Kriegel H P, Seeger B. 1993: Efficient processing of spatial joins using R-trees//Proceedings of ACM SIGMOD International Conference on Management of Data.
[11]  Washinton D.C.: ACM Press: 237-246.
[12]  Chen S, Lu X, Zhou C. 1999. Introduction to Geographic Information Systems. Beijing, China: Science Press: 125-126. [陈述彭, 鲁学军, 周成虎. 1999. 地理信息系统导论. 北京: 科学出版社: 125-126.]
[13]  Garcia V, Debreuve E, Barlaud M. 2008. Fast k-nearest neighbor search using GPU//Proceedings of the Workshop on Computer Vision on GPU. Alaska, USA: 1-6.
[14]  Greiner G, Hormann K. 1998. Efficient clipping of arbitrary polygons. Journal of ACM Transactions of Graphics, 17 (2): 71-83.
[15]  Harish P, Narayanan P. 2007. Accelerating large graph algorithms on the GPU using CUDA//Proceedings High Performance Computing, 4873: 197-208.
[16]  Harris M, Sengupta S, Owens J D. 2007. Parallel prefix sum (scan) with CUDA//Nguyen H. 2007. GPU Gems 3.
[17]  New Jersey: Addison-Wesley Press: 851-876.
[18]  Hillis W D, Steele G L. 1986. Data parallel algorithms. Communications of the ACM, 92(2): 1170-1183.
[19]  Horn D. 1992. Stream reduction operations for GPGPU Applications//Pharr M, Fernando R. 2005. GPU Gems 2. New Jersey: Addison-Wesley Press: 573-589.
[20]  Li D, Li X, Liu X P, et al. 2011. GPU-CA model and large-scale land-use change simulation. Chinese Science Bulletin, 57(11): 959-969. [李丹, 黎夏, 刘小平, 等 2011.
[21]  GPU-CA模型及大尺度土地利用变化模拟. 科学通报, 57(11): 959-969.]
[22]  Liu Y Q, Gao Y, Huang Y Q. 2003. An efficient algorithm for polygon clipping. Journal of Software, 14(4): 845-856. [刘勇奎, 高云, 黄有群. 2003. 一个有效的多边形裁剪算法. 软件学报, 14(4): 845-856.]
[23]  Longley P A, Goodchild M F, Maguire D J, et al. 2007. Geographic information systems and science. 2nd ed. Beijing, China: China Machine Press: 208-282. [Longley P A, Goodchild M F, Maguire D J, et al. 2007. 地理信息系统与科学. 2版. 张晶, 刘瑜, 张洁, 等, 译. 北京: 机械工业出版社: 208-282.]
[24]  Simion B, Ray S, Brown A D 2012. Speeding up spatial database query execution using GPUs. Procedia Computer Science, 9: 1870-1979.
[25]  Sutherland I, Hodgman G W. 1974. Reentrant polygon clipping. Communications of the ACM, 17(1): 32-42.
[26]  白淑英, 张树文, 张养贞. 土地利用/土地覆被时空分布100 年数字重建: 以大庆市杜尔伯特蒙古族自治县为例. 地理学报, 2007, 62(4): 427-436.
[27]  Zhao S, Zhou C. 2010. Accelerating spatial clustering detection of epidemic disease with graphics processing unit// Proceedings of Geoinformatics 2010. Beijing, China: 1-6.
[28]  Klein Goldewijk K, Beusen A, Van Drecht G, et al. TheHYDE 3.1 spatially explicit database of human-induced global land-use change over the past 12,000 years. GlobalEcology and Biogeography, 2011, 20(1): 73-86.
[29]  Van Minnen J G, Klein Goldewijk K, Stehfest E, et al.The importance of three centuries of land-use change forthe global and regional terrestrial carbon cycle. ClimaticChange, 2009, 97(1): 123-144.
[30]  Houghton R A, Hackler J L. Sources and sinks of carbonfrom land-use change in China. Global BiogeochemicalCycles, 2003, 17(2): 1034, doi: 10.1029/2002GB001970.
[31]  葛全胜, 戴君虎, 何凡能, 等. 过去300 年中国土地利用、土地覆被变化与碳循环研究. 中国科学: D辑, 2008, 38(2): 197- 210.
[32]  李巧萍, 丁一汇, 董文杰. 中国近代土地利用变化对区域气候影响的数值模拟. 气象学报, 2006, 64(3):257-270.
[33]  林珊珊, 郑景云, 何凡能. 中国传统农区历史耕地数据网格化方法. 地理学报, 2008, 63(1): 83-92.
[34]  Zhou X, Abel D J, Truffet D. 1998. Data partitioning for parallel spatial join processing. Geoinformatica, 2(2): 175-204.
[35]  Zhu X Y, Zhou C H, Wo W, et al. 2011. Distributed spatial data fragmentation and cross-border topological join optimization. Journal of Software, 22(2): 269-284. [朱欣焰, 周春晖, 呙维, 等. 2011. 分布式空间数据分片与跨边界拓扑连接优化方法. 软件学报, 22(2): 269-284.]

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133