0 引言

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

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

    基于CPU+GPU的異構(gòu)計算系統(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)計算系統(tǒng)的KNN并行算法。該方法將待分類的數(shù)據(jù)集通過并行冒泡的方法進行分類,，稱該方法為PBKNN（parallel sort）,。

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

1.1 KNN算法

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

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

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

1.2 OpenCL架構(gòu)

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果分析

3.1 算法性能分析

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

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

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

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

3.2 實驗驗證

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

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

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

4 結(jié)論

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

參考文獻

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