TU Berlin

Fachgebiet Datenbanksysteme und InformationsmanagementPublikationen

Logo FG DIMA-new  65px


zur Navigation


Efficient k-means on GPUs
Zitatschlüssel damon/LutzBRZM18
Autor Clemens Lutz, Sebastian Breß, Tilmann Rabl, Steffen Zeuch, Volker Markl
Buchtitel Proceedings of the 14th International Workshop on Data Management on New Hardware (DAMON '18)
Seiten 3:1 - 3:3
Jahr 2018
DOI 10.1145/3211922.3211925
Ort Houston, Texas
Adresse New York, NY, USA,
Journal DaMoN 2018
Herausgeber ACM,
Serie DAMON '18
Kapitel 3
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe