基于GPU的K-近鄰算法實(shí)現(xiàn)

田 盼,華 蓓,陸 李

(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥230027)

基于GPU的K-近鄰算法實(shí)現(xiàn)

田 盼,華 蓓,陸 李

(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥230027)

K-近鄰計(jì)算在數(shù)據(jù)集規(guī)模較大時(shí)計(jì)算復(fù)雜度較高,因此,利用圖形處理器(GPU)強(qiáng)大的并行計(jì)算能力對(duì)K-近鄰算法進(jìn)行加速。在分析現(xiàn)有K-近鄰算法的基礎(chǔ)上,針對(duì)該算法時(shí)間開銷過大的問題,結(jié)合GPU的體系結(jié)構(gòu)特征實(shí)現(xiàn)基于GPU的K-近鄰算法。利用全局存儲(chǔ)器的合并訪問特性,提高GPU全局存儲(chǔ)器訪問數(shù)據(jù)的效率,通過事先過濾數(shù)據(jù)的方法來減少參與排序的數(shù)據(jù)量,進(jìn)而減少排序階段的線程串行化時(shí)間。在KDD,Poker, Covertype 3個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),結(jié)果表明,該實(shí)現(xiàn)方法在距離計(jì)算階段每秒執(zhí)行的浮點(diǎn)運(yùn)算次數(shù)為266.37×109次,而排序階段為26.47×109次,優(yōu)于已有方法。

K-近鄰問題;圖形處理器;并行計(jì)算;算法加速;合并訪問;全局存儲(chǔ)器

1 概述

異常檢測(cè)是指發(fā)現(xiàn)系統(tǒng)或用戶偏離常規(guī)的行為。異常檢測(cè)在信用卡欺詐[1]、網(wǎng)絡(luò)入侵[2]、系統(tǒng)故障檢測(cè)[3]等方面具有廣泛應(yīng)用。通常將正常的行為特征存儲(chǔ)在數(shù)據(jù)庫中,然后將當(dāng)前行為特征與數(shù)據(jù)庫中的行為特征進(jìn)行比較,當(dāng)兩者偏差足夠大時(shí)判斷發(fā)生了異常。局部異常因子(Local Outlier Factor,LOF)[4]算法是目前應(yīng)用最廣泛的離群點(diǎn)檢測(cè)算法,它通過計(jì)算每個(gè)對(duì)象相對(duì)于其鄰域的孤立情況(局部離群因子)來判斷對(duì)象是否為離群點(diǎn),進(jìn)而判定是否異常。然而LOF算法的計(jì)算復(fù)雜度很高,其中,最耗時(shí)的操作是計(jì)算每個(gè)對(duì)象的k個(gè)最近鄰居[5]。這是另一個(gè)經(jīng)典問題,稱K-近鄰(K-nearest Neighbor,KNN)問題。

K-近鄰計(jì)算在模式識(shí)別、分類、回歸等方面都有重要應(yīng)用。K-近鄰問題可以定義為:給定d維空間上的一個(gè)對(duì)象集合S={vi|vi∈Rd,i=1,2,…,n},距離函數(shù)δ和整數(shù)k,求出離對(duì)象vi最近的k個(gè)對(duì)象。KNN問題通常采用暴力求解方法,找到距離某個(gè)對(duì)象最近的k個(gè)鄰居的計(jì)算復(fù)雜度為O(dn+nlbn),其中,d是對(duì)象的數(shù)據(jù)維度;n是集合內(nèi)對(duì)象數(shù)量。一些KNN算法[6]被提出以降低K-近鄰搜索的復(fù)雜度,但在數(shù)據(jù)規(guī)模較大時(shí),這種優(yōu)化算法的時(shí)間開銷仍然過重[7]。按照離群因子的計(jì)算方法,LOF算法的時(shí)間復(fù)雜度為O(dnk+nklbn)[4]。在一些異常檢測(cè)問題中n往往很大,比如NASA采集的數(shù)據(jù)可能達(dá)到數(shù)百萬,這使得KNN計(jì)算成為L(zhǎng)OF算法的瓶頸。

近幾年來,圖形處理器(Graphic Processor Unit, GPU)已發(fā)展成為擁有成百上千個(gè)核、具有強(qiáng)大計(jì)算能力的數(shù)據(jù)處理單元。統(tǒng)一計(jì)算設(shè)備架構(gòu)(Compute Unified Device Architecture,CUDA)[8]的提出使得GPU的應(yīng)用領(lǐng)域從圖形處理很快擴(kuò)展到通用計(jì)算[9-11]。CUDA是NVIDIA推出的一個(gè)通用并行計(jì)算架構(gòu),它允許開發(fā)人員使用C語言為GPU編寫程序[12]。目前,不少研究工作試圖將一些計(jì)算密集的任務(wù)交給GPU完成,包括將KNN計(jì)算交給GPU完成[7,13]。

如下因素影響算法在GPU上的執(zhí)行性能: (1)數(shù)據(jù)在CPU和GPU之間的移動(dòng)開銷;(2)GPU中線程的并發(fā)執(zhí)行度。文獻(xiàn)[7,13]主要利用GPU的片上存儲(chǔ)資源來減少數(shù)據(jù)移動(dòng),以及將計(jì)算任務(wù)分布到GPU的眾多核上實(shí)現(xiàn)并行處理。然而GPU的片上存儲(chǔ)資源很有限,且這些資源還要被系統(tǒng)本身使用,當(dāng)數(shù)據(jù)集規(guī)模很大時(shí)效果不佳。其次,排序是數(shù)據(jù)依賴性很強(qiáng)的一種運(yùn)算,已有算法在利用多個(gè)線程實(shí)現(xiàn)排序時(shí),線程的并發(fā)執(zhí)行度很低。

本文給出一種在GPU上高效實(shí)現(xiàn)KNN算法的方法。該方法利用GPU片外全局存儲(chǔ)器的合并訪問特性,提高數(shù)據(jù)移動(dòng)的效率,并通過減少參與排序的對(duì)象數(shù)量來減少線程串行化執(zhí)行時(shí)間。

2 相關(guān)工作

GPU的計(jì)算單元被組織在2層結(jié)構(gòu)中。每個(gè)GPU由多個(gè)流多處理器(Streaming Multiprocessor, SM)組成,每個(gè)SM包含一定數(shù)量的流處理器(Streaming Processor,SP)。SM采用單指令流多數(shù)據(jù)流的執(zhí)行模式,一個(gè)SM中所有的SP執(zhí)行相同的代碼。GPU執(zhí)行的代碼稱為內(nèi)核,內(nèi)核在GPU中被多個(gè)線程執(zhí)行。GPU中的線程也被組織成2層,一定數(shù)量的線程先被組織成束(warp),一定數(shù)量的束再組織成塊(block)。每個(gè)線程塊被分配給一個(gè)SM執(zhí)行,SM中的warp調(diào)度器每次調(diào)度一個(gè)warp在SP上運(yùn)行。

GPU可以使用5類存儲(chǔ)資源,除全局存儲(chǔ)器以外,其余均為片上存儲(chǔ)器:(1)全局存儲(chǔ)器,可被GPU上所有線程訪問,存儲(chǔ)容量最大;(2)共享存儲(chǔ)器,可被同一個(gè)塊中的線程共享,容量有限;(3)紋理存儲(chǔ)器;(4)常數(shù)存儲(chǔ)器,它與紋理存儲(chǔ)器都為只讀存儲(chǔ)器;(5)本地存儲(chǔ)器,為每個(gè)線程所私有,容量很小,超出容量的數(shù)據(jù)保存在全局存儲(chǔ)器中。片上存儲(chǔ)器的訪問速度較快,全局存儲(chǔ)器的隨機(jī)訪問速度較慢,但它的合并訪問非常高效,即如果一個(gè)warp中所有線程要訪問的數(shù)據(jù)剛好在同一個(gè)Cache行中,則這些數(shù)據(jù)訪問在一次讀/寫事務(wù)中就可完成。

文獻(xiàn)[7]使用紋理存儲(chǔ)器存放參考對(duì)象集,全局存儲(chǔ)器存放待計(jì)算的對(duì)象集(稱查詢對(duì)象集),每個(gè)線程負(fù)責(zé)一個(gè)查詢對(duì)象的KNN計(jì)算。由于warp中的所有線程執(zhí)行相同的代碼,而排序操作對(duì)數(shù)據(jù)的依賴性很大,這種簡(jiǎn)單的并行化方法導(dǎo)致很嚴(yán)重的線程串行化。

文獻(xiàn)[13]在計(jì)算距離時(shí),先啟動(dòng)線程把參考對(duì)象集和查詢對(duì)象集讀入共享存儲(chǔ)器,每個(gè)線程塊負(fù)責(zé)一個(gè)查詢對(duì)象的KNN計(jì)算。每個(gè)線程塊維護(hù)一個(gè)包含k個(gè)元素的大根堆,保存當(dāng)前找到的k個(gè)最小距離。每個(gè)線程負(fù)責(zé)一部分距離的排序,整個(gè)排序過程劃分為一系列循環(huán)。在每次循環(huán)中,各線程獨(dú)立讀取距離值,與堆頂元素比較,小于堆頂?shù)木嚯x被記錄在線程的本地存儲(chǔ)器中。在循環(huán)結(jié)束后,各線程將本地存儲(chǔ)器中的距離逐個(gè)插入到堆中,然后開始下一次循環(huán)。雖然本地存儲(chǔ)器的使用避免了線程間同步,但當(dāng)保存的距離較多時(shí),這些距離實(shí)際上是存放在訪問速度較慢的全局存儲(chǔ)器中。另外,各線程將距離值插入堆中這個(gè)過程是串行化的。

3 基于GPU的KNN算法實(shí)現(xiàn)

K-近鄰計(jì)算包括距離計(jì)算和排序2個(gè)步驟。由于各個(gè)查詢對(duì)象的距離計(jì)算和排序是獨(dú)立無關(guān)的,因此該問題具有天然的并行性。但是,如果只是簡(jiǎn)單地將一個(gè)查詢對(duì)象分配給一個(gè)線程或一個(gè)線程塊處理,而不解決好數(shù)據(jù)移動(dòng)和線程同步的問題,則無法獲得最佳的性能。由于一個(gè)warp中的線程是鎖步執(zhí)行的,較大的內(nèi)核容易出現(xiàn)線程串行化,因此將距離計(jì)算和排序分到2個(gè)內(nèi)核中執(zhí)行。

3.1 距離計(jì)算

基于LOF算法的異常檢測(cè)涉及2個(gè)集合:參考對(duì)象集和查詢對(duì)象集。對(duì)于每個(gè)查詢對(duì)象,計(jì)算其在參考對(duì)象集中的本地離群因子,進(jìn)而判斷對(duì)象是否異常。因此,距離計(jì)算階段需要計(jì)算每個(gè)查詢對(duì)象與每個(gè)參考對(duì)象之間的歐幾里德距離。

由于GPU內(nèi)部的線程調(diào)度、線程執(zhí)行等都需要使用片上存儲(chǔ)資源,人為過多地干預(yù)這部分資源的使用可能反而影響系統(tǒng)性能,因此僅使用全局存儲(chǔ)器保存參考對(duì)象集和查詢對(duì)象集。為克服全局存儲(chǔ)器隨機(jī)訪問速度慢的缺點(diǎn),需要充分利用其合并訪問特性來提高數(shù)據(jù)移動(dòng)效率。

假設(shè)參考對(duì)象集有n個(gè)對(duì)象,查詢對(duì)象集有m個(gè)對(duì)象,每個(gè)對(duì)象的數(shù)據(jù)維度為d。將參考對(duì)象集存儲(chǔ)為d×n的矩陣,將查詢對(duì)象集存儲(chǔ)為d×m的矩陣,同一維度的數(shù)據(jù)連續(xù)存放。此外,查詢對(duì)象與參考對(duì)象的距離存放在m×n的矩陣C中,同一個(gè)查詢對(duì)象的距離值連續(xù)存放。

為了劃分計(jì)算任務(wù),將矩陣C劃分為一系列大小為T1×T2的小矩陣(圖1),每個(gè)小矩陣分配給一個(gè)線程塊計(jì)算,線程塊內(nèi)的每個(gè)線程計(jì)算一對(duì)＜查詢對(duì)象,參考對(duì)象＞之間的距離。為了實(shí)現(xiàn)合并訪問,當(dāng)從全局存儲(chǔ)器讀取T1個(gè)參考對(duì)象(或T2個(gè)查詢對(duì)象)時(shí),每個(gè)線程按照間隔T1(或T2)讀取數(shù)據(jù)。

圖1 距離矩陣的劃分

采用以上數(shù)據(jù)存儲(chǔ)方法和數(shù)據(jù)訪問方法之后,數(shù)據(jù)的讀、寫操作均可以通過合并訪問來得到優(yōu)化。

3.2 k個(gè)最小距離的查找

當(dāng)參考點(diǎn)數(shù)量n很大時(shí),對(duì)n個(gè)距離全排序非常耗時(shí)。然而只關(guān)心最小的k個(gè)值,且k通常遠(yuǎn)小于n,因此考慮在排序前先過濾掉大部分?jǐn)?shù)據(jù),然后從剩余的數(shù)據(jù)中選擇最小的k個(gè)。具體來說,設(shè)定一個(gè)全局過濾閾值,各線程獨(dú)立地進(jìn)行距離過濾,最后合并剩余的距離進(jìn)行排序。這里需要解決閾值的選取和動(dòng)態(tài)調(diào)整的問題。

過濾閾值的選取顯然和參考對(duì)象集有關(guān)。在這里先定義k-距離的概念,一個(gè)對(duì)象與其第k個(gè)鄰居(按距離從小到大排列)的距離稱為該對(duì)象的k-距離。為選取閾值的初始值,計(jì)算參考集內(nèi)每個(gè)對(duì)象的k-距離,并將這些k-距離從小到大排列,初始閾值就取為這個(gè)距離序列的中值。由于參考集是事先給定的,這個(gè)距離序列可以預(yù)先離線計(jì)算。

由于沒有先驗(yàn)知識(shí),初始閾值可能會(huì)過大或過小,為此設(shè)計(jì)動(dòng)態(tài)調(diào)整的過程。每個(gè)線程根據(jù)閾值獨(dú)立進(jìn)行過濾,小于閾值的距離被保存下來并統(tǒng)計(jì)數(shù)量。一輪過濾結(jié)束后,統(tǒng)計(jì)保存下來的距離數(shù)量。如果數(shù)量超過一個(gè)給定的值(為敘述方便記為p?k,p是與k相關(guān)的一個(gè)數(shù)),選取距離序列中下半部分的中位數(shù)作為新的閾值;如果數(shù)量小于k,則選取距離序列中上半部分的中位數(shù)作為新的閾值。確定新的閾值后,開始新一輪過濾,直到保留下來的距離數(shù)量落在[k,p?k]內(nèi)。

在一些極端情況中,查詢對(duì)象的k-距離可能非常接近甚至超出兩邊的邊界(分別記為min_dist和max_dist)。對(duì)此,當(dāng)剩余距離的數(shù)量連續(xù)2次大于p?k或小于k時(shí),在更新閾值前先調(diào)整相應(yīng)的邊界。當(dāng)統(tǒng)計(jì)數(shù)量連續(xù)大于p?k時(shí),按式(1)減小min_dist,并按式(2)調(diào)整閾值。當(dāng)統(tǒng)計(jì)數(shù)量連續(xù)小于k時(shí),按式(3)增大max_dist,并按式(4)調(diào)整閾值。r1和r2是不同的比例因子,并可能因數(shù)據(jù)集而異。

在過濾過程結(jié)束后,各線程將保留下來的距離值拷貝到片上共享存儲(chǔ)器中進(jìn)行排序。采用具有k個(gè)元素的大根堆進(jìn)行排序,排序結(jié)果寫回到全局存儲(chǔ)器。由于排序過程是串行的,p?k越接近k越好;但是p?k太小可能導(dǎo)致過濾輪數(shù)較多。因此,p?k值的選取要權(quán)衡這兩方面的開銷。

對(duì)過濾階段的距離存儲(chǔ)進(jìn)行了優(yōu)化:線程并不將保留下來的距離存放在本地存儲(chǔ)器,這是因?yàn)楫?dāng)距離數(shù)量較多時(shí),這些距離實(shí)際上存放在全局存儲(chǔ)器中,而這時(shí)的寫操作并不是合并操作。令每個(gè)線程維護(hù)一個(gè)比特串,該比特串對(duì)應(yīng)矩陣C中該線程所負(fù)責(zé)的那一部分距離。當(dāng)某個(gè)距離小于閾值時(shí),線程將比特串中對(duì)應(yīng)該距離的比特置位,該位置可根據(jù)列號(hào)和線程ID計(jì)算出來。由于比特串占用存儲(chǔ)空間少,因此可以放在本地存儲(chǔ)器中加快訪問。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在一臺(tái)Dell PowerEdge R720多核服務(wù)器上進(jìn)行,所用GPU為NVIDIA Tesla-M2090(512個(gè)SP,6 GB顯存),操作系統(tǒng)為Fedora11.10,軟件平臺(tái)為CUDA2.1。

使用了3個(gè)數(shù)據(jù)集[14]:(1)KDD CUP1999:包含4 000 000個(gè)數(shù)據(jù)對(duì)象,每個(gè)對(duì)象41個(gè)屬性。(2)Poker:包含1025 010個(gè)數(shù)據(jù)對(duì)象,每個(gè)對(duì)象10個(gè)屬性。(3)Covertype:包含581012個(gè)數(shù)據(jù)對(duì)象,每個(gè)對(duì)象10個(gè)屬性。從每個(gè)數(shù)據(jù)集的參考集里取20 000個(gè)對(duì)象組成參考對(duì)象集,從查詢集里取5 000個(gè)對(duì)象組成查詢對(duì)象集。

4.1 距離計(jì)算階段的實(shí)驗(yàn)

本節(jié)比較3種方法的性能。方法1為本文采用的方法(見3.1節(jié)),只使用全局存儲(chǔ)器保存參考對(duì)象集和查詢對(duì)象集;方法2實(shí)現(xiàn)了文獻(xiàn)[13]提出的存儲(chǔ)方式,將參考對(duì)象集和查詢對(duì)象集從全局存儲(chǔ)器顯式讀入共享存儲(chǔ)器;方法3實(shí)現(xiàn)了文獻(xiàn)[7]提出的存儲(chǔ)方式,使用紋理存儲(chǔ)器存儲(chǔ)參考對(duì)象集,使用全局存儲(chǔ)器存儲(chǔ)查詢對(duì)象集。在參考數(shù)據(jù)集(KDD, Poker和Covertype)上運(yùn)行這3種方法,測(cè)量系統(tǒng)在距離計(jì)算階段的性能,用每秒執(zhí)行的浮點(diǎn)運(yùn)算次數(shù)(GFlop/s)衡量。實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同方法在距離計(jì)算階段的性能109

從表1可以看到,在3種數(shù)據(jù)集上方法1都優(yōu)于其他2種方法,這表明本文方法是有效的。從表1還可以看到,在相同的數(shù)據(jù)集規(guī)模下,方法1在KDD數(shù)據(jù)集上的性能要優(yōu)于在另外2個(gè)數(shù)據(jù)集上的性能。對(duì)此可能的解釋是,KDD數(shù)據(jù)集的數(shù)據(jù)維度是41,其他2個(gè)數(shù)據(jù)集的數(shù)據(jù)維度都是10,較大的數(shù)據(jù)量和計(jì)算量有利于CUDA程序在執(zhí)行時(shí)隱藏?cái)?shù)據(jù)移動(dòng)和訪存開銷,從而計(jì)算效率更高。

4.2 排序階段的實(shí)驗(yàn)

本節(jié)比較3種方法的性能。方法4為本文采用的方法(見3.2節(jié))。由于p?k的取值影響過濾的輪數(shù)和最后參與排序的距離數(shù)目,對(duì)系統(tǒng)性能影響較大,而p?k的選取與數(shù)據(jù)集特性有關(guān),為此,取不同的p?k值進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)發(fā)現(xiàn),當(dāng)k分別取20, 40,80,100時(shí),在KDD數(shù)據(jù)集上p?k分別取80, 120,150,220時(shí)性能最佳,而在Poker和Covertype數(shù)據(jù)集上p?k分別取60,100,120,200時(shí)性能最佳。以下實(shí)驗(yàn)中使用了這些參數(shù)設(shè)置。需要注意的是,對(duì)于一個(gè)特定的異常檢測(cè)問題,參考集是預(yù)知的,因而通過離線實(shí)驗(yàn)獲得最佳參數(shù)設(shè)置是可能的。方法5實(shí)現(xiàn)了文獻(xiàn)[13]在距離排序階段提出的方法,并且將參與排序的距離值預(yù)先存儲(chǔ)在全局存儲(chǔ)器中。方法6將以上2種方法結(jié)合起來,首先通過一到幾輪過濾得到q個(gè)參與排序的距離值(一旦滿足q≥k即停止過濾),然后用并行堆排序的方法從q個(gè)距離中找到k個(gè)最小值。

在參考數(shù)據(jù)集上運(yùn)行以上3種方法求最小的k個(gè)距離,表2～表4為k取不同值時(shí)系統(tǒng)的計(jì)算性能(同樣用GFlop/s衡量)。

表2 KDD數(shù)據(jù)集上的計(jì)算性能109

表3 Poker數(shù)據(jù)集上的計(jì)算性能109

表4 Covertype數(shù)據(jù)集上的計(jì)算性能109

從表2～表4可以看到,在不同數(shù)據(jù)集上方法4都優(yōu)于其他2種方法,這表明該方法是有效的。盡管本文方法需要先進(jìn)行多次過濾來獲得一個(gè)較小的待排序數(shù)據(jù)集合,但由于各線程的過濾操作是完全并行執(zhí)行的,這個(gè)過程其實(shí)非常快;而帶來的好處則是極大地減小了排序階段線程串行化執(zhí)行的時(shí)間,當(dāng)n很大時(shí)帶來的性能提高是非常明顯的。

從表2～表4還可以看到,隨著k的增大,3種方法的吞吐率總體上是下降的,這是因?yàn)榕判螂A段線程串行化執(zhí)行的時(shí)間增大了。

5 結(jié)束語

本文在GPU上實(shí)現(xiàn)了對(duì)K-近鄰算法的并行加速,算法包括距離計(jì)算和k個(gè)最小距離查找2個(gè)階段。距離計(jì)算階段重新組織了數(shù)據(jù)的存儲(chǔ)方式,以充分利用全局存儲(chǔ)器的合并訪問能力;k個(gè)最小距離查找階段被分為2個(gè)步驟(距離值過濾和排序),以盡量減少線程串行化執(zhí)行時(shí)間,過濾時(shí)所有線程可以并行執(zhí)行,只有少量的距離值參與排序。實(shí)驗(yàn)結(jié)果表明,系統(tǒng)性能得到有效提高。

[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] 程 豪,張?jiān)迫?張先軼,等.CPU-GPU并行矩陣乘法的實(shí)現(xiàn)與性能分析[J].計(jì)算機(jī)工程,2010,36(13): 24-26,29.

[11] 陳 鵬,曹劍煒,陳慶奎.基于GPU的H.264并行解碼算法[J].計(jì)算機(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-近鄰算法實(shí)現(xiàn)[J].計(jì)算機(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-),女,碩士研究生,主研方向:機(jī)器學(xué)習(xí),模式識(shí)別;華 蓓,教授;陸 李,博士研究生。

2014-04-01

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