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

K-Means Multi-level Parallel Optimization Method Based on CUDA

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

K-means clustering algorithm is one of the most commonly used algorithms in data mining.When performing massive data analysis,the calculation time of K-Means mean clustering is also proportional to the amount of data to be processed,so the larger the amount of data,the greater the calculation.In order to improve the performance of the algorithm,this paper designs a multi-level parallel k-means algorithm optimization method based on CUDA model.Based on serial analysis of the K-Means algorithm,it is modified into a parallel algorithm.And the multi-level performance optimization of the parallel computing part including thread block level,thread level,instruction level,and bit level.First,in the kernel that calculates the distance between the sample points and the cluster center,the idea of matrix multiplication is used to improve the algorithm performance.Then,the block,the number of threads,the number of instructions executed by each thread, and the number of bits are analyzed and optimized step by step.With the reasonable use of computing resources and storage resources,the algorithm s computing performance is increased as much as possible to achieve the optimal clustering effect.Finally,through a number of experiments,the method of this paper is simulated and verified to verify its feasibility.The experimental results show that the optimized algorithm improves the calculation speed while ensuring the accuracy of the experimental results.Compared with the general parallel K-M eans algorithm,the maximum speed-up is 39.1% and average speed-up is 22.3%,while the resource occupancy rate has decreased.