K-Means for Parallel Architectures Using All-Prefix-Sum Sorting and Updating Steps

Kai J. Kohlhoff, Vijay S. Pande, Russ B. AltmanIEEE TPDS 2013 · DOI · OpenReview

Abstract

We present an implementation of parallel K-means clustering, called Kps-means, that achieves high performance with near-full occupancy compute kernels without imposing limits on the number of dimensions and data points permitted as input, thus combining flexibility with high degrees of parallelism and efficiency. As a key element to performance improvement, we introduce parallel sorting as data preprocessing and updating steps. Our final implementation for Nvidia GPUs achieves speedups of up to 200-fold over CPU reference code and of up to three orders of magnitude when compared with popular numerical software packages.
BibTeX
@article{kohlhoff2013k,
  author = {Kai J. Kohlhoff and Vijay S. Pande and Russ B. Altman},
  title = {{K-Means for Parallel Architectures Using All-Prefix-Sum Sorting and Updating Steps}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2013},
  doi = {10.1109/tpds.2012.234},
}

Loading related content...

Figure