基于滑动门中心点计算的K均值聚类并行算法研究

Research on K - means clustering parallel algorithm based on sliding gate center point calculation

摘要:

随着GPU硬件设备的普及和GPGPU技术的快速发展,越来越多的研究人员投入到GPGPU的研究当中。当前,GPU具有很强大的并行计算能力、浮点运算能力、计算单元集成能力等特点,显示出了GPU在并行计算领域的巨大潜力。CUDA是由NVIDIA公司提出的一种利用GPU进行并行计算的架构,CUDA使得GPU具有友好的可编程性,为研究人员能够在GPU上实现各种领域的科学计算提供了方便的途径。K均值聚类算法由于其概念简单,易于实现等优点成为并行计算研究的一个热门方向。对于K均值并行算法的研究,有基于8核CPU并配备FPGA加速板的方法,但对于一个需要启动数千个线程的复杂模型,基于传统CPU并行计算方法难以实现；也有使用CUDA并行计算平台对K均值聚类算法进行处理,但处理算法时通常忽略对CUDA平台上K均值聚类算法自身的优化。基于以上缺陷,介绍K均值聚类算法的同时对算法在CUDA平台上进行了相应优化,特别针对更新中心点的耗时问题,提出了一种基于滑动门中心点计算的K均值聚类并行计算。实验结果表明,当聚类数较多时,相对于传统的更新中心点算法,基于滑动门中心点并行算法的效率更高。

Abstract:

With the popularity of GPU hardware and the rapid development of GPGPU technology, more researchers have invested in GPGPU research. Beacuse of the strong parallel computing power, floating-point computing power, computing unit integration capabilities and other characteristics, GPU shows the great potential in the field of parallel computing. CUDA is an architecture developed by NVIDIA for parallel computing using a GPU and it makes the GPU highly user-friendly and provides a convenient way for researchers to implement scientific computing in a variety of fields on the GPU. K-means clustering algorithm has become a popular direction for parallel computing because of its simple concept and easy realization. For the K-means parallel algorithm, there is a 8-core CPU and FPGA-based accelerator board method, but for a complex model that needs to start thousands of threads and the traditional CPU parallel computing method is difficult to achieve; What’s more, some researches have study the K-means clustering algorithm based on the CUDA parallel computing platform, but the studies usually ignore the algorithm optimization. Based on the above shortcomings, the K-means clustering algorithm is introduced on the CUDA platform, and the K-means clustering parallel computation based on sliding gate center point calculation is proposed. The The experimental results show that when the number of clusters is large, the parallel algorithm based on the sliding gate is more efficient than the traditional updating center algorithm.