A New Method for GPU Based Irregular Reductions and Its Application to K-Means Clustering

Report
Authors:Dhanasekeran, Balaji, Department of Computer ScienceUniversity of Virginia Rubin, Norm, Department of Computer ScienceUniversity of Virginia
Abstract:

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´┐Ż HD 5870 (best speedup was 3.5 times) compared to the hybrid approach. In addition, we compare the GPU code with the standard OpenMP benchmark, MineBench. In that implementation, both the map and reduce steps are computed on the CPU. For large data sizes, the new GPU scheme shows great promise, with performance up to 35 times faster than MineBench on a four core Intel i7 CPU.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Dhanasekeran, Balaji, and Norm Rubin. "A New Method for GPU Based Irregular Reductions and Its Application to K-Means Clustering." University of Virginia Dept. of Computer Science Tech Report (2010).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2010