基于GPU的高性能并行算法研究

随着计算机技术的发展，人们发现CPU有时候难以满足处理的需要，同时，人们发现了GPU（GPU英文全称Graphic Processing Unit，中文翻译为“图形处理器”）具有强大的处理能力，可以加强对GPU的使用。因此本文的研究目标是基于gpu的高性能并行算法。本文首先对并行计算和GPU进行简单的介绍，然后针对稀疏矩阵向量乘算法和空间最近邻搜索算法展开研究，利用GPU对这两个算法进行研究和实现，通过加速比来反应GPU的优良性能。

【关键词】GPU 高性能 并行算法 稀疏矩阵向量乘 空间最近邻搜索

GPU并行计算属于目前并行计算领域的一个新的分支，我们常见的并行计算有多线程，OpenMP[5]等等，它们都属于超负荷的使用CPU加快运算的速度。GPU并行计算是利用的图形处理器，也可以说是计算机上的显卡，充分的利用GPU的内部结构，加快运算的效率。目前，针对GPU并行计算，人们已经提出了很多的模型，甚至是开发平台，比如CUDA、OpenGL等。当前，产业界和学术界对GPU的并行计算都产生了很大的兴趣，甚至有人说，以后GPU必将取代CPU的存在。但是目前，能够被证明利用GPU达到高速计算的算法并不多，很多算法使用GPU并不如不使用GPU的效果好。因此，对GPU的研究更加迫切，证明那些算法，如何设计可以使用GPU得到最大的加速比是非常重要的。这不仅仅是学术研究的需要，同时对于工业界产业界都将发挥不可取代的作用。一旦GPU被证明可以取代CPU的地位，计算机界必将掀起再一次发展的高潮。本文针对GPU高性能并行算法进行研究，主要是对稀疏矩阵向量乘算法和空间邻搜索算法进行研究，通过一定的实验证明在GPU下的加速比，了解GPU的加速状况。

1 并行计算简介

并行计算是指在单位时间段内，同时执行多条数据计算和多条指令，可以充分的利用多个处理器单元。并行计算的提出是根据现实的需要，现实中，很多领域的数据利用传统的计算方法数据量非常大，计算很耗时，人们就思考，计算机能不能一次处理多个数据进行多次计算，然后就提出了并行计算。

2 GPU简介

GPU的体系架构在不停的更新，不同的体系架构必然要设计不同的模型才能进行并行加速操作。目前来说，GPU有存储器系统和可伸缩流处理器阵列两部分组成。可伸缩流处理器阵列都是有很多的线程处理器群组成，然后线程处理器群又有多个流处理器组成。流处理器都具有指令指针和寄存器，流多处理器有发射、取值、译码、执行单元等。目前多数GPU的体系结构如图1所示。

对于一般的计算机来说，GPU就是图形处理的一个硬件，计算机显示界面的效果，或者三维图片，视频播放效果的好坏都与GPU有关。GPU的主要工作其实是渲染图像和绘制图像。但是图像形态的生成、运动等图形处理操作还是由CPU所完成的。这就导致了CPU的工作量巨大，GPU长期处于空闲状态，没有被合理的利用。随着计算机行业的发展，GPU的体系结构也得到了进一步的改变，GPU开始适合于标准处理模式，大大简化了通用算法进行GPU并行计算的复杂程度。

下面本文将介绍基于GPU的高性能并行算法，通过对三种不同类型的算法的GPU并行计算，来展示GPU针对某些具体计算的并行计算效率。

3 基于GPU的稀疏矩阵向量乘算法研究

稀疏矩阵（矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律）与稠密矩阵（非0元素占所有元素比例较大的矩阵）不同，稠密矩阵可以采用m行n列的数组来存放数据即可，稀疏矩阵来说就不可以采用m行n列的数组来存放数据，因为这样就会浪费很多的存储单元和存储空间，增加计算的时间。对于稀疏矩阵来说，还有没一种统一的最好的存储结构来存储稀疏矩阵，通常都是根据稀疏矩阵不同的特征来确定具体的存储形式。

CSR（Corporate-Social-Responsibility）是一种存储没有规律的稀疏矩阵数据的形式，对于拥有q个元素的稀疏矩阵，采用CSR存储的话，要使用三个数组，一个是数组长度为q的数组Data，按行分为m段，一个是数组长度为q的列下标数组Indices，一个是数组长度为m+1的数组ptr，稀疏矩阵数组中的顺序号由该数组元素指向。CSR与其他稀疏矩阵的存储来比较，CSR具有相当好的空间效率，我们将采用该形式完成SPMV（Sparse Matrix-Vector Multiplication中文名稀疏矩阵向量乘）。

根据线程同步特性，一个线程块对应一行数据是比较适合GPU的内部结构的，但是每个线程块通常都有多个线程，当非零元素的个数不能与线程数匹配时，也会导致一些现成无事可做。结合GPU访问时，全局存储器合并的需要，我们采用Half-warp作为最小的单位，作为输入向量和稀疏矩阵一行相乘的计算。这样就可以减少一定程度上线程空转的比例。

利用CUDA平台尽量测试，经过实验，GPU下进行并行计算的平均加速比为30左右。

4 基于GPU的空间最近邻搜索算法研究

最近相邻问题是对每个点找到距离它最近的数据点，最近相邻问题再目标识别、模式识别、数据聚类、密度估计、函数逼近、文本分类、矢量量化等科学工程中应用非常广泛。通常求解最近相邻问题的方法是暴力搜索法。具体步骤如下：

（1）计算所有点到指定点的距离。

（2）对所有的距离进行排序。

（3）找出离指定点最近的那个点

（4）所有点都使用上面三种步骤找到最近点。

显然上面的最近相邻问题解法复杂度非常的高，超过一定的数据量的话，就会产生很大的计算量，因此我们可以对空间最近邻搜索算法采用GPU并行化的方法。针对传统的最近邻搜索算法使用GPU高性能并行计算，研究此算法在GPU上的运行效率。我们可以将传统的最近邻搜索算法进行一些改进，视同CPU进行空间的划分，划分方法使用KD-Tree算法，然后求出剪枝阈值，ABT剪枝和空间点距离的计算采用GPU上并行计算。这种方法经过大量的实验证明比普通的CPU暴力方法效率要高几十倍，也比GPU上并行采用暴力的方法要高上一倍的效率。证明这种解法，效率是非常不错的。

基于KD-Tree空间划分介绍：

此种方法属于一种高维空间搜索树法，它的每个节点代表n维空间的一维。它的作用是进行空间剪枝，通过此种算法将空间合理的进行划分，避免将大量的数据同时计算距离问题，利用此种算法将空间划分为若干部分，每部分的任务量基本一致。

通过将此算法利用CUDA平台上进行基于GPU的高性能并行计算测试，大量的测试结果证明与串行的效果相比，加速比在20左右。

5 基于GPU的NDVI算法研究

NDVI的计算：NDVI计算是通过一定的数学公式得到的，但是数学公式的参数却是我们利用遥感卫星拍摄的遥感图像，通过计算机分析得到的。归一化植被指数即NDVI是通过NIR（近红外波段反射率）和RED（红光波段反射率）来计算出来的。即NDVI=（NIR-RED）/（NIR+RED）。

5.1 NDVI的并行化实现

利用GPU的并行特性及OpenCL的异构计算特性，可以分别对：直方图的计算、直方图的拉伸、直方图的均衡化、NDVI的计算等四个过程进行并行实现。

5.2 NDVI算法并行和串行运行比较

CPU程序运行的串行算法，选用的是OpenVC库，对遥感图像进行读取，OpenCV库，会对CPU的代码进行优化，因此使用OpenCV库，可以对实验的结果进行客观的比较。OpenCL并行程序的测试时间不包括CPU程序部分的时间，但是包括数据从内存中读出来的时间。

串行与并行运行结果表1所示。

通过表1，我们可以看到直方图的加速比为9.7；直方图拉伸的加速比为7.2；直方图均衡化的加速比为5.9；NDVI计算的加速比为5.8。整体的加速比为8.1。根据我们得到的加速比，我们可以看出我们的实现结果是非常可观的。我们的最低加速比也在5以上，而通过多核来进行并行操作时，在我们测试的4核的机器上，最理想的加速比应该是4。因此我们的实现结果还是非常良好的。

从上面我们对加速比的计算结果，我们也可以得出另外一个结论，不仅仅加速效果比较好，而且当数据量比较大，比如直方图的计算，在CPU串行情况下，需要76ms，在GPU并行的情况下，需要7.83376ms，加速比为9.7，在所有的段中属于最高的加速比。也说明了，在数据量越大的情况下加速的效果越明显。但是此结论仅仅是在本实验结果中，数据量太大的情况下，也可能会出现相反的结果。

6 总结

本文研究的目标是基于GPU的高性能并行算法研究，首先本文对并行计算和GPU进行了简单的说明，通过对稀疏矩阵向量乘算法、空间最近邻搜索算法和基于GPU的NDVI算法的研究，说明了GPU高性能并行计算在某些算法上应用起来效率是非常可观的，比普通的CPU计算要高几十倍的效率。本文提到的稀疏矩阵向量乘算法的加速比为30左右，空间最近邻搜索算法的加速比为20左右，NDVI算法的加速比为8左右。

参考文献

[1]张舒，褚艳利.GPU 高性能计算之CUDA[M].中国水利水电出版社，2011.

[2]吴恩华.柳有权.基于图形处理器（GPU）的通用计算[J].计算机辅助设计与图形学学报，2010，16（5）：601-612.

[3]白洪涛，欧阳丹彤，何丽莉，姜珊珊.一种基于图形处理器的压缩单纯形方法[J].电子学报，2012.

[4]朱鉴，吴恩华，基于 GPU 的球面深度图实时绘制[J].计算机学报，2011，32（2）： 231-240.

[5]陈永健.OpenMP 编译与优化技术研究[D].北京：清华大学，2011.

[6]N. Fujimoto. Faster matrix-vector multiplication on GeForce 8800 GTX[C].Proceedings ofthe 22nd IEEE International Parallel and Distributed Processing Symposium， Program andCD-ROM，2011，1-8.

作者单位

广东交通职业技术学院 广东省广州市 510650