Performance Analysis of GPU and CPU Parallelization on the Kmeans Algorithm

Sammanfattning: The K-means algorithm is one of the more known unsupervised algorithms that aims to partition data points into a specified number of clusters, where each data point belongs to the cluster with the nearest cluster center, which is also known as a centroid. However, a basic implementation of the K-means algorithm, without any optimizations, is ineffective when used in larger applications. In the study, parallelization is investigated as a tool for speeding up the K-means algorithm. An experiment comparing both CPU and GPU parallelization was conducted. The experimentation consisted of benchmarking different parallel implementations of CPU and GPU K-means algorithms with timers. Different parameters were used, such as the number of clusters that the data sets should be divided into as well as the number of data points. Some of the CPU implementations also allowed different amounts of threads to run which was also varied in this experimentation. The result from the experimentation shows that most of the CPU implementations were efficient for low to medium size data sets and lower number of clusters meanwhile the GPU implementation was the most efficient for larger data sets and did also perform better as the number of clusters grew for each data set.