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 Lei1, WANG Pengfei1, ZHAO Xuesheng1, LU Lituo2   

  1. 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, 王鹏飞1, 赵学胜1, 卢立托2   

  1. 1. 中国矿业大学(北京) 地球科学与测绘工程学院, 北京 100083;
    2. 中国石油集团工程设计有限责任公司 北京分公司, 北京 100085
  • 通讯作者: 王磊(1989-),男,安徽宿州人,博士研究生,主要研究方向:球面Voronoi图、GPU并行计算;wl890627@163.com
  • 作者简介:王鹏飞(1991-),男,山东德州人,硕士研究生,主要研究方向:三维建模、海量三维模型可视化;赵学胜(1967-),男,山东菏泽人,教授,博士,主要研究方向:三维GIS、数字地球空间建模;卢立托(1986-),男,河北石家庄人,助理工程师,硕士,主要研究方向:并行计算、全球定位系统。
  • 基金资助:

    国家自然科学基金资助项目(41171306);高等学校博士学科点专项科研基金资助项目(20130023110001)。

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: