摘要：基于四元三角格网（QTM）之间距离计算与比较的球面Voronoi图生成算法相对于扩张算法具有较高的精度，但由于需要计算并比较每个格网到所有种子点的距离，致使算法效率较低。针对这一问题，利用图形处理器（GPU）并行计算对算法进行实现，然后从GPU共享内存、常量内存、寄存器等三种内存的访问方面进行优化，最后用C++语言和统一计算设备架构（CUDA）开发了实验系统，对优化前后算法的效率进行对比。实验结果表明，不同内存的合理使用能在很大程度上提高算法的效率，且数据规模越大，所获得的加速比越高。
关键词：球面Voronoi图；统一计算设备架构；共享内存；常量内存；寄存器
英文摘要
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 speedup 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
0 引言
近年来，图形处理器（Graphic Processing Unit，GPU）技术快速发展，其浮点运算能力和内存带宽已远远超过中央处理器（Central Processing Unit，CPU）[6]。NVIDIA公司开发的统一计算设备架构（Compute Unified Device Architecture，CUDA）为GPU增加了一个易用的编程接口[7]，使得GPU并行计算在群体行为仿真[8]、三维数据并行可视化[9]、地球表面测绘[10]等领域得到广泛应用。
本文利用CUDA对基于距离计算与比较的球面V图生成算法进行实现，然后从GPU共享内存、常量内存、寄存器等三种内存的访问方面，对算法进行优化，最后利用C++和CUDA开发了实验系统，对优化前后算法的效率进行对比。
1 基于QTM的球面Voronoi图并行生成算法
若将式（1）中的ω定义为一个QTM格网，Ω定义为球面上所有QTM格网的集合，距离函数d定义为球面大弧距离，则式（1）表示的即为基于QTM的球面V图。
基于QTM格网之间距离计算与比较的球面V图生成算法[5]，通过计算并比较每个格网到所有种子点的距离，来确定格网单元所属的Voronoi区域，算法具有计算密集性、指令一致性及相互独立性的特点，本文采用GPU单指令多数据流（Single Instruction Multiple Date，SIMD）并行计算模型来执行这些运算，算法实现的核函数（Kernel）伪码如下（Kernel_1）。
2 算法的优化
在CUDA架构中有多种内存可供使用，如全局内存、局部内存、共享内存、常量内存、寄存器等，每种内存的空间大小、作用范围及访问速度都各不相同。因此，在实现算法时使用不同的内存、不同的访问方式，将会对程序的性能产生巨大的影响。本文将从GPU内存访问方面（包括共享内存、常量内存及寄存器等）对上述算法进行优化。
2.1 共享内存优化
2.2 常量内存优化
GPU中的常量内存是只读内存。如果半个线程束（HalfWarp， 16个线程）中的每个线程都从常量内存的相同地址读取数据，GPU只会产生一次读取请求并在随后将数据广播到每个线程；同时，由于常量内存的内容是不会发生变化的，硬件会主动把这个常量数据缓存在GPU上，在第一次从常量内存的某个地址上读取后，当其他半线程束请求同一个地址时，将命中缓存，同样减少了额外的内存流量。因此，与从全局内存中读取数据相比，从常量内存中读取相同的数据可以节约大量的内存带宽[11]。
由于算法中的种子点数据不会发生改变，且每个线程都从第1个种子点数据开始读取，因此，可将种子点数据直接从CPU内存复制到GPU常量内存中，以消除全局内存访问对算法效率的影响。与使用共享内存类似，在计算能力为1.1的设备中，GPU常量内存的大小只有64KB，当种子点数据较大时，需要分成多次将数据从CPU内存复制到GPU常量内存，并多次调用核函数进行计算。算法实现的伪码与Kernel_1类似，只是将种子点数据存储在GPU常量内存中。
2.3 寄存器优化
为按顺序进行编号，也可以将文中的Kernel-4直接改成Kernel-3！）。
3 实验与分析
实现本文算法所用的编程语言为C++和NVIDIA CUDA 6.5；硬件环境为Intel Core 2 Quad CPU Q8400 @2.66GHz，2.00GB内存，NVIDIA GeForce 9600 GT GPU，计算能力1.1。在该环境下，将基于距离计算与比较的球面V图生成算法及上述各优化算法进行实现，并进行了对比分析。
4 结语
本文利用CUDA对基于距离计算与比较的球面V图生成算法进行实现，并从GPU共享内存、常量内存、寄存器等三种内存的访问方面对算法进行优化，通过实验得出如下结论：
1）仅使用GPU全局内存时，算法的效率仅与CPU串行算法相当；
2）GPU共享内存、常量内存、寄存器的合理使用，能够大大提高算法的效率；
3）在一定的数据规模下，随着种子点数的增多，GPU加速比逐渐增大。
本文仅从GPU内存访问的角度对基于距离计算与比较的球面V图生成算法进行了优化，下一步的工作是综合考虑算法指令、任务划分、内存访问等因素，对算法进一步优化。 参考文献：
[8]HE Y， YE C， LIU Z， et al. Parallel simulation and optimization of CUDAbased realtime huge crowd behavior[J]. Journal of Comput
