基于GPU的K-近邻算法实现

田 盼,华 蓓,陆 李

(中国科学技术大学计算机科学与技术学院,合肥230027)

基于GPU的K-近邻算法实现

田 盼,华 蓓,陆 李

(中国科学技术大学计算机科学与技术学院,合肥230027)

K-近邻计算在数据集规模较大时计算复杂度较高,因此,利用图形处理器(GPU)强大的并行计算能力对K-近邻算法进行加速。在分析现有K-近邻算法的基础上,针对该算法时间开销过大的问题,结合GPU的体系结构特征实现基于GPU的K-近邻算法。利用全局存储器的合并访问特性,提高GPU全局存储器访问数据的效率,通过事先过滤数据的方法来减少参与排序的数据量,进而减少排序阶段的线程串行化时间。在KDD,Poker, Covertype 3个数据集上进行实验,结果表明,该实现方法在距离计算阶段每秒执行的浮点运算次数为266.37×109次,而排序阶段为26.47×109次,优于已有方法。

K-近邻问题;图形处理器;并行计算;算法加速;合并访问;全局存储器

1 概述

异常检测是指发现系统或用户偏离常规的行为。异常检测在信用卡欺诈[1]、网络入侵[2]、系统故障检测[3]等方面具有广泛应用。通常将正常的行为特征存储在数据库中,然后将当前行为特征与数据库中的行为特征进行比较,当两者偏差足够大时判断发生了异常。局部异常因子(Local Outlier Factor,LOF)[4]算法是目前应用最广泛的离群点检测算法,它通过计算每个对象相对于其邻域的孤立情况(局部离群因子)来判断对象是否为离群点,进而判定是否异常。然而LOF算法的计算复杂度很高,其中,最耗时的操作是计算每个对象的k个最近邻居[5]。这是另一个经典问题,称K-近邻(K-nearest Neighbor,KNN)问题。

K-近邻计算在模式识别、分类、回归等方面都有重要应用。K-近邻问题可以定义为:给定d维空间上的一个对象集合S={vi|vi∈Rd,i=1,2,…,n},距离函数δ和整数k,求出离对象vi最近的k个对象。KNN问题通常采用暴力求解方法,找到距离某个对象最近的k个邻居的计算复杂度为O(dn+nlbn),其中,d是对象的数据维度;n是集合内对象数量。一些KNN算法[6]被提出以降低K-近邻搜索的复杂度,但在数据规模较大时,这种优化算法的时间开销仍然过重[7]。按照离群因子的计算方法,LOF算法的时间复杂度为O(dnk+nklbn)[4]。在一些异常检测问题中n往往很大,比如NASA采集的数据可能达到数百万,这使得KNN计算成为LOF算法的瓶颈。

近几年来,图形处理器(Graphic Processor Unit, GPU)已发展成为拥有成百上千个核、具有强大计算能力的数据处理单元。统一计算设备架构(Compute Unified Device Architecture,CUDA)[8]的提出使得GPU的应用领域从图形处理很快扩展到通用计算[9-11]。CUDA是NVIDIA推出的一个通用并行计算架构,它允许开发人员使用C语言为GPU编写程序[12]。目前,不少研究工作试图将一些计算密集的任务交给GPU完成,包括将KNN计算交给GPU完成[7,13]。

如下因素影响算法在GPU上的执行性能: (1)数据在CPU和GPU之间的移动开销;(2)GPU中线程的并发执行度。文献[7,13]主要利用GPU的片上存储资源来减少数据移动,以及将计算任务分布到GPU的众多核上实现并行处理。然而GPU的片上存储资源很有限,且这些资源还要被系统本身使用,当数据集规模很大时效果不佳。其次,排序是数据依赖性很强的一种运算,已有算法在利用多个线程实现排序时,线程的并发执行度很低。

本文给出一种在GPU上高效实现KNN算法的方法。该方法利用GPU片外全局存储器的合并访问特性,提高数据移动的效率,并通过减少参与排序的对象数量来减少线程串行化执行时间。

2 相关工作

GPU的计算单元被组织在2层结构中。每个GPU由多个流多处理器(Streaming Multiprocessor, SM)组成,每个SM包含一定数量的流处理器(Streaming Processor,SP)。SM采用单指令流多数据流的执行模式,一个SM中所有的SP执行相同的代码。GPU执行的代码称为内核,内核在GPU中被多个线程执行。GPU中的线程也被组织成2层,一定数量的线程先被组织成束(warp),一定数量的束再组织成块(block)。每个线程块被分配给一个SM执行,SM中的warp调度器每次调度一个warp在SP上运行。

GPU可以使用5类存储资源,除全局存储器以外,其余均为片上存储器:(1)全局存储器,可被GPU上所有线程访问,存储容量最大;(2)共享存储器,可被同一个块中的线程共享,容量有限;(3)纹理存储器;(4)常数存储器,它与纹理存储器都为只读存储器;(5)本地存储器,为每个线程所私有,容量很小,超出容量的数据保存在全局存储器中。片上存储器的访问速度较快,全局存储器的随机访问速度较慢,但它的合并访问非常高效,即如果一个warp中所有线程要访问的数据刚好在同一个Cache行中,则这些数据访问在一次读/写事务中就可完成。

文献[7]使用纹理存储器存放参考对象集,全局存储器存放待计算的对象集(称查询对象集),每个线程负责一个查询对象的KNN计算。由于warp中的所有线程执行相同的代码,而排序操作对数据的依赖性很大,这种简单的并行化方法导致很严重的线程串行化。

文献[13]在计算距离时,先启动线程把参考对象集和查询对象集读入共享存储器,每个线程块负责一个查询对象的KNN计算。每个线程块维护一个包含k个元素的大根堆,保存当前找到的k个最小距离。每个线程负责一部分距离的排序,整个排序过程划分为一系列循环。在每次循环中,各线程独立读取距离值,与堆顶元素比较,小于堆顶的距离被记录在线程的本地存储器中。在循环结束后,各线程将本地存储器中的距离逐个插入到堆中,然后开始下一次循环。虽然本地存储器的使用避免了线程间同步,但当保存的距离较多时,这些距离实际上是存放在访问速度较慢的全局存储器中。另外,各线程将距离值插入堆中这个过程是串行化的。

3 基于GPU的KNN算法实现

K-近邻计算包括距离计算和排序2个步骤。由于各个查询对象的距离计算和排序是独立无关的,因此该问题具有天然的并行性。但是,如果只是简单地将一个查询对象分配给一个线程或一个线程块处理,而不解决好数据移动和线程同步的问题,则无法获得最佳的性能。由于一个warp中的线程是锁步执行的,较大的内核容易出现线程串行化,因此将距离计算和排序分到2个内核中执行。

3.1 距离计算

基于LOF算法的异常检测涉及2个集合:参考对象集和查询对象集。对于每个查询对象,计算其在参考对象集中的本地离群因子,进而判断对象是否异常。因此,距离计算阶段需要计算每个查询对象与每个参考对象之间的欧几里德距离。

由于GPU内部的线程调度、线程执行等都需要使用片上存储资源,人为过多地干预这部分资源的使用可能反而影响系统性能,因此仅使用全局存储器保存参考对象集和查询对象集。为克服全局存储器随机访问速度慢的缺点,需要充分利用其合并访问特性来提高数据移动效率。

假设参考对象集有n个对象,查询对象集有m个对象,每个对象的数据维度为d。将参考对象集存储为d×n的矩阵,将查询对象集存储为d×m的矩阵,同一维度的数据连续存放。此外,查询对象与参考对象的距离存放在m×n的矩阵C中,同一个查询对象的距离值连续存放。

为了划分计算任务,将矩阵C划分为一系列大小为T1×T2的小矩阵(图1),每个小矩阵分配给一个线程块计算,线程块内的每个线程计算一对＜查询对象,参考对象＞之间的距离。为了实现合并访问,当从全局存储器读取T1个参考对象(或T2个查询对象)时,每个线程按照间隔T1(或T2)读取数据。

图1 距离矩阵的划分

采用以上数据存储方法和数据访问方法之后,数据的读、写操作均可以通过合并访问来得到优化。

3.2 k个最小距离的查找

当参考点数量n很大时,对n个距离全排序非常耗时。然而只关心最小的k个值,且k通常远小于n,因此考虑在排序前先过滤掉大部分数据,然后从剩余的数据中选择最小的k个。具体来说,设定一个全局过滤阈值,各线程独立地进行距离过滤,最后合并剩余的距离进行排序。这里需要解决阈值的选取和动态调整的问题。

过滤阈值的选取显然和参考对象集有关。在这里先定义k-距离的概念,一个对象与其第k个邻居(按距离从小到大排列)的距离称为该对象的k-距离。为选取阈值的初始值,计算参考集内每个对象的k-距离,并将这些k-距离从小到大排列,初始阈值就取为这个距离序列的中值。由于参考集是事先给定的,这个距离序列可以预先离线计算。

由于没有先验知识,初始阈值可能会过大或过小,为此设计动态调整的过程。每个线程根据阈值独立进行过滤,小于阈值的距离被保存下来并统计数量。一轮过滤结束后,统计保存下来的距离数量。如果数量超过一个给定的值(为叙述方便记为p∗k,p是与k相关的一个数),选取距离序列中下半部分的中位数作为新的阈值;如果数量小于k,则选取距离序列中上半部分的中位数作为新的阈值。确定新的阈值后,开始新一轮过滤,直到保留下来的距离数量落在[k,p∗k]内。

在一些极端情况中,查询对象的k-距离可能非常接近甚至超出两边的边界(分别记为min_dist和max_dist)。对此,当剩余距离的数量连续2次大于p∗k或小于k时,在更新阈值前先调整相应的边界。当统计数量连续大于p∗k时,按式(1)减小min_dist,并按式(2)调整阈值。当统计数量连续小于k时,按式(3)增大max_dist,并按式(4)调整阈值。r1和r2是不同的比例因子,并可能因数据集而异。

在过滤过程结束后,各线程将保留下来的距离值拷贝到片上共享存储器中进行排序。采用具有k个元素的大根堆进行排序,排序结果写回到全局存储器。由于排序过程是串行的,p∗k越接近k越好;但是p∗k太小可能导致过滤轮数较多。因此,p∗k值的选取要权衡这两方面的开销。

对过滤阶段的距离存储进行了优化:线程并不将保留下来的距离存放在本地存储器,这是因为当距离数量较多时,这些距离实际上存放在全局存储器中,而这时的写操作并不是合并操作。令每个线程维护一个比特串,该比特串对应矩阵C中该线程所负责的那一部分距离。当某个距离小于阈值时,线程将比特串中对应该距离的比特置位,该位置可根据列号和线程ID计算出来。由于比特串占用存储空间少,因此可以放在本地存储器中加快访问。

4 实验结果与分析

实验在一台Dell PowerEdge R720多核服务器上进行,所用GPU为NVIDIA Tesla-M2090(512个SP,6 GB显存),操作系统为Fedora11.10,软件平台为CUDA2.1。

使用了3个数据集[14]:(1)KDD CUP1999:包含4 000 000个数据对象,每个对象41个属性。(2)Poker:包含1025 010个数据对象,每个对象10个属性。(3)Covertype:包含581012个数据对象,每个对象10个属性。从每个数据集的参考集里取20 000个对象组成参考对象集,从查询集里取5 000个对象组成查询对象集。

4.1 距离计算阶段的实验

本节比较3种方法的性能。方法1为本文采用的方法(见3.1节),只使用全局存储器保存参考对象集和查询对象集;方法2实现了文献[13]提出的存储方式,将参考对象集和查询对象集从全局存储器显式读入共享存储器;方法3实现了文献[7]提出的存储方式,使用纹理存储器存储参考对象集,使用全局存储器存储查询对象集。在参考数据集(KDD, Poker和Covertype)上运行这3种方法,测量系统在距离计算阶段的性能,用每秒执行的浮点运算次数(GFlop/s)衡量。实验结果如表1所示。

表1 不同方法在距离计算阶段的性能109

从表1可以看到,在3种数据集上方法1都优于其他2种方法,这表明本文方法是有效的。从表1还可以看到,在相同的数据集规模下,方法1在KDD数据集上的性能要优于在另外2个数据集上的性能。对此可能的解释是,KDD数据集的数据维度是41,其他2个数据集的数据维度都是10,较大的数据量和计算量有利于CUDA程序在执行时隐藏数据移动和访存开销,从而计算效率更高。

4.2 排序阶段的实验

本节比较3种方法的性能。方法4为本文采用的方法(见3.2节)。由于p∗k的取值影响过滤的轮数和最后参与排序的距离数目,对系统性能影响较大,而p∗k的选取与数据集特性有关,为此,取不同的p∗k值进行实验。实验发现,当k分别取20, 40,80,100时,在KDD数据集上p∗k分别取80, 120,150,220时性能最佳,而在Poker和Covertype数据集上p∗k分别取60,100,120,200时性能最佳。以下实验中使用了这些参数设置。需要注意的是,对于一个特定的异常检测问题,参考集是预知的,因而通过离线实验获得最佳参数设置是可能的。方法5实现了文献[13]在距离排序阶段提出的方法,并且将参与排序的距离值预先存储在全局存储器中。方法6将以上2种方法结合起来,首先通过一到几轮过滤得到q个参与排序的距离值(一旦满足q≥k即停止过滤),然后用并行堆排序的方法从q个距离中找到k个最小值。

在参考数据集上运行以上3种方法求最小的k个距离,表2～表4为k取不同值时系统的计算性能(同样用GFlop/s衡量)。

表2 KDD数据集上的计算性能109

表3 Poker数据集上的计算性能109

表4 Covertype数据集上的计算性能109

从表2～表4可以看到,在不同数据集上方法4都优于其他2种方法,这表明该方法是有效的。尽管本文方法需要先进行多次过滤来获得一个较小的待排序数据集合,但由于各线程的过滤操作是完全并行执行的,这个过程其实非常快;而带来的好处则是极大地减小了排序阶段线程串行化执行的时间,当n很大时带来的性能提高是非常明显的。

从表2～表4还可以看到,随着k的增大,3种方法的吞吐率总体上是下降的,这是因为排序阶段线程串行化执行的时间增大了。

5 结束语

本文在GPU上实现了对K-近邻算法的并行加速,算法包括距离计算和k个最小距离查找2个阶段。距离计算阶段重新组织了数据的存储方式,以充分利用全局存储器的合并访问能力;k个最小距离查找阶段被分为2个步骤(距离值过滤和排序),以尽量减少线程串行化执行时间,过滤时所有线程可以并行执行,只有少量的距离值参与排序。实验结果表明,系统性能得到有效提高。

[1] Chen M C,Wang R J,Chen A P.An Empirical Study for the Detection of Corporate Financial Anomaly Using OutlierMiningTechniques[C]//Proceedingsof International Conference on Convergence Information Technology.[S.l.]:IEEE Press,2007:612-617.

[2] Lazarevic A,Ertöz L,Kumar V,et al.A Comparative Study ofAnomalyDetectionSchemesinNetwork Intrusion Detection[C]//Proceedings of SDM’03. Chicago,USA:[s.n.],2003:25-36.

[3] Guttormsson S E,Marks R J,El-Sharkawi M A,et al. EllipticalNoveltyGroupingforOnlineShort-turn DetectionofExcitedRunningRotors[J].IEEE Transactions on Energy Conversion,1999,14(1): 16-22.

[4] Breunig M M,Kriegel H P,Ng R T,et al.LOF: IdentifyingDensity-basedLocalOutliers[C]// Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:[s.n.], 2000:93-104.

[5] Alshawabkeh M,Jang B,Kaeli D.Accelerating the Local Outlier FactorAlgorithmonaGPUforIntrusion DetectionSystems[C]//Proceedingsofthe3rd Workshop on General-purpose Computation on Graphics Processing Units.[S.l.]:ACM Press,2010:104-110.

[6] Arya S,Mount D M,Netanyahu N S,et al.An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions[J].Journal of the ACM,1998, 45(6):891-923.

[7] Garcia V,Debreuve E,Barlaud M.Fast K Nearest Neighbor Search Using GPU[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops.[S.l.]:IEEE Press, 2008:1-6.

[8] NVIDIA Co.,CUDA Zone[EB/OL].(2010-11-21). http://www.nvidia.com/object/cuda home.html.

[9] Dudek R,Cuenca C,Quintana F.Accelerating Space VariantGaussianFilteringonGraphicsProcessing Unit[M].Berlin,Germany:Springer Press,2007.

[10] 程 豪,张云泉,张先轶,等.CPU-GPU并行矩阵乘法的实现与性能分析[J].计算机工程,2010,36(13): 24-26,29.

[11] 陈 鹏,曹剑炜,陈庆奎.基于GPU的H.264并行解码算法[J].计算机工程,2014,40(1):283-286.

[12] NVIDIA Co.,CUDA 2.1Programming Guide[EB/OL]. (2008-11-21).http://www.nvidia.com/object/cudadeve lop.html.

[13] Kato K,Hosino T.Solving K-nearest Neighbor Problem on Multiple Graphics Processors[C]//Proceedings of the10thIEEE/ACMInternationalConferenceon Cluster,Cloud and Grid Computing.[S.l.]:IEEE Computer Society,2010:769-773.

[14] Asuncion A,NewmanD.UCIMachineLearning Repository[J].Knowledge and Information Systems, 2007,18(1):1-4.

编辑 刘 冰

Implementation of K-nearest Neighbor Algorithm Based on GPU

TIAN Pan,HUA Bei,LU Li
(School of Computer Science&Technology,University of Science and Technology of China,Hefei 230027,China)

K-nearest Neighbor(KNN)is a classical problem whose computational complexity increases rapidly with the size of data set.It is an interesting research to accelerate KNN implementation on the Graphics Processor Unit(GPU)by employing GPU’s massive parallel computing power.For its heavy overhead on time,after analyzing the existing work of GPU-based KNN implementations and the architectural features of GPU,this paper efficiently parallelizes KNN on the GPU.It optimizes data access by making good use of the coalesced access power of global memory,and reduces thread serialization by filtering out as much data as possible in advance that is to be sorted.Experiments on KDD,Poker and Covertype datasets and comparisons with some existing methods show that the number of floating point arithmetic of executed per second of this distance computing method is up to 266.37×109,and is up to 26.47×109in sort phase, which are superior to that of existed methods.

K-nearest Neighbor(KNN)problem;Graphics Processing Unit(GPU);parallel computing;algorithm acceleration;coalesced access;global memory

田 盼,华 蓓,陆 李.基于GPU的K-近邻算法实现[J].计算机工程,2015,41(2):189-192,198.

英文引用格式:Tian Pan,Hua Bei,Lu Li.Implementation of K-nearest Neighbor Algorithm Based on GPU[J]. Computer Engineering,2015,41(2):189-192,198.

1000-3428(2015)02-0189-04

:A

:TP311

10.3969/j.issn.1000-3428.2015.02.036

田 盼(1989-),女,硕士研究生,主研方向:机器学习,模式识别;华 蓓,教授;陆 李,博士研究生。

2014-04-01

:2014-05-04E-mail:ptian@mail.ustc.edu.cn