Abstract:
K-nearest Neighbor(KNN) is a classical problem whose computational complexity increases rapidly with the
size of data set. It is an interesting research to accelerate KNN implementation on the Graphics Processor Unit(GPU) by employing GPU’s massive parallel computing power. For its heavy overhead on time,after analyzing the existing work of GPU-based KNN implementations and the architectural features of GPU,this paper efficiently parallelizes KNN on the GPU. It optimizes data access by making good use of the coalesced access power of global memory,and reduces thread serialization by filtering out as much data as possible in advance that is to be sorted. Experiments on KDD,Poker and Covertype datasets and comparisons with some existing methods show that the number of floating point arithmetic of executed per second of this distance computing method is up to 266. 37 × 109 ,and is up to 26. 47 × 109 in sort phase, which are superior to that of existed methods.
Key words:
K-nearest Neighbor ( KNN) problem,
Graphics Processing Unit ( GPU),
parallel computing,
algorithm
acceleration,
coalesced access,
global memory
摘要： K-近邻计算在数据集规模较大时计算复杂度较高,因此,利用图形处理器(GPU)强大的并行计算能力对K-近邻算法进行加速。在分析现有K-近邻算法的基础上,针对该算法时间开销过大的问题,结合GPU 的体系结构特征实现基于GPU 的K-近邻算法。利用全局存储器的合并访问特性,提高GPU 全局存储器访问数据的效率,通过事先过滤数据的方法来减少参与排序的数据量,进而减少排序阶段的线程串行化时间。在KDD,Poker, Covertype 3 个数据集上进行实验, 结果表明, 该实现方法在距离计算阶段每秒执行的浮点运算次数为266. 37 ×109 次,而排序阶段为26. 47 ×109 次,优于已有方法。
关键词:
K-近邻问题,
图形处理器,
并行计算,
算法加速,
合并访问,
全局存储器
CLC Number: