《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 一種基于OpenCL的高能效并行KNN算法及其GPU驗證
一種基于OpenCL的高能效并行KNN算法及其GPU驗證
2016年電子技術應用第2期
賀 江1,蒲宇亮1,李海波2,閻 波1
1.電子科技大學,四川 成都610036;2.廣東省公安廳,廣東 廣州510050
摘要: 近年來數據分類技術已經被廣泛應用于各類問題中,作為最重要的分類算法之一,K最近鄰法(KNN)也被廣泛使用。在過去的近50年,人們就如何提高KNN的并行性能做出巨大努力。基于CUDA的KNN并行實現算法——CUKNN算法證明KNN在GPU上的并行實現比在CPU上串行實現的速度提升數十倍,然而,CUDA在實現過程中包含了大量的冗余計算。提出了一種并行冒泡的新型KNN并行算法,并通過OpenCL,在以GPU作為計算核心的異構系統上進行驗證,結果顯示提出的方法比CUDA快16倍。
中圖分類號: TP311
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.02.003
中文引用格式: 賀江,蒲宇亮,李海波,等. 一種基于OpenCL的高能效并行KNN算法及其GPU驗證[J].電子技術應用,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 引言

    近年來,許多不同類型的處理器廣泛應用于高性能計算領域,如GPU、FPGA、DSP等[1],而異構計算平臺由不同類型的處理器組成,能對許多不同的算法進行加速實現。OpenCL是一種開放式的異構計算標準,支持異構系統的并行程序應用。作為經典聚類算法,KNN在文字識別、預測分析、圖像處理和圖像識別等方面[2]有非常重要的應用。

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

    基于CPU+GPU的異構計算系統最近幾年在算法加速方面得到了廣泛使用,如神經網絡[6]、數據挖掘[7]等。而基于CPU+FPGA系統由于其能效優勢[8],得到業界的認可。

    本文提出了一種基于CPU+GPU異構計算系統的KNN并行算法。該方法將待分類的數據集通過并行冒泡的方法進行分類,稱該方法為PBKNN(parallel sort)。

1 KNN算法與OpenCL架構

1.1 KNN算法

    KNN分類算法實現簡單,分類錯誤率低,其實現通常分為三步:距離計算、距離排序、分類判決。

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

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

gnx3-t1.gif

1.2 OpenCL架構

    OpenCL程序在主機和設備上執行,支持基于數據和基于任務的并行編程模型。圖2是有主機的多個設備組成的OpenCL平臺模型[10]

gnx3-t2.gif

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

    本文采用通用圖形處理器(GPGPU)來作為異構系統的計算設備,由于GPU擁有大量的計算核心,其浮點計算效率遠高于CPU,所以GPU作為OpenCL的通用計算設備擁有很高的計算效率。

2 并行冒泡的KNN算法實現

2.1 距離計算內核

    距離計算內核計算每個待分類數據到每個參考數據集樣本之間的距離,每次距離計算由一個工作項完成。數據集由CPU傳輸到GPU的全局內存,相應工作組的數據由GPU全局內存傳輸到GPU局部內存,以此充分利用局部內存的帶寬,提高GPU計算核心的數據訪存速度。距離計算如圖3所示。

gnx3-t3.gif

2.2 距離分組排序內核

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

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

gnx3-t4.gif

gnx3-t5.gif

2.3 距離計算內核

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

3 結果分析

3.1 算法性能分析

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

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

gnx3-t6.gif

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

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

3.2 實驗驗證

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

    BPKNN和CUKNN均通過三個內核實現KNN算法。由于第一個和第三個內核的時間消耗較少,主要對比第二個內核的時間消耗。實驗結果如表1。

gnx3-b1.gif

    從實驗結果可以看出,在相同的實現平臺上通過減少無關數據的排序,PBKNN相比于CUKNN計算時間大幅減少,因而對應的能量效率也得到了很大的提升。

4 結論

    本文提出了一種基于CPU+GPU的異構計算架構的并行冒泡KNN算法—PBKNN算法,該算法充分利用了GPU的并行計算能力及OpenCL的編程優化。通過在AMD Radeon HD GPU實測,PBKNN在關鍵排序時間僅為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.

此內容為AET網站原創,未經授權禁止轉載。
亚洲一区二区欧美_亚洲丝袜一区_99re亚洲国产精品_日韩亚洲一区二区
亚洲一卡久久| 亚洲二区在线| 国内精品99| 国产精品免费一区豆花| 亚洲综合精品自拍| 日韩午夜免费| 91久久香蕉国产日韩欧美9色| 亚洲一区二区三区久久| 亚洲国产精品专区久久| 国产在线精品二区| 国产婷婷色一区二区三区| 欧美在线免费一级片| 一本色道久久| 亚洲三级免费电影| 久久精品国产77777蜜臀| 亚洲综合二区| 亚洲午夜国产一区99re久久 | 国产精品高清免费在线观看| 欧美电影美腿模特1979在线看| 久久久夜夜夜| 久久精品亚洲一区二区三区浴池| 亚洲欧美日韩一区二区三区在线| 一区二区三区四区五区在线 | 欧美一区影院| 亚洲欧美偷拍卡通变态| 一本色道88久久加勒比精品 | 久久精品一区二区三区中文字幕| 午夜在线视频一区二区区别| 在线天堂一区av电影| 亚洲美女av在线播放| 亚洲精品老司机| 亚洲精品久久久久久下一站| 亚洲激情视频网| 亚洲福利久久| 亚洲国产精品va在看黑人| 亚洲盗摄视频| 亚洲激情不卡| 亚洲精品美女久久久久| 亚洲日本免费| 亚洲人妖在线| 99天天综合性| 99亚洲伊人久久精品影院红桃| 亚洲免费成人| 宅男在线国产精品| 亚洲综合色网站| 欧美一级艳片视频免费观看| 欧美怡红院视频| 亚洲第一天堂无码专区| 亚洲国产精品成人精品| 亚洲精品久久嫩草网站秘色 | 久久国产精彩视频| 午夜精品久久久久久99热| 欧美一区二区女人| 久久久久综合网| 玖玖玖免费嫩草在线影院一区| 久久性色av| 欧美激情欧美狂野欧美精品| 欧美激情亚洲激情| 欧美日韩亚洲91| 国产精品欧美久久| 国产一区日韩欧美| 亚洲人成网站影音先锋播放| 日韩亚洲国产精品| 亚洲女与黑人做爰| 亚洲电影免费观看高清完整版在线观看| 亚洲第一搞黄网站| 日韩性生活视频| 亚洲一区二区三| 久久精品视频播放| 欧美成人精品在线视频| 欧美日韩国产成人| 国产欧美欧美| 尤物九九久久国产精品的特点| 亚洲三级免费电影| 亚洲欧美日韩高清| 亚洲国产精品久久人人爱蜜臀| 日韩亚洲欧美一区| 亚洲欧美日韩国产综合在线| 久久九九国产| 欧美精品在线一区| 国产精品综合色区在线观看| 精品成人国产在线观看男人呻吟| 亚洲精品一区二区三区樱花| 亚洲伊人网站| 亚洲三级影院| 午夜精品久久久久影视 | 欧美视频在线不卡| 国内自拍视频一区二区三区| 日韩午夜电影av| 久久国产福利| 亚洲一区二区三区精品在线| 久久色在线播放| 欧美色视频一区| 黑人巨大精品欧美黑白配亚洲| 99国产一区| 亚洲国产导航| 欧美一区2区三区4区公司二百| 欧美黑人国产人伦爽爽爽| 国产精品视频久久| 亚洲激情另类| 欧美专区福利在线| 亚洲免费在线精品一区| 欧美岛国在线观看| 国产亚洲激情| 在线一区二区日韩| 亚洲精品一区二区三| 欧美一区二区在线| 欧美日韩视频在线一区二区| 精品二区久久| 亚洲欧美日韩一区在线观看| 夜夜精品视频| 欧美二区视频| 国产一区二区三区在线免费观看| av成人免费在线观看| 亚洲国产美女| 久久久av毛片精品| 国产精品区免费视频| 亚洲精品日本| 亚洲青涩在线| 久热这里只精品99re8久| 国产麻豆9l精品三级站| 一区二区三区日韩在线观看 | 久久久久久一区二区三区| 国产精品久久毛片a| 亚洲精品免费在线观看| 亚洲电影第三页| 久久国产手机看片| 国产精品一区二区黑丝| 一区二区三区你懂的| 一区二区三区精品视频在线观看 | 麻豆亚洲精品| 国产在线观看91精品一区| 亚洲欧美日本国产有色| 亚洲一区二区在线播放| 欧美日韩国产不卡| 亚洲美女毛片| 一道本一区二区| 六月丁香综合| 影音先锋国产精品| 久久精品久久99精品久久| 久久国产一区| 国产一区欧美| 久久精品国产在热久久| 久久精品国产一区二区电影| 欧美日韩一区二| 一二三四社区欧美黄| 一区二区三区日韩精品视频| 欧美日韩精选| 99国产精品99久久久久久粉嫩| 9久草视频在线视频精品| 欧美激情视频在线播放| 亚洲国产精品一区制服丝袜 | 91久久极品少妇xxxxⅹ软件| 亚洲欧洲日韩综合二区| 免费精品视频| 亚洲第一久久影院| 亚洲精品视频在线观看免费| 欧美黄免费看| 日韩亚洲欧美精品| 亚洲欧美日韩国产综合精品二区| 国产精品av一区二区| 亚洲线精品一区二区三区八戒| 亚洲欧美日韩精品久久奇米色影视| 国产精品乱码久久久久久| 亚洲永久在线| 久久精视频免费在线久久完整在线看| 国内精品久久久久久久影视麻豆 | 欧美在线亚洲| 欧美xxx在线观看| 亚洲人成久久| 亚洲一区二区在线| 国产日韩一区二区三区| 久久精品久久99精品久久| 美女福利精品视频| 日韩午夜中文字幕| 午夜精品免费在线| 欧美精品一区二区三区视频| 亚洲国产精品久久久久久女王| 亚洲理论在线观看| 国产精品v欧美精品v日本精品动漫| 在线看不卡av| 中文国产亚洲喷潮| 国产欧美在线视频| 亚洲激情成人网| 欧美日韩国内自拍| 午夜久久tv| 欧美成人国产| 亚洲神马久久| 久久婷婷成人综合色| 91久久精品国产91久久性色tv| 亚洲一级网站| 国产视频一区二区在线观看| 亚洲级视频在线观看免费1级| 欧美日韩中文在线| 欧美一区免费| 欧美片在线观看| 亚久久调教视频| 美女免费视频一区| 在线视频一区二区| 免费看av成人|