一种基于CUDA的K-Means多级并行优化方法

摘要

K-Means聚类算法是data mining领域中最常用的算法之一.在进行海量数据分析时,K-Means均值聚类的计算时间与其要处理的计算量成正比.因此,数据量越大计算开销也越长.为了提升算法的运算性能,本文设计了一种基于CUDA模型的多级并行的K-Means算法优化方法.将K-Means串行算法并行化,并对并行计算部分进行包括线程块级,线程级,指令级,比特级在内的多级性能优化.首先,在计算样本点与聚类中心距离的核函数中,采用矩阵乘的思想对主要步骤进行并行处理,初步提升算法性能;然后,对核函数的线程块,块中线程数,每线程执行的指令数及比特数进行逐级分析和优化.在合理利用计算资源和存储资源的同时提升算法计算性能,使聚类效果达到最优;最后,通过多项实验对本文方法进行仿真和验证,检验其可行性.结果表明,在保证实验结果准确性的情况下,与其它优化并行算法相比,本文方法最高加速比达到了39.7%,平均加速比达到了22.3%,同时降低了GPU资源占用率.