技术开发 频道

利用CUDA加速k近邻算法

  【IT168 技术】

  注:本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见:http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案,将会逐步与大家分享,不可错过哦!

  CUDA ZONE专区:http://cuda.it168.com/

  CUDA技术论坛:http://cuda.itpub.net

  在接触CUDA之前,已经听说过可以利用GPU来加速一些通用计算,也有不少人研究GPU上的通用计算(GPGPU)。但是在CUDA出现之前,在GPU上面进行通用计算时颇为迂回的一个过程:需要先将数据上传成纹理,然后编写着色器程序来处理这些纹理对象,进行所需要的计算,完成之后再将数据从显存上下载。对于不熟悉计算机图形学相关知识或者是缺少图形编程经验的人来说,这种迂回而且略显繁琐的方法并不具有太大的吸引力。因此, GPU进行并行计算在07年以前并没有大范围地推广开来。

  CUDA的推出在GPU并行计算领域毫无疑问是一个划时代的事件,它使得大多数人能够以相对熟悉的方式来直接编写GPU上的并行程序。并不需要学习很多额外的知识,却能够很容易地获得一到两个数量级的加速,这样的特性使得CUDA迅速地为人们所接受,各种基于CUDA的应用也就如云后春笋般迅速出现。

  本人也是在这种背景下开始学习CUDA并尝试GPU并行编程的。由于Nvidia提供了一整套完整的编程接口,而且也有比较详细的文档资料,CUDA的学习曲线还是比较低的。在具有良好C程序编程的基础上,CUDA的入门大概几个小时就可以完成。当然,学会使用CUDA并不意味着就能写出好的GPU并行程序,因为本质上而言CUDA只是一套控制GPU上多个处理器的库而已,而GPU并行程序设计的核心,在于针对特定的应用寻找一个良好的并行化方案,而这本身需要程序员自身对要解决的问题的本质有着深入的了解。

  然而在刚开始编写CUDA程序时,本人并没有意识到这一点的重要性,而是简单的将CPU上的串行算法改写成多核版本,直接映射到GPU之上。这样做的效果可想而知——对于大规模的计算,加速比非常低,往往连10倍的加速都达不到;而对于小规模的计算,甚至还不如经过优化的CPU程序,因为数据在主存和显存之间的传输已经花费了大量的时间。

  在此以本人在初学CUDA时参与一个项目的经历为例。当时我们面对的问题是一个高维空间中k近邻(kNN)搜索,它是我们设计的图像超分辨率算法中的核心部分之一。暴力的kNN算法通过直接计算数据集中计算所有个体相互之间的距离,并且对这些距离排序来找出每个个体的k近邻。该算法其实不复杂,仅仅需要计算个体之间的距离矩阵,并且对矩阵按列(或者行)排序即可。但是它具有O(n*n)复杂度,而我们的运算规模一般为n=4000~8000之间,维度在10个左右,用CPU实现的算法需要时间在10秒以上。我们的算法希望能够达到可交互的速度,因此CPU实现是无法满足我们对性能的要求。解决这个问题有两种选择:一种是采用改进过的算法,例如ANN算法,来取代kNN;另一种则是将kNN并行化。采用改进的算法要求建立特殊的数据结构,或者采用近似算法、牺牲一定的计算精度,然而我们希望得到的结果是精确的,而且并不打算改变数据结构。于是我们决定这个搜索并行化。

  并行化这个搜索的关键在于并行化距离矩阵的计算,即求出任意两个个体之间的距离。考虑到每两个个体之间的距离计算与其他个体无关,因此直接的方案就是利用CUDA中线程机制,每一个线程处理一对个体的距离计算。这个方案看起来似乎已经是最优化的方案了,因为里面没有任何冗余计算。出乎意料的是,我们按照这个方案实现的结果并不理想,加速比非常小(只有2~3倍)。

  运算次数上既然已经是最优了,那么问题肯定出在IO上。仔细检查程序,发现在GPU的计算核心(Kernel)上存在大量的访问冲突(Bank Conflict),并且由于并没有有效地利用共享内存(Shared Memory)等高速存储器。访问冲突导致的结果必然是程序性能低下,GPU的计算能力无法得到完全的发挥。另一方面,过多的使用全局内存(Global Memory)也导致在IO上花费了大量的时间。

  解决IO问题的关键在于避免访问冲突,而这要求我们设计一个合理的数据存取顺序。我们发现以矩阵来表示高维数据集,则距离矩阵的计算过程与矩阵乘法相似。如果记高维数据集为X(xi),其中xi为第i列的列向量个体,则距离矩阵D可以表示为D=X⊙XT,⊙代表如下计算:

  作为对比,这里列出矩阵乘法D’=XXT的运算规则:

利用CUDA加速k近邻算法

  这种相似性使得我们可以直接利用已有的各种高效并行矩阵乘法算法来计算距离矩阵。经过试验,我们最终采用了基于分块矩阵乘法的算法来计算距离矩阵。

  距离矩阵计算出来之后,需要通过列排序来获得每个个体的k个最近邻。直接进行完全的排序当然是一种可能的方案,但是却不是非常好的的方案,因为在我们的应用中一般k都非常小。在这种情况下,完全的排序引入了过多不必要的计算。我们设计了一种基于插入排序的算法,无需对整个矩阵进行列排序即可找到所有的k近邻。该算法的核心在于对每一个个体i,保持一个已经找到的k个最近邻集合K,并且线性扫描距离矩阵D中的列向量di,不断用距离该个体更近的个体更新集合K,从而最终得到全局的k近邻。集合K是一个有序的集合,因此仅需要通过一次判断即可确定是否需要更新该集合。在最坏的情况下,该算法的复杂度为Nklogk,而由于通常而言我们的k非常小(小于10),该算法的时间消耗可以与线性算法相媲美。当然,在k比较大的情形,这个算法是不适用的。

  我们的算法在Tesla C870上实现,与CPU(Intel Xeon 2.5GHz)上实现的算法相比有30~50倍的加速。我们并没有进行更多的代码级优化,因为一方面我们已经获得了期望中的结果,实现了可交互的超分辨率算法,另一方面则是由于我们还需要关注于整个项目的其他部分而无法在这里花费更多的时间。无论如何,在这个项目中我们通过GPU比较快速地对其中计算密集而且时间消耗大的部分进行了加速,并且最终获得了较高的加速比;而最令人兴奋的是,我们以很小的时间、精力代价获得了巨大的性能提升。这也正是本人所体验到的基于CUDA的GPU并行程序设计之魅力所在。

0
相关文章