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

来源：计算机应用杂志2015年第6期北京时间：

作者：王磊, 王鹏飞, 赵学胜, 卢立托

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

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

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

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