Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit
WANG Lei1, WANG Pengfei1, ZHAO Xuesheng1, LU Lituo2
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
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.
王磊, 王鹏飞, 赵学胜, 卢立托. 基于图形处理器的球面Voronoi图生成算法优化[J]. 计算机应用, 2015, 35(6): 1564-1566.
WANG Lei, WANG Pengfei, ZHAO Xuesheng, LU Lituo. Optimization of spherical Voronoi diagram generating algorithm based on graphic processing unit. Journal of Computer Applications, 2015, 35(6): 1564-1566.
[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.)
2015, Vol. 35 
