Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit

doi:10.11772/j.issn.1001-9081.2015.06.1564

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (6): 1564-1566.DOI: 10.11772/j.issn.1001-9081.2015.06.1564

Previous Articles Next Articles

Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit

WANG Lei¹, WANG Pengfei¹, ZHAO Xuesheng¹, LU Lituo²

1. College of Geoscience and Surveying Engineering, China University of Mining and Technology (Beijing), Beijing 100083, China;
2. Beijing Company, China Petroleum Engineering Company Limited, Beijing 100085, China

Received:2015-01-07 Revised:2015-04-02 Published:2015-06-12

基于图形处理器的球面Voronoi图生成算法优化

王磊¹, 王鹏飞¹, 赵学胜¹, 卢立托²

1. 中国矿业大学(北京) 地球科学与测绘工程学院, 北京 100083;
2. 中国石油集团工程设计有限责任公司北京分公司, 北京 100085

通讯作者: 王磊(1989-),男,安徽宿州人,博士研究生,主要研究方向:球面Voronoi图、GPU并行计算;wl890627@163.com
作者简介:王鹏飞(1991-),男,山东德州人,硕士研究生,主要研究方向:三维建模、海量三维模型可视化;赵学胜(1967-),男,山东菏泽人,教授,博士,主要研究方向:三维GIS、数字地球空间建模;卢立托(1986-),男,河北石家庄人,助理工程师,硕士,主要研究方向:并行计算、全球定位系统。
基金资助:
国家自然科学基金资助项目(41171306);高等学校博士学科点专项科研基金资助项目(20130023110001)。

Abstract

Abstract:

Spherical Voronoi diagram generating algorithm based on distance computation and comparison of Quaternary Triangular Mesh (QTM) has a higher precision relative to dilation algorithm. However, massive distance computation and comparison lead to low efficiency. To improve efficiency, Graphic Processing Unit (GPU) parallel computation was used to implement the algorithm. Then, the algorithm was optimized with respect to the access to GPU shared memory, constant memory and register. At last, an experimental system was developed by using C++ and Compute Unified Device Architecture (CUDA) to compare the efficiency before and after the optimization. The experimental results show that efficiency can be improved to a great extent by using different GPU memories reasonably. In addition, a higher speed-up ratio can be acquired when the data scale is larger.

Key words: spherical Voronoi diagram, Compute Unified Device Architecture (CUDA), shared memory, constant memory, register

摘要：

基于四元三角格网(QTM)之间距离计算与比较的球面Voronoi图生成算法相对于扩张算法具有较高的精度,但由于需要计算并比较每个格网到所有种子点的距离,致使算法效率较低。针对这一问题,利用图形处理器(GPU)并行计算对算法进行实现,然后从GPU共享内存、常量内存、寄存器等三种内存的访问方面进行优化,最后用C++语言和统一计算设备架构(CUDA)开发了实验系统,对优化前后算法的效率进行对比。实验结果表明,不同内存的合理使用能在很大程度上提高算法的效率,且数据规模越大,所获得的加速比越高。

关键词: 球面Voronoi图, 统一计算设备架构, 共享内存, 常量内存, 寄存器

CLC Number:

WANG Lei, WANG Pengfei, ZHAO Xuesheng, LU Lituo. Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit[J]. Journal of Computer Applications, 2015, 35(6): 1564-1566.

王磊, 王鹏飞, 赵学胜, 卢立托. 基于图形处理器的球面Voronoi图生成算法优化[J]. 计算机应用, 2015, 35(6): 1564-1566.

References

[1] LUKATELA H. Ellipsoidal area computations of large terrestrial objects [C/OL]//Proceedings of the First International Conference on Discrete Grids. [2014-12-01]. http://ncgia.ucsb.edu/globalgrids-book/eac/.
[2] LUKATELA H. Hipparchus geopositioning model: an overview [C/OL]//Proceedings of the Eighth International Symposium on Computer-Assisted Cartography, 1987. [2014-12-01]. http://www.geodyssey.com/papers/hlauto8.html.
[3] MOSTAFAVI M A, GOLD C. A global kinetic spatial data structure for a marine simulation [J]. International Journal of Geographical Information Science, 2004, 18(3):211-227.
[4] DUTTON G. Modeling locational uncertainty via hierarchical tessellation [M]. Accuracy of Spatial Databases. London: Taylor & Francis, 1989:125-140.
[5] WANG L, ZHAO X, CAO W, et al. A GPU-based algorithm for the generation of spherical Voronoi diagram in QTM mode [J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2013, XL-4/W2:45-50.
[6] NVIDIA. CUDA C programming guide Version 6.5 [EB/OL]. [2014-12-01]. http://docs.nvidia.com/cuda/pdf/CUDA_C_ Programming_Guide.pdf.
[7] COOK S. CUDA programming: a developer's guide to parallel computing with GPUs [M]. SU T, LI D, LI S, et al. translated. Beijing: China Machine Press, 2014: 12-13. (COOK S.GPU并行程序设计——GPU编程指南[M].苏统华, 李东, 李松泽, 等译.北京:机械工业出版社, 2014:12-13.)
[8] HE Y, YE C, LIU Z, et al. Parallel simulation and optimization of CUDA-based real-time huge crowd behavior[J]. Journal of Computer Applications, 2012, 32(9): 2466-2469. (贺毅辉, 叶晨, 刘志忠, 等. 基于CUDA的大规模群体行为实时仿真并行实现及优化[J].计算机应用, 2012, 32(9):2466-2469.)
[9] XU S, ZHANG E. CUDA-based parallel visualization of 3D data[J]. CT Theory and Applications, 2011, 20(1): 47-54. (徐赛花, 张二华. 基于CUDA的三维数据并行可视化[J].CT理论与应用研究, 2011, 20(1):47-54.)
[10] DESCHIZEAUX B, BLANC J-Y. Imaging earth's subsurface using CUDA [C/OL]//GPU Gems. 2007. [2014-12-01]. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch38.html.
[11] SANDERS J, KANDROT E. CUDA by example: an introduction to general-purpose GPU programming [M]. NIE X, et al. translated. Beijing: China Machine Press, 2011: 54-55, 78.(SANDERS J, KANDROT E.GPU高性能编程——CUDA实战[M]. 聂雪军, 等译. 北京:机械工业出版社, 2011:54-55, 78.)
[12] ZHAN S, ZHU Y, ZHAO K, et al. GPU high performance computation -CUDA [M]. Beijing: China Water & Power Press, 2009: 46-47, 141-142. (张舒, 褚艳利, 赵开勇, 等.GPU高性能运算之CUDA[M].北京:中国水利水电出版社, 2009:46-47, 141-142.)

[1]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[2]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[3]	PAN Guoteng, OU Guodong, CHAO Zhanghu, LI Mengjun. Design and implementation of Lite register model [J]. Journal of Computer Applications, 2020, 40(5): 1369-1373.
[4]	ZHAO Yongtao, CHEN Qingkui, FANG Yuling, ZHAO Deyu, JI Lina. Early warning method for driving safety based on CUDA [J]. Journal of Computer Applications, 2017, 37(1): 134-137.
[5]	JI Lina, CHEN Qingkui, CHEN Yuanjing, ZHAO Deyu, FANG Yuling, ZHAO Yongtao. Real-time crowd counting method from video stream based on GPU [J]. Journal of Computer Applications, 2017, 37(1): 145-152.
[6]	GUAN Yaqin, ZHAO Xuesheng, WANG Pengfei, LI Dapeng. Parallel algorithm for massive point cloud simplification based on slicing principle [J]. Journal of Computer Applications, 2016, 36(7): 1793-1796.
[7]	ZHANG Shuo, HE Fazhi, ZHOU Yi, YAN Xiaohu. GPU parallel particle swarm optimization algorithm based on adaptive warp [J]. Journal of Computer Applications, 2016, 36(12): 3274-3279.
[8]	WANG Yuzhuo, LIU Xiuguo, ZHANG Wei. Parallel algorithm of raster river network extraction based on CUDA [J]. Journal of Computer Applications, 2015, 35(4): 960-963.
[9]	LI Jinjing, CHEN Qingkui, LIU Baoping, LIU Bocheng. Binary probability segmentation of video based on graphics processing unit [J]. Journal of Computer Applications, 2015, 35(11): 3187-3193.
[10]	CHEN Zhi, LI Tianrui, LI Ming, YANG Yan. Fault diagnosis method of high-speed rail based on compute unified device architecture [J]. Journal of Computer Applications, 2015, 35(10): 2819-2823.
[11]	YAN Guochang HE Yanxiang LI Qingan. Static register reallocation approach for soft error reduction of register files [J]. Journal of Computer Applications, 2014, 34(9): 2730-2733.
[12]	JIANG Liehui CHEN Huichao DONG Weiyu ZHANG Yanwen. Co-design optimization approach based on static register allocation in system emulation [J]. Journal of Computer Applications, 2014, 34(5): 1404-1407.
[13]	SUN Xiaolin ZHANG Jianyang JIA Xiao. Optimization of intra-MAP handover in HMIPv6 [J]. Journal of Computer Applications, 2014, 34(2): 338-340.
[14]	DU Xin LIU Dagang ZHANG Kaihuo SHEN Yuan ZHAO Kang NI Youcong. Auto-clustering algorithm based on compute unified device architecture and gene expression programming [J]. Journal of Computer Applications, 2013, 33(07): 1890-1893.
[15]	CHEN Xiuliang LIANG Yingjie GUO Fuliang. Fireworks simulation based on CUDA particle system [J]. Journal of Computer Applications, 2013, 33(07): 2059-2062.

Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit

基于图形处理器的球面Voronoi图生成算法优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics