Speeding up k-means algorithm by GPUs

You Li*, Kaiyong Zhao, Xiaowen CHU, Jiming LIU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

42 Citations (Scopus)

Abstract

Cluster analysis plays a critical role in a wide variety of applications, but it is now facing the computational challenge due to the continuously increasing data volume. Parallel computing is one of the most promising solutions to overcoming the computational challenge. In this paper, we target at parallelizing k-Means, which is one of the most popular clustering algorithms, by using the widely available Graphics Processing Units (GPUs). Different from existing GPU-based k-Means algorithms, we observe that data dimension is an important factor that should be taken into consideration when parallelizing k-Means on GPUs. In particular, we use two different strategies for low-dimensional data sets and high-dimensional data sets respectively, in order to make the best use of the power of GPUs. For low-dimensional data sets, we exploit GPU on-chip registers to significantly decrease data access latency. For highdimensional data sets, we design a novel algorithm which simulates matrix multiplication and exploits GPU on-chip registers and also on-chip shared memory to achieve high compute-to-memory-access ratio. As a result, our GPU-based k-Means algorithm is three to eight times faster than the best reported GPU-based algorithm.

Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010
Pages115-122
Number of pages8
DOIs
Publication statusPublished - 2010
Event10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010 - Bradford, United Kingdom
Duration: 29 Jun 20101 Jul 2010

Publication series

NameProceedings - 10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, ScalCom-2010

Conference

Conference10th IEEE International Conference on Computer and Information Technology, CIT-2010, 7th IEEE International Conference on Embedded Software and Systems, ICESS-2010, 10th IEEE Int. Conf. Scalable Computing and Communications, ScalCom-2010
Country/TerritoryUnited Kingdom
CityBradford
Period29/06/101/07/10

Scopus Subject Areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Software

User-Defined Keywords

  • Cluster
  • CUDA
  • GPGPU
  • K-means

Fingerprint

Dive into the research topics of 'Speeding up k-means algorithm by GPUs'. Together they form a unique fingerprint.

Cite this