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

CUDA-based Parallel K-means Clustering Algorithm

摘要:

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

Abstract:

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.