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

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

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

中图分类号： TP391.41； P208 文献标志码：A

英文摘要

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 引言

随着数字地球的发展，球面Voronoi图（以下简称V图）在全球空间索引[1-2]、球面动态模拟[3]等方面得到了广泛的应用。基于四元三角格网（Quaternary Triangular Mesh，QTM）[4]单元之间距离计算与比较的球面V图生成算法[5]相对于扩张算法具有较高的精度，但由于需要计算并比较每个格网到所有种子点之间的距离，致使算法效率较低，无法满足实时应用的需求。

近年来，图形处理器（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 共享内存优化

GPU全局内存位于显存，具有较大的存储空间，可被Kernel调用的所有线程访问，但全局内存的访问具有较高的访存延迟（一次访问需要400～600个时钟周期）。而共享内存是GPU片内的高速存储器，它的缓冲区驻留在物理GPU上，而不是GPU之外的系统内存中。因此，共享内存的访存延迟要远远低于全局内存（只有全局内存的1%左右）[11-12]。共享内存可供一个线程块内所有的线程访问，是实现线程间通信的延迟最小的方法[11]。然而，共享内存存储空间较小，可供每个线程块使用的共享内存大小仅为16KB（计算能力1.1的设备）。

Kernel_1所述算法中，格网中心点的坐标数据及种子点坐标数据，都存储在全局内存中，在计算每个QTM格网到所有种子点的距离时，需要频繁地从全局内存获取种子点数据。设种子点数为N，球面上QTM格网总数为G，则生成球面V图所需要的计算和比较的总次数为2NG，所需要的全局内存访问的次数为（G+NG），二者之比为2NG∶（G+NG）≈2∶1。也就是说，每进行两次计算（或比较）就需要进行一次全局内存的访问，这将严重影响算法的效率。

共享内存相对于全局内存具有更高的访存速度，因此可先将种子点数据从全局内存中取出，存储到共享内存中，供一个线程块内所有的线程（每个线程处理一个格网）使用，每次计算只需要从共享内存中读取数据即可。但由于可供每个线程块使用的共享内存仅为16KB，当种子点数量较多时，无法一次性放入共享内存。这就需要分成多次，每次将部分种子点数据放入共享内存，当该部分数据使用完成后，再取出一部分种子点数据进行计算，依次进行，直至所有的种子点都计算完毕。算法实现的伪码如下（Kernel_2）。

若每个线程块中的线程数量为B，则每个线程块内所要进行的计算和比较的总次数为2NB，需要进行的全局内存访问次数为（B+N）（包括从全局内存中取出B个QTM格网数据和N个种子点数据），则计算（或比较）的次数与全局内存访存次数之比为2NB∶（B+N）=2N∶（1+N/B）。若取N=1024、B=256，则计算与访存次数之比为2048∶5≈400∶1。这相对于原算法大幅度减小了全局内存访问的次数，在很大程度上提高了算法的效率。

2.2 常量内存优化

GPU中的常量内存是只读内存。如果半个线程束（HalfWarp， 16个线程）中的每个线程都从常量内存的相同地址读取数据，GPU只会产生一次读取请求并在随后将数据广播到每个线程；同时，由于常量内存的内容是不会发生变化的，硬件会主动把这个常量数据缓存在GPU上，在第一次从常量内存的某个地址上读取后，当其他半线程束请求同一个地址时，将命中缓存，同样减少了额外的内存流量。因此，与从全局内存中读取数据相比，从常量内存中读取相同的数据可以节约大量的内存带宽[11]。

由于算法中的种子点数据不会发生改变，且每个线程都从第1个种子点数据开始读取，因此，可将种子点数据直接从CPU内存复制到GPU常量内存中，以消除全局内存访问对算法效率的影响。与使用共享内存类似，在计算能力为1.1的设备中，GPU常量内存的大小只有64KB，当种子点数据较大时，需要分成多次将数据从CPU内存复制到GPU常量内存，并多次调用核函数进行计算。算法实现的伪码与Kernel_1类似，只是将种子点数据存储在GPU常量内存中。

2.3 寄存器优化

在2.2节所述的算法中，每个GPU线程处理一个QTM格网，即在处理每个QTM格网时，都要从常量内存中获取所有的种子点数据。尽管GPU常量内存的访问速度较快，但频繁的访问也将带来效率上的影响，为减少对常量内存的访问次数，本节采取如下策略：在每个线程中，将多个QTM格网数据从全局内存中取出，存储在寄存器中，同时从常量内存中获取一次种子点数据，供这些QTM格网使用。算法实现的伪码如下（Kernel_3为什么没有kernel-3？文中2.2节所述的“常量内存优化”伪码（默认为Kernel-3）与文中的Kernel-1类似，不同之处仅在于Kernel-1中种子点数据存储在全局内存，而Kernel-3存储在常量内存，因此文中并未给出。所以Kernel-2之后就直接为Kernel-4了！

为按顺序进行编号，也可以将文中的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图生成算法及上述各优化算法进行实现，并进行了对比分析。

基于第9层QTM格网（格网总数2097152），分别用不同数量的种子点对以上算法进行测试，原算法（CPU串行）生成球面V图所用的时间如表1所示，各优化算法在不同数据规模下所获得的加速比如图1所示。图2为利用不同数量的种子点数生成的球面V图。

由图1可以看出，使用GPU全局内存对算法进行实现时，频繁的全局内存访问致使算法执行的时间与CPU串行算法相当，仅可获得较小的加速比；而通过使用共享内存、常量内存、寄存器对算法进行加速后，在不同的数据规模（种子点数）下都能够获得几十甚至上百倍的加速比，使算法执行的时间大大降低。从图1中还可以看出，当种子点数较少时，所获得的加速比较低，随着种子点数的增多，加速比也随之增大。这是由于GPU更适合于密集型的计算，当数据量（计算量）较小时，算法在GPU上的执行时无法隐藏访存和数据传输的延迟[12]，而随着数据量的增大，这些延迟逐渐被隐藏，因此加速比会逐渐增大；而当数据量大到能使GPU满负荷工作时，所有的访存和数据传输的延迟都已被很好地隐藏，加速比也将趋于稳定，如图1所示。

4 结语

本文利用CUDA对基于距离计算与比较的球面V图生成算法进行实现，并从GPU共享内存、常量内存、寄存器等三种内存的访问方面对算法进行优化，通过实验得出如下结论：

1）仅使用GPU全局内存时，算法的效率仅与CPU串行算法相当；

2）GPU共享内存、常量内存、寄存器的合理使用，能够大大提高算法的效率；

3）在一定的数据规模下，随着种子点数的增多，GPU加速比逐渐增大。

本文仅从GPU内存访问的角度对基于距离计算与比较的球面V图生成算法进行了优化，下一步的工作是综合考虑算法指令、任务划分、内存访问等因素，对算法进一步优化。

参考文献：

[1]LUKATELA H. Ellipsoidal area computations of large terrestrial objects [C/OL]// Proceedings of the First International Conference on Discrete Grids. [2014-12-01]. .

[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 GPUbased algorithm for the generation of spherical Voronoi diagram in QTM mode [J]. International Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2013， XL4/W2：45-50.

[6]NVIDIA. CUDA C programming guide Version 6.5 [EB/OL]. [2014-12-01]. .

[11]SANDERS J， KANDROT E. CUDA by example： an introduction to generalpurpose 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.）