一种基于OpenCL的高能效并行KNN算法及其GPU验证  

A energy efficient parallel KNN algorithm evaluated on GPU using OpenCL

作　　者：贺江[1] 蒲宇亮 李海波[2] 阎波[1] 

机构地区：[1]电子科技大学,四川成都610036 [2]广东省公安厅,广东广州510050

出　　处：《电子技术应用》2016年第2期14-16,共3页Application of Electronic Technique

摘　　要：近年来数据分类技术已经被广泛应用于各类问题中,作为最重要的分类算法之一,K最近邻法(KNN)也被广泛使用。在过去的近50年,人们就如何提高KNN的并行性能做出巨大努力。基于CUDA的KNN并行实现算法——CUKNN算法证明KNN在GPU上的并行实现比在CPU上串行实现的速度提升数十倍,然而,CUDA在实现过程中包含了大量的冗余计算。提出了一种并行冒泡的新型KNN并行算法,并通过OpenCL,在以GPU作为计算核心的异构系统上进行验证,结果显示提出的方法比CUDA快16倍。Recently, data classification techniques have been used to solve many problems. As one of the most popular classifica-tion 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.

关 键 词：KNN GPGPU OPENCL 并行冒泡 并行计算 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]