K-Means on Commodity GPUs with CUDA

Abstract

K-means algorithm is one of the most famous unsupervised clustering algorithms. Many theoretical improvements for the performance of original algorithms have been put forward, while almost all of them are based on single instruction single data (SISD) architecture processors (GPUs), which partly ignored the inherent paralleled characteristic of the algorithms. In this paper, a novel single instruction multiple data (SIMD) architecture processors (GPUs) based k-means algorithm is proposed. In this algorithm, in order to accelerate compute-intensive portions of traditional k-means, both data objects assignment and k-centroids recalculation are offloaded to the GPU in parallel. We have implemented this GPU-based k-means on the newest generation GPU with compute unified device architecture(CUDA). The numerical experiments demonstrated that the speed of GPU-based k-means could reach as high as 40 times of the CPU-based k-means.