0 引言

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

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

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

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

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

1.1 KNN算法

    KNN分類算法實(shí)現(xiàn)簡(jiǎ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)。針對(duì)如何從多個(gè)數(shù)據(jù)中選取K個(gè)最小的數(shù)據(jù)，提出了一種新的并行冒泡排序方法，該方法無(wú)冗余計(jì)算且可并行實(shí)現(xiàn)。并行冒泡排序也曾被提出來(lái)加速排序的計(jì)算速度，如奇偶冒泡排序^[9]，但該算法由于大量冗余計(jì)算，實(shí)現(xiàn)時(shí)性能不佳。本文提出的并行冒泡排序只需要K個(gè)氣泡來(lái)選取K個(gè)最小的數(shù)據(jù)，如圖1所示。

1.2 OpenCL架構(gòu)

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

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

    本文采用通用圖形處理器（GPGPU）來(lái)作為異構(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局部?jī)?nèi)存，以此充分利用局部?jī)?nèi)存的帶寬，提高GPU計(jì)算核心的數(shù)據(jù)訪存速度。距離計(jì)算如圖3所示。

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

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

    每個(gè)工作組通過(guò)并行冒泡進(jìn)行排序，一個(gè)工作組擁有K個(gè)工作項(xiàng)，每個(gè)工作項(xiàng)對(duì)比相鄰的兩個(gè)數(shù)據(jù)，K個(gè)工作項(xiàng)從數(shù)據(jù)的起始端一直對(duì)比到數(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)過(guò)若干個(gè)周期，K個(gè)氣泡便可以同時(shí)攜帶K個(gè)最小的距離。所以該過(guò)程共有2個(gè)過(guò)程，氣泡增加，氣泡穩(wěn)定。具體過(guò)程如圖4、圖5所示。

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ù)目，通過(guò)設(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。通過(guò)實(shí)驗(yàn)，記錄每次實(shí)驗(yàn)的GPU時(shí)間消耗，如圖6所示。

    當(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ù)傳輸量過(guò)大，且GPU的計(jì)算資源沒(méi)有充分利用；當(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ì)算無(wú)關(guān)數(shù)據(jù)的排序。而PBKNN對(duì)此進(jìn)行優(yōu)化，避免了無(wú)關(guān)數(shù)據(jù)的排序。所以，理論上來(lái)說(shuō)，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。對(duì)于PBKNN，共有256個(gè)工作組，每個(gè)工作組共有64個(gè)工作項(xiàng)；對(duì)于CUKNN，工作組數(shù)目分別設(shè)置為40，80，120，…，320，其每個(gè)工作組的工作項(xiàng)數(shù)目最大時(shí)，性能最好。所以每個(gè)工作組的工作項(xiàng)的數(shù)目設(shè)置為256。

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

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

4 結(jié)論

    本文提出了一種基于CPU+GPU的異構(gòu)計(jì)算架構(gòu)的并行冒泡KNN算法—PBKNN算法，該算法充分利用了GPU的并行計(jì)算能力及OpenCL的編程優(yōu)化。通過(guò)在AMD Radeon HD GPU實(shí)測(cè)，PBKNN在關(guān)鍵排序時(shí)間僅為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.