《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 一種基于OpenCL的高能效并行KNN算法及其GPU驗(yàn)證
一種基于OpenCL的高能效并行KNN算法及其GPU驗(yàn)證
2016年電子技術(shù)應(yīng)用第2期
賀 江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倍。
中圖分類號： TP311
文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.2016.02.003
中文引用格式： 賀江，蒲宇亮，李海波，等. 一種基于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 OpenCL[J].Application of Electronic Technique，2016，42(2)：14-16.
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，Guangzhou 510050，China
Abstract： 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.
Key words : KNN；GPGPU；OpenCL；bubble sort；parallel computing

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ù)集時高度并化，然后對距離進(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.1 KNN算法

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

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

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

gnx3-t1.gif

1.2 OpenCL架構(gòu)

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

gnx3-t2.gif

    執(zhí)行內(nèi)核程序時，OpenCL將定義一個索引來執(zhí)行該內(nèi)核的實(shí)例，該實(shí)例就是OpenCL的工作項(xiàng)，每個工作項(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ì)算每個待分類數(shù)據(jù)到每個參考數(shù)據(jù)集樣本之間的距離，每次距離計(jì)算由一個工作項(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所示。

gnx3-t3.gif

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

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

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

gnx3-t4.gif

gnx3-t5.gif

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

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

3 結(jié)果分析

3.1 算法性能分析

    為了讓距離分組內(nèi)核得到合理的分組數(shù)目，通過設(shè)置不同的分組數(shù)目，得到在GPU上計(jì)算消耗的時間。實(shí)驗(yàn)中，采用英特爾處理器i7-3770K作為OpenCL主機(jī)，AMD Radeon HD7950作為OpenCL設(shè)備。該CPU是4核處理器，主頻3.5 GHz，24 GB內(nèi)存。該GPU擁有28個計(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個浮點(diǎn)數(shù)據(jù)，每個數(shù)據(jù)共64維，K為16，待分類數(shù)據(jù)個數(shù)為32。

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

gnx3-t6.gif

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

    本次實(shí)驗(yàn)，把CUKNN和PBKNN進(jìn)行OpenCL實(shí)現(xiàn)時，工作組大小均設(shè)置為256。CUKNN進(jìn)行排序時，每個工作組將浪費(fèi)(256-K)/256×100%的時間計(jì)算無關(guān)數(shù)據(jù)的排序。而PBKNN對此進(jìn)行優(yōu)化，避免了無關(guān)數(shù)據(jù)的排序。所以，理論上來說，PBKNN的時間消耗是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)個數(shù)從1×10 240到64×10 240變化，如表1。對于PBKNN，共有256個工作組，每個工作組共有64個工作項(xiàng)；對于CUKNN，工作組數(shù)目分別設(shè)置為40，80，120，…，320，其每個工作組的工作項(xiàng)數(shù)目最大時，性能最好。所以每個工作組的工作項(xiàng)的數(shù)目設(shè)置為256。

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

gnx3-b1.gif

    從實(shí)驗(yàn)結(jié)果可以看出，在相同的實(shí)現(xiàn)平臺上通過減少無關(guān)數(shù)據(jù)的排序，PBKNN相比于CUKNN計(jì)算時間大幅減少，因而對應(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)鍵排序時間僅為CUKNN的1/16，因而極大地提升了處理速度和計(jì)算能效。

參考文獻(xiàn)

[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 OpenCL[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.

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。