一種基于OpenCL的高能效并行KNN算法及其GPU驗(yàn)證

賀　江，蒲宇亮，李海波，閻　波

（1.電子科技大學(xué)，四川 成都 610036；2.廣東省公安廳，廣東 廣州510050）

一種基于OpenCL的高能效并行KNN算法及其GPU驗(yàn)證

賀江1，蒲宇亮1，李海波2，閻波1

（1.電子科技大學(xué)，四川 成都 610036；2.廣東省公安廳，廣東 廣州510050）

近年來數(shù)據(jù)分類技術(shù)已經(jīng)被廣泛應(yīng)用于各類問題中，作為最重要的分類算法之一，K最近鄰法（KNN）也被廣泛使用。在過去的近50年，人們就如何提高KNN的并行性能做出巨大努力?；贑UDA的KNN并行實(shí)現(xiàn)算法——CUKNN算法證明KNN在GPU上的并行實(shí)現(xiàn)比在CPU上串行實(shí)現(xiàn)的速度提升數(shù)十倍，然而，CUDA在實(shí)現(xiàn)過程中包含了大量的冗余計(jì)算。提出了一種并行冒泡的新型KNN并行算法，并通過OpenCL，在以GPU作為計(jì)算核心的異構(gòu)系統(tǒng)上進(jìn)行驗(yàn)證，結(jié)果顯示提出的方法比CUDA快16倍。

KNN；GPGPU；OpenCL；并行冒泡；并行計(jì)算

0　引言

近年來，許多不同類型的處理器廣泛應(yīng)用于高性能計(jì)算領(lǐng)域，如GPU、FPGA、DSP等[1]，而異構(gòu)計(jì)算平臺由不同類型的處理器組成，能對許多不同的算法進(jìn)行加速實(shí)現(xiàn)。OpenCL是一種開放式的異構(gòu)計(jì)算標(biāo)準(zhǔn)，支持異構(gòu)系統(tǒng)的并行程序應(yīng)用。作為經(jīng)典聚類算法，KNN在文字識別、預(yù)測分析、圖像處理和圖像識別等方面[2]有非常重要的應(yīng)用。

為了加速KNN算法的實(shí)現(xiàn)，許多文章也提出了一些新的思路。Zhang Hao等[3]通過結(jié)合支持向量機(jī)(SVM)和KNN算法實(shí)現(xiàn)視覺分類識別。Garcia等[4]提出一種基于插入排序的快速KNN算法實(shí)現(xiàn)，并分析了奇偶排序和插入排序的性能。2009年，Liang Shenshen等人[5]提出了基于CUDA實(shí)現(xiàn)的并行KNN算法，稱該算法為CUKNN。該算法通過調(diào)用大量GPU線程，在計(jì)算待分類數(shù)據(jù)和參考數(shù)據(jù)集時(shí)高度并化，然后對距離進(jìn)行并行排序。

基于CPU+GPU的異構(gòu)計(jì)算系統(tǒng)最近幾年在算法加速方面得到了廣泛使用，如神經(jīng)網(wǎng)絡(luò)[6]、數(shù)據(jù)挖掘[7]等。而基于CPU+FPGA系統(tǒng)由于其能效優(yōu)勢[8]，得到業(yè)界的認(rèn)可。

本文提出了一種基于 CPU+GPU異構(gòu)計(jì)算系統(tǒng)的KNN并行算法。該方法將待分類的數(shù)據(jù)集通過并行冒泡的方法進(jìn)行分類，稱該方法為PBKNN（parallel sort）。

1　KNN算法與OpenCL架構(gòu)

1.1KNN算法

KNN分類算法實(shí)現(xiàn)簡單，分類錯(cuò)誤率低，其實(shí)現(xiàn)通常分為三步：距離計(jì)算、距離排序、分類判決。

距離計(jì)算是計(jì)算待分類數(shù)據(jù)和參考數(shù)據(jù)集數(shù)據(jù)之間的距離，本文采用的是歐式距離。

算出待分類數(shù)據(jù)與每個(gè)參考數(shù)據(jù)集樣本之間的距離之后，需選出其中最小的K個(gè)距離，作為判決的標(biāo)準(zhǔn)。針對如何從多個(gè)數(shù)據(jù)中選取K個(gè)最小的數(shù)據(jù)，提出了一種新的并行冒泡排序方法，該方法無冗余計(jì)算且可并行實(shí)現(xiàn)。并行冒泡排序也曾被提出來加速排序的計(jì)算速度，如奇偶冒泡排序[9]，但該算法由于大量冗余計(jì)算，實(shí)現(xiàn)時(shí)性能不佳。本文提出的并行冒泡排序只需要K個(gè)氣泡來選取K個(gè)最小的數(shù)據(jù)，如圖1所示。

圖1　并行冒泡

1.2OpenCL架構(gòu)

OpenCL程序在主機(jī)和設(shè)備上執(zhí)行，支持基于數(shù)據(jù)和基于任務(wù)的并行編程模型。圖2是有主機(jī)的多個(gè)設(shè)備組成的OpenCL平臺模型[10]。

圖2　OpenCL平臺模型

執(zhí)行內(nèi)核程序時(shí)，OpenCL將定義一個(gè)索引來執(zhí)行該內(nèi)核的實(shí)例，該實(shí)例就是OpenCL的工作項(xiàng)，每個(gè)工作項(xiàng)執(zhí)行的代碼相同。工作項(xiàng)的內(nèi)存稱作私有內(nèi)存。一些特定的工作項(xiàng)組成工作組，相同工作組共享局部內(nèi)存，相同工作組中的不同工作項(xiàng)在不同計(jì)算單元上并行運(yùn)行。

本文采用通用圖形處理器（GPGPU）來作為異構(gòu)系統(tǒng)的計(jì)算設(shè)備，由于GPU擁有大量的計(jì)算核心，其浮點(diǎn)計(jì)算效率遠(yuǎn)高于CPU，所以GPU作為OpenCL的通用計(jì)算設(shè)備擁有很高的計(jì)算效率。

2　并行冒泡的KNN算法實(shí)現(xiàn)

2.1距離計(jì)算內(nèi)核

距離計(jì)算內(nèi)核計(jì)算每個(gè)待分類數(shù)據(jù)到每個(gè)參考數(shù)據(jù)集樣本之間的距離，每次距離計(jì)算由一個(gè)工作項(xiàng)完成。數(shù)據(jù)集由CPU傳輸?shù)紾PU的全局內(nèi)存，相應(yīng)工作組的數(shù)據(jù)由GPU全局內(nèi)存?zhèn)鬏數(shù)紾PU局部內(nèi)存，以此充分利用局部內(nèi)存的帶寬，提高GPU計(jì)算核心的數(shù)據(jù)訪存速度。距離計(jì)算如圖3所示。

2.2距離分組排序內(nèi)核

為了充分利用GPU的計(jì)算資源，提高計(jì)算的并行度，將得到的待分類數(shù)據(jù)和參考數(shù)據(jù)集的所有距離進(jìn)行排序時(shí)，先將距離分組，若分組數(shù)為N，通過并行冒泡選取每組數(shù)據(jù)最小的K個(gè)距離，得到N×K個(gè)距離。一個(gè)待分類數(shù)據(jù)共有N個(gè)工作組進(jìn)行分組排序。

圖3　距離計(jì)算內(nèi)核

每個(gè)工作組通過并行冒泡進(jìn)行排序，一個(gè)工作組擁有K個(gè)工作項(xiàng)，每個(gè)工作項(xiàng)對比相鄰的兩個(gè)數(shù)據(jù)，K個(gè)工作項(xiàng)從數(shù)據(jù)的起始端一直對比到數(shù)據(jù)的末端，從而選出最小的K個(gè)距離。第1個(gè)周期時(shí)，共一個(gè)工作項(xiàng)進(jìn)行第1個(gè)和第2個(gè)距離進(jìn)行比較；第2個(gè)周期時(shí)，第1個(gè)氣泡比較第3個(gè)和第4個(gè)距離，第2個(gè)數(shù)據(jù)比較第1個(gè)和第2個(gè)距離，直到N個(gè)工作項(xiàng)產(chǎn)生N個(gè)氣泡。氣泡數(shù)目穩(wěn)定后，經(jīng)過若干個(gè)周期，K個(gè)氣泡便可以同時(shí)攜帶K個(gè)最小的距離。所以該過程共有2個(gè)過程，氣泡增加，氣泡穩(wěn)定。具體過程如圖4、圖5所示。

圖4　氣泡增加階段

圖5　氣泡穩(wěn)定階段

2.3距離計(jì)算內(nèi)核

在分組內(nèi)核中，每個(gè)待分類數(shù)據(jù)共得到M×K個(gè)距離，該內(nèi)核就是從這M×K個(gè)數(shù)據(jù)中選出K個(gè)最小的數(shù)據(jù)。由于參考數(shù)據(jù)集很大，這個(gè)內(nèi)核消耗的計(jì)算時(shí)間相比分組排序只占小部分。

3　結(jié)果分析

3.1算法性能分析

為了讓距離分組內(nèi)核得到合理的分組數(shù)目，通過設(shè)置不同的分組數(shù)目，得到在GPU上計(jì)算消耗的時(shí)間。實(shí)驗(yàn)中，采用英特爾處理器 i7-3770K作為 OpenCL主機(jī)，AMD Radeon HD7950作為OpenCL設(shè)備。該CPU是4核處理器，主頻3.5 GHz，24 GB內(nèi)存。該GPU擁有28個(gè)計(jì)算單元，最大工作頻率為900 MHz，3 GB GDDR5內(nèi)存，內(nèi)存帶寬為240 GB/s。所有實(shí)驗(yàn)數(shù)據(jù)由MATLAB產(chǎn)生，參考數(shù)據(jù)集為 10 240×8個(gè)浮點(diǎn)數(shù)據(jù)，每個(gè)數(shù)據(jù)共 64維，K為16，待分類數(shù)據(jù)個(gè)數(shù)為32。

為了找到每個(gè)待分類數(shù)據(jù)距離的最佳分組數(shù)，將每個(gè)待分類數(shù)據(jù) 10 240×8個(gè)參考數(shù)據(jù)集的距離進(jìn)行分組，將分組數(shù)分別設(shè)置為 4×8，8×8，直至48×8。通過實(shí)驗(yàn)，記錄每次實(shí)驗(yàn)的GPU時(shí)間消耗，如圖6所示。

圖6　不同分組的內(nèi)核計(jì)算時(shí)間

當(dāng)分組數(shù)較小時(shí)，分組排序內(nèi)核隨著分組數(shù)的變大，時(shí)間消耗迅速下降；當(dāng)分組數(shù)變大后，時(shí)間消耗趨于穩(wěn)定。因?yàn)楫?dāng)分組數(shù)較小時(shí)，每個(gè)工作項(xiàng)的計(jì)算量和數(shù)據(jù)傳輸量過大，且GPU的計(jì)算資源沒有充分利用；當(dāng)分組數(shù)變大后，GPU計(jì)算資源得到充分利用，但工作組和工作項(xiàng)的數(shù)目也會(huì)隨之變大，從而導(dǎo)致額外的控制開銷。根據(jù)實(shí)驗(yàn)數(shù)據(jù)，將分組數(shù)設(shè)定為32。

本次實(shí)驗(yàn)，把CUKNN和PBKNN進(jìn)行OpenCL實(shí)現(xiàn)時(shí)，工作組大小均設(shè)置為256。CUKNN進(jìn)行排序時(shí)，每個(gè)工作組將浪費(fèi)(256-K)/256×100%的時(shí)間計(jì)算無關(guān)數(shù)據(jù)的排序。而PBKNN對此進(jìn)行優(yōu)化，避免了無關(guān)數(shù)據(jù)的排序。所以，理論上來說，PBKNN的時(shí)間消耗是CUKNN的K/256。

3.2實(shí)驗(yàn)驗(yàn)證

PBKNN和CUKNN采用相同的數(shù)據(jù)和相同的實(shí)驗(yàn)環(huán)境。參考數(shù)據(jù)集中數(shù)據(jù)點(diǎn)個(gè)數(shù)從1×10 240到64×10 240變化，如表1。對于PBKNN，共有256個(gè)工作組，每個(gè)工作組共有64個(gè)工作項(xiàng)；對于CUKNN，工作組數(shù)目分別設(shè)置為40，80，120，…，320，其每個(gè)工作組的工作項(xiàng)數(shù)目最大時(shí)，性能最好。所以每個(gè)工作組的工作項(xiàng)的數(shù)目設(shè)置為256。

BPKNN和CUKNN均通過三個(gè)內(nèi)核實(shí)現(xiàn)KNN算法。由于第一個(gè)和第三個(gè)內(nèi)核的時(shí)間消耗較少，主要對比第二個(gè)內(nèi)核的時(shí)間消耗。實(shí)驗(yàn)結(jié)果如表1。

表1　CUKNN和PBKNN時(shí)間消耗對比

從實(shí)驗(yàn)結(jié)果可以看出，在相同的實(shí)現(xiàn)平臺上通過減少無關(guān)數(shù)據(jù)的排序，PBKNN相比于CUKNN計(jì)算時(shí)間大幅減少，因而對應(yīng)的能量效率也得到了很大的提升。

4　結(jié)論

本文提出了一種基于CPU+GPU的異構(gòu)計(jì)算架構(gòu)的并行冒泡KNN算法—PBKNN算法，該算法充分利用了GPU的并行計(jì)算能力及 OpenCL的編程優(yōu)化。通過在AMD Radeon HD GPU實(shí)測，PBKNN在關(guān)鍵排序時(shí)間僅為CUKNN的1/16，因而極大地提升了處理速度和計(jì)算能效。

[1]Khronos group.The open standard for parallel programming of heterogeneous systems[EB/OL].http://www.khronos.org/opencl/.

[2]PENG Y，KOU G，SHI Y，et al.A descriptive framework for the field of data mining and knowledge discovery[J].Int. J.Inf.Technol.Decis.Mak.，2008，7(4)：639-682.

[3]ZHANG H，BERG A C，MAIRE M，et al.SVM-KNN：discriminative nearest neighbor classification for visual category recognition[C].In International Conference on Computer Vision and Pattern Recognition，New York(NY)，USA，2006.

[4]GARCIA V，DEBREUVE E，BARLAUD M.Fast k nearest neighbor search using GPU[C].In：IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops(CVPRW′08)，2008：1-6.

[5]LIANG S，WANG C，LIU Y，et al.CUKNN：a parallel implementation of knearest neighbor on cuda enabled GPU[C]. In：IEEE Youth Conference on Information，Computing and Telecommunication(YC-ICT′09)，2009：415-418.

[6]HOFFMANN J，EI-LAITHY K，GüTTLER F，et al.Simulating biological-inspired spiking neural networks with Open-CL[C].ICANN 2010，Part I，LNCS 6352，2010：184-187.

[7]CHE S，BOYER M，MENG J Y，et al.A performance study of general purpose applications on graphics processors[J]. Journal of Parallel and Distributed Computing，2008，68 (10)：137-1380.

[8]BALEVIC A，ROCKSTROH L，LI W，et al.Acceleration of a finite-difference time-domain method with general purpose GPUs(GPGPUs)[C].Proc.of International Conference on Computer and Information Technology，2008，1-2：291-294.

[9]PETERS H，SCHULZ-HILDEBRANDT O，LUTTENBERGER N. A novel sorting algorithm for many-core architectures based on adaptive bitonic sort[C].In：Parallel&Distributed Processing Symposium(IPDPS)，2012 IEEE 26th International，2012.

[10]GROUP K O W.The opencl specification[EB/OL].(2011) [2015].http://www.khronos.org/registry/cl/specs/opencl-1.1.pdf.

A energy efficient parallel KNN algorithm evaluated on GPU using OpenCL

He Jiang1，Pu Yuliang1，Li Haibo2，Yan Bo1
(1.University of Electronic Science and Technology of China，Chengdu 610036，China；2.Guangdong Provincial Public Security Bureau，Guangzhou510050，China)

Recently,data classification techniques have been used to solve many problems.As one of the most popular classification algorithms,K-Nearest Neighbor(KNN)algorithm has been widely used.Over the past 50 years,many efforts about parallel computing have been made to improve the efficiency of KNN.A new CUDA-based parallel implementation of KNN algorithm called CUKNN has proved that the parallel solution implemented by GPU is dozens of times faster than the serial solution implemented by CPU.However,plenty of redundant computation has been done in CUKNN.This paper proposes a new parallel solution of KNN algorithm which is implemented by parallel bubble sort.Then we evaluate it on GPU-based heterogeneous computing system using OpenCL,and the result shows that the efficiency of our solution has improved 16 times.

KNN；GPGPU；OpenCL；bubble sort；parallel computing

TP311

A

10.16157/j.issn.0258-7998.2016.02.003

2015-12-29)

賀江（1991-），男，碩士研究生，主要研究方向：智能信息處理、異構(gòu)計(jì)算。

蒲宇亮（1991-），男，碩士研究生，主要研究方向：圖像數(shù)據(jù)處理與圖像識別、異構(gòu)計(jì)算。

李海波（1975-），男，碩士研究生，高級工程師（副高），主要研究方向：大數(shù)據(jù)應(yīng)用、圖像與視頻內(nèi)容識別。

中文引用格式：賀江，蒲宇亮，李海波，等.一種基于 OpenCL的高能效并行 KNN算法及其 GPU驗(yàn)證[J].電子技術(shù)應(yīng)用，2016，42(2)：14-16.

英文引用格式：He Jiang，Pu Yuliang，Li Haibo，et al.A energy efficient parallel KNN algorithm evaluated on GPU using Open-CL[J].Application of Electronic Technique，2016，42(2)：14-16.