基于GPU的K-近邻算法实现

摘要：

K-近邻计算在数据集规模较大时计算复杂度较高,因此,利用图形处理器( GPU )强大的并行计算能力对K-近邻算法进行加速。在分析现有K-近邻算法的基础上,针对该算法时间开销过大的问题,结合GPU的体系结构特征实现基于GPU的K-近邻算法。利用全局存储器的合并访问特性,提高GPU全局存储器访问数据的效率,通过事先过滤数据的方法来减少参与排序的数据量,进而减少排序阶段的线程串行化时间。在 KDD, Poker, Covertype 3个数据集上进行实验,结果表明,该实现方法在距离计算阶段每秒执行的浮点运算次数为266.37×109次,而排序阶段为26.47×109次,优于已有方法。

关键词：K-近邻问题、图形处理器、并行计算、算法加速、合并访问、全局存储器

分类号：TP311(计算技术、计算机技术)

在线出版日期：2015-03-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：189-192,198