炼数成金 门户 CUDA 查看内容

KNN算法的CUDA实现

2015-9-9 12:16| 发布者: 炼数成金_小数| 查看: 2470| 评论: 0|原作者: Time_Runner|来自: Time_Runner的博客

摘要: 1. 算法思路KNN算法的基础是对给定的query点集,对应查找在参考空间中距离最近的K个紧邻点。KNN的应用方面非常广泛,在ICP配准问题,Spin-image旋转图像配准法,SIFT点提取,数据挖掘,机器学习等多个方面中有广泛应 ...

算法 测试 C++ GPU CUDA

1.  算法思路
KNN算法的基础是对给定的query点集,对应查找在参考空间中距离最近的K个紧邻点。KNN的应用方面非常广泛,在ICP配准问题,Spin-image旋转图像配准法,SIFT点提取,数据挖掘,机器学习等多个方面中有广泛应用。

KNN算法存在的一个重要问题是,繁重的计算量。如果参考空间由M个点,query点集有N个点,空间维度维d维,那么计算query点集与参考空间各个点集的距离就有O(mnd)的时间复杂度。同时,对于每一个query点计算出的M个距离进行排序,至少要有O(m*logm)的时间复杂度,仅仅排序就要有O(mn*logm)的时间复杂度。因此,整个KNN问题的时间复杂度为O(mnd)+O(mnlogm)。这里为了方便,输入参考空间与query点集都是n个点。

虽然针对于KNN算法有各种各样的优化方式,但是这里讨论的重点是CUDA对KNN问题的优化,因此采用最基础(也是最暴力的)Brute Force算法——穷举法。

虽然快排算法的效率很高,但是在CUDA中无法采用递归的方法,因此这里采用了插值方法,虽然梳排序(comb sort)的时间复杂度O(nlogn)要小于插值法O(n^2),但是在后面的分析中可以看到,针对于GPU环境下插值法可以取得更好的效果。

在CUDA中内存按照如下格式安排。

其中GPU可以被分为多个块,并自带有Register和shared memory,每个块可以直接访问constant与texture,从访问速度上讲,有registers --> shared memory --> constant memory --> RAM。

这里吧query sets安排在Texture memory中,把参考空间点放在Global 中。

2. cuda应用
a.  对比comb 与插值法
当给定N = 4800时,随着需要紧邻点个数的增加,comb 排序算法保持不变,但是插值法的计算时间不断增加。但是可以注意到,当所取K点比较少时,插值法明显优于Comb法,因此这里存在一个comb法与插值法相交的K0点。

下面给出测试点数与K0值的近似关系。

当测试点集与K值落在斜线右下方时,采用插值法要更优,反之亦然。针对于本问题,采用插值法更适合于KNN算法在CUDA上的应用。

3.  实验效果
采用了四种对比方法:

     · BF method implemented in Matlab (noted BF-Matlab)
     · BF method implemented in C (noted BF-C)
     · BF method implemented in CUDA (noted BF-CUDA)
     · ANN C++ library (noted ANN-C++)

一种比较直观的解释是,当采用38400个点,96个维度的空间进行测试时,BF-Matlab用了57分钟,BF-C用了44分钟,ANN-C++用了22分钟,BF-CUDA用了不到10s。。。

更有意思的是,当空间的维度不断提高时,其他算法的计算耗时也在不断提高,但是BF-cuda的耗时没有变化(在前面的乘法计算中也采用了并行处理的方式,因此尽管空间维度增加但是依然不会影响它的计算)。

4.  时间利用分析 
当采用4800点,32维空间,K取20时,CPU与GPU的时间利用对比。

CPU的主要耗时就是在O(nmd)的距离计算上,排序只用了很少时间,GPU虽然在排序上耗时比例大,但是整体应用时间很小,这得益于其并行处理的框架。

鲜花

握手

雷人

路过

鸡蛋

最新评论

 

GMT+8, 2020-10-26 00:06 , Processed in 0.099018 second(s), 23 queries .