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

关键词：opencl gpu knn 双调排序 

单位：西北师范大学计算机科学与工程学院; 甘肃兰州730070