基于OpenCL的并行kNN算法设计与实现

计算机工程与科学

基于OpenCL的并行kNN算法设计与实现

杨朋霖，冯百明，周志阳，温向慧

（西北师范大学计算机科学与工程学院,甘肃兰州 730070）

收稿日期:2016-05-05 修回日期:2016-09-28 出版日期:2017-12-25 发布日期:2017-12-25
基金资助:
国家自然科学基金（61462076）

A parallel kNN algorithm based on OpenCL

YANG Peng-lin,FENG Bai-ming,ZHOU Zhi-yang,WEN Xiang-hui

（College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China）

Received:2016-05-05 Revised:2016-09-28 Online:2017-12-25 Published:2017-12-25

摘要/Abstract

摘要：

kNN算法是机器学习和数据挖掘程序中经常使用的经典算法。随着数据量的增大，kNN算法的执行时间急剧上升。为了有效利用现代计算机的GPU等计算单元减少kNN算法的计算时间，提出了一种基于OpenCL的并行kNN算法，该算法对距离计算和排序两个瓶颈点进行并行化，在距离计算阶段使用细粒度并行化策略和优化的线程模型，排序阶段使用优化内存模型的双调排序。以UCI数据集letter为测试集，分别使用E8400和GTS450运行kNN算法进行测试，采用GPU加速的并行kNN算法的计算速度比CPU版提高了40.79倍。

关键词: OpenCL, GPU, kNN, 双调排序

Abstract:

The kNN algorithm is a classical algorithm often used in machine learning and data mining programs. With the increasing amount of data, the execution time of the kNN algorithm increases sharply. In order to effectively utilize GPU and other computing units of modern computers to reduce the computation time of the kNN algorithm, we present a parallel kNN algorithm based on OpenCL, which parallelizes the two segments of bottleneck code: distance calculation and sorting. The algorithm adopts the fine-grained parallelization strategy and the optimized memory model in the phase of distance calculation and uses bitonic sort that can optimize memory model in the phase of sorting. We use Letter, one of UCI datasets, as the test set and E8400 AND GTS450 to run the kNN algorithm for testing. The computing speed of the parallel kNN algorithm accelerated by GPU is 40.79 times faster than that of its CPU version.

Key words: OpenCL, GPU, kNN, bitonic sort

杨朋霖，冯百明，周志阳，温向慧. 基于OpenCL的并行kNN算法设计与实现[J]. 计算机工程与科学.

YANG Peng-lin,FENG Bai-ming,ZHOU Zhi-yang,WEN Xiang-hui. A parallel kNN algorithm based on OpenCL[J]. Computer Engineering & Science.

[1]	王宇华, 何俊飞, 张宇琪, 徐悦竹, 崔环宇. DRM:基于迭代归并策略的GPU并行SpMV存储格式[J]. 计算机工程与科学, 2024, 46(03): 381-394.
[2]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[3]	朱浩, 周博洋, 卢雪山, 杜溢墨. OpenCL计算软件栈评估[J]. 计算机工程与科学, 2021, 43(12): 2105-2114.
[4]	孙宝贵, 车文刚, 廖江福, . 一种改进的KNN案例推理检索算法[J]. 计算机工程与科学, 2021, 43(12): 2263-2271.
[5]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[6]	龚昊, 刘莹, 冯建周, 赵仁良, 冷佳旭, . 基于GPU加速的脉冲多普勒雷达信号处理[J]. 计算机工程与科学, 2021, 43(07): 1141-1149.
[7]	孙兆鹏, 周宽久. 基于PCIe的高性能FPGA-GPU-CPU异构编程架构[J]. 计算机工程与科学, 2021, 43(04): 641-651.
[8]	魏金晖, 李晨, 鲁建壮. 多GPU系统虚实地址转换架构研究[J]. 计算机工程与科学, 2021, 43(02): 228-234.
[9]	张亮, 常旭, 秦志楷, 沈立. 量子线路模拟器QuEST在多GPU平台上的性能优化[J]. 计算机工程与科学, 2021, 43(01): 17-23.
[10]	杨岚雁, 靳敏, 张迎春, 张珣. 一种基于关联规则的MLKNN多标签分类算法[J]. 计算机工程与科学, 2020, 42(07): 1309-1317.
[11]	李荣春，周鑫，潘衡岳，牛新，高蕾，窦勇. 基于GPU的并行Turbo乘积码译码器[J]. 计算机工程与科学, 2020, 42(05): 761-769.
[12]	徐频捷1,2，王诲喆1,2，李策3，唐丹1，赵地1. 基于脉冲神经网络与移动GPU计算的图像分类算法研究与实现[J]. 计算机工程与科学, 2020, 42(03): 397-403.
[13]	左宪禹1,2，张哲1,5，黄祥志4,5，葛强1,2，张理涛3，臧文乾4,5. 一种适用于GPU图像处理算法的合并存储结构[J]. 计算机工程与科学, 2020, 42(02): 197-202.
[14]	安婷玉1，郭宝宝2. 基于国产软硬件的OpenCL计算平台研究[J]. 计算机工程与科学, 2019, 41(11): 1919-1923.
[15]	沈立，杨耀华，王志英. 通过部分Warp重组消除GPGPU控制流的不一致性[J]. 计算机工程与科学, 2019, 41(08): 1335-1342.