基于CUDA的并行K-means聚类图像分割算法优化

CUDA-based Parallel K-means Clustering Algorithm

为提高K-means聚类算法的运算速度,基于CUDA架构提出一种分块、并行的K-means算法,并采用'合并访问'、'多级规约求和'、'负载均衡'和'指令优化'等策略优化并行算法。实验结果表明,并行K-means算法的分割效果与串行K-means算法相同,但运行速度得到了极大的提高,加速比最高达到560,很好地解决了农业工程实际中由于分割算法带来的瓶颈问题,能够极大地提高农业劳动生产率。

K-means clustering algorithm is an excellent algorithm which has been widely used in the image processing and data mining. However, the algorithm arouses a high computational complexity. This paper made a parallel analysis of K-means algorithm in detail, and proposed a partitioning and parallel K- means algorithm based on CUDA （Compute unified device architecture）. In addition, some optimization strategies, e.g. , coalesced memory access, parallel reduction, load balance and instruction optimization, were discussed to obtain the higher performance. Experimental results show that the parallel K-means algorithm achieves 560x speedup over the sequential C codes, while maintains the same effect. Hence it solves the bottleneck of the algorithm perfectly, which is an attractive alternative to the sequential K-means algorithm for image segmentation and clustering analysis.