Prestandaanalys av GPU- och CPU parallelisering på K- means algoritmen

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. K-means algoritmen är en av de vanligaste oövervakade maskininlärningsalgoritmerna som finns. K-means syfte är att partitionera datapunkter till ett specificerat antal grupper, där varje datapunkt tillhör den grupp med närmast centrum (även kallat centroid). Men en grundlig implementation av K-means algoritmen, utan några optimeringar, är ineffektiv i större applikationer. I denna studie undersöks parallellisering som ett verktyg för att accelerera K-means genom att jämföra både CPU och GPU parallellisering. I studien mäts prestandan av olika parallella CPU och GPU implementationer av K-means genom timers. Olika parametrar, såsom antal grupper och antar datapunkter, användes och timades. Några CPU implementation tillät även modifikationer på antal trådar, vilket vi också timade för olika trådar. Resultatet från studien visade att de flesta CPU implementationerna var mer effektiva än GPU implementationen för små till mellanstora datauppsättningar med få grupper. Däremot visade det sig att GPU implementation var mer effektiv för stora datauppsättningar och gjorde bättre ifrån när antalet grupper ökade