《電子技術應用》
您所在的位置:首頁 > 可編程邏輯 > 設計應用 > 一種基于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亚洲国产精品_日韩亚洲一区二区
国产精品久久久久久久浪潮网站 | 噜噜噜躁狠狠躁狠狠精品视频| 夜夜嗨av一区二区三区网站四季av| 亚洲第一二三四五区| 亚洲在线中文字幕| 99re6这里只有精品视频在线观看| 伊甸园精品99久久久久久| 国产午夜精品全部视频在线播放| 国产精品普通话对白| 欧美日韩中文精品| 欧美日韩国产色视频| 欧美精品久久久久久久久久| 欧美激情导航| 欧美成人精品影院| 欧美成熟视频| 欧美激情综合在线| 欧美精品在线观看一区二区| 欧美精品国产| 欧美日韩一区二区高清| 欧美日韩亚洲精品内裤| 欧美日韩亚洲综合一区| 欧美色网一区二区| 国产精品狠色婷| 国产精品一区二区三区久久久| 国产精品入口尤物| 国产欧美亚洲一区| 国内精品久久久久久久97牛牛| 国产一区二区| 在线日韩中文字幕| 亚洲精品四区| 这里只有精品视频| 亚洲欧美日韩一区二区在线| 小辣椒精品导航| 久久国产精品久久久久久| 亚洲国产精品嫩草影院| 亚洲人成高清| 一区二区三区毛片| 亚洲一区在线免费观看| 亚洲欧美日韩天堂| 久久久久久亚洲精品杨幂换脸 | 国产深夜精品福利| 激情综合久久| 亚洲精品一区二区网址| 亚洲天堂偷拍| 性久久久久久久久久久久| 亚洲高清av| 夜夜爽av福利精品导航| 亚洲欧美日韩国产成人| 久久精品视频免费播放| 久久资源在线| 欧美日韩色婷婷| 国产日韩欧美高清免费| 亚洲成色999久久网站| 夜夜躁日日躁狠狠久久88av| 羞羞视频在线观看欧美| 亚洲精选一区二区| 亚洲欧美日韩精品久久久| 久久久九九九九| 欧美日本不卡高清| 国产精品亚洲网站| 亚洲国产一区二区三区青草影视| av成人毛片| 久久精品视频在线| 亚洲一区二区三区在线| 久久久人成影片一区二区三区| 欧美黄色aa电影| 国产精品免费在线| 亚洲福利一区| 亚洲欧美另类国产| 日韩视频不卡中文| 久久爱另类一区二区小说| 欧美精品亚洲| 国产亚洲日本欧美韩国| 亚洲精品综合在线| 欧美一区日韩一区| 亚洲一二三区视频在线观看| 久久婷婷亚洲| 国产精品美女久久久| 亚洲国产成人久久综合| 亚洲国产日韩欧美综合久久| 亚洲欧美日本另类| 日韩午夜电影av| 久久久99久久精品女同性| 国产精品xxxxx| 亚洲国产精品悠悠久久琪琪| 亚洲欧美日韩精品久久久| 99精品欧美| 免费精品视频| 国产在线乱码一区二区三区| 亚洲色无码播放| 99www免费人成精品| 久久综合电影| 国产人妖伪娘一区91| 在线亚洲欧美| 在线亚洲成人| 欧美大片一区二区| 尤物在线观看一区| 欧美中文字幕在线观看| 香蕉av777xxx色综合一区| 欧美日韩亚洲天堂| 亚洲激情视频| 亚洲欧美网站| 亚洲中字黄色| 欧美偷拍另类| 99亚洲一区二区| 日韩亚洲欧美综合| 欧美成人精品h版在线观看| 国产综合久久| 久久aⅴ乱码一区二区三区| 欧美有码在线视频| 欧美激情成人在线视频| 亚洲高清在线| 最新日韩精品| 欧美+亚洲+精品+三区| 亚洲高清毛片| 日韩视频不卡| 欧美日韩国产精品成人| 亚洲人在线视频| 日韩午夜电影在线观看| 欧美精品一区二| 亚洲美女黄色| 亚洲一区区二区| 国产精品成人免费| 一区二区欧美在线观看| 亚洲永久免费视频| 国产精品日韩电影| 亚洲制服av| 久久精品99国产精品| 国产婷婷97碰碰久久人人蜜臀| 午夜精彩国产免费不卡不顿大片| 午夜亚洲福利| 国产欧美一区二区三区久久人妖 | 欧美日韩在线直播| 夜夜嗨一区二区三区| 亚洲资源av| 国产精品视频网址| 欧美一级久久久| 蜜桃av噜噜一区二区三区| 亚洲国产精品视频一区| 一本色道久久综合一区| 国产精品久久久久久久7电影 | 一区二区三区视频在线观看| 亚洲一区二区三区三| 国产精品亚洲综合久久| 亚洲专区一区二区三区| 久久婷婷成人综合色| 亚洲国产精品免费| 亚洲网站视频| 国产一级揄自揄精品视频| 亚洲欧洲视频在线| 欧美福利电影网| 中文高清一区| 久久国产精品99久久久久久老狼| 精品99一区二区| 一本色道久久88综合亚洲精品ⅰ| 欧美午夜影院| 欧美一级专区| 免费成人高清视频| 一区二区三区|亚洲午夜| 香蕉精品999视频一区二区| 国产亚洲一区在线| 亚洲乱码国产乱码精品精| 国产精品盗摄久久久| 欧美一区亚洲| 老司机精品久久| 一区二区三区av| 久久精品国产91精品亚洲| 国产偷国产偷亚洲高清97cao | 久久久综合网| 亚洲激情一区二区| 午夜日本精品| 狠狠色综合色区| 日韩特黄影片| 国产精品久久国产精麻豆99网站| 欧美在线亚洲综合一区| 欧美激情在线播放| 中文欧美在线视频| 久久九九国产| 一本大道久久精品懂色aⅴ| 欧美一区二区三区免费在线看| 国外成人性视频| 99视频一区二区| 国产日韩欧美成人| 日韩视频二区| 国产欧美精品在线| 亚洲麻豆国产自偷在线| 国产精品久久久久久久午夜片| 欧美影院午夜播放| 欧美粗暴jizz性欧美20| 亚洲一区二区三区视频播放| 久久久久在线| …久久精品99久久香蕉国产| 亚洲欧美影院| 亚洲国产精品一区在线观看不卡 | 黄色精品免费| 亚洲自啪免费| 在线成人av.com| 亚洲一区二区精品在线| 国产欧美精品一区| 亚洲自拍都市欧美小说|