TU Berlin

Database Systems and Information Management GroupPublications

Logo FG DIMA-new  65px

Page Content

to Navigation


Efficient k-means on GPUs
Citation key damon/LutzBRZM18
Author Clemens Lutz, Sebastian BreƟ, Tilmann Rabl, Steffen Zeuch, Volker Markl
Title of Book Proceedings of the 14th International Workshop on Data Management on New Hardware (DAMON '18)
Pages 3:1 - 3:3
Year 2018
DOI 10.1145/3211922.3211925
Location Houston, Texas
Address New York, NY, USA,
Journal DaMoN 2018
Editor ACM,
Series DAMON '18
Chapter 3
Abstract k-Means is a versatile clustering algorithm widely-used in practice. To cluster large data sets, state-of-the-art implementations use GPUs to shorten the data to knowledge time. These implementations commonly assign points on a GPU and update centroids on a CPU. We show that this approach has two main drawbacks. First, it separates the two algorithm phases over different processors, which requires an expensive data exchange between devices. Second, even when both phases are computed on the GPU, the same data are read twice per iteration, leading to inefficient use of memory bandwidth. In this paper, we describe a new approach that executes k-means in a single data pass per iteration. We propose a new algorithm to updates centroids that allows us to perform both phases efficiently on GPUs. Thereby, we remove data transfers within each iteration. We fuse both phases to eliminate artificial synchronization barriers, and thus compute k-means in a single data pass. Overall, we achieve up to 20x higher throughput compared to the state-of-the-art approach.
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe