基于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