A new method for GPU based irregular reductions and its application to k-means clustering
Advanced Micro Devices, Inc.
Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units, GPGPU-4, 2011
@inproceedings{dhanasekaran2011new,
title={A new method for GPU based irregular reductions and its application to k-means clustering},
author={Dhanasekaran, B. and Rubin, N.},
booktitle={Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units},
pages={2},
year={2011},
organization={ACM}
}
A frequently used method of clustering is a technique called k-means clustering. The k-means algorithm consists of two steps: A map step, which is simple to execute on a GPU, and a reduce step, which is more problematic. Previous researchers have used a hybrid approach in which the map step is computed on the GPU and the reduce step is performed on the CPU. In this work, we present a new algorithm for irregular reductions and apply it to k-means such that the GPU executes both the map and reduce steps. We provide experimental comparisons using OpenCL. Our results show that our scheme is 3.2 times faster than the hybrid scheme for k = 10, an average 1.5 times faster when the number of clusters, k = 100 and on average equal for k = 400, on an ATI Radeon
August 21, 2011 by hgpu
