DocumentCode :
3146462
Title :
An Efficient k-Means Algorithm on CUDA
Author :
Wu, Jiadong ; Hong, Bo
Author_Institution :
Sch. of Electr. & Comput. Eng., Georgia Inst. of Technol., Atlanta, GA, USA
fYear :
2011
fDate :
16-20 May 2011
Firstpage :
1740
Lastpage :
1749
Abstract :
The k-means algorithm is widely used for unsupervised clustering. This paper describes an efficient CUDA-based k-means algorithm. Different from existing GPU-based k-means algorithms, our algorithm achieves better efficiency by utilizing the triangle inequality. Our algorithm explores the trade-off between load balance and memory access coalescing through data layout management. Because the effectiveness of the triangle inequity depends on the input data, we further propose a hybrid algorithm that adaptively determines whether to apply the triangle inequality. The efficiency of our algorithm is validated through extensive experiments, which demonstrate improved performance over existing CPU-based and CUDA-based k-means algorithms, in terms of both speed and scalability.
Keywords :
parallel programming; pattern clustering; resource allocation; storage management; CUDA; data layout management; k-means algorithm; load balancing; memory access coalescing; triangle inequality; unsupervised clustering; Algorithm design and analysis; Clustering algorithms; Graphics processing unit; Instruction sets; Labeling; Layout; Linear matrix inequalities;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
ISSN :
1530-2075
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
Type :
conf
DOI :
10.1109/IPDPS.2011.331
Filename :
6009040
Link To Document :
بازگشت