Title :
Parallelization of spectral clustering algorithm on multi-core processors and GPGPU
Author :
Jing Zheng ; Wenguang Chen ; Yurong Chen ; Zhang, Yimin ; Zhao, Ying ; Weimin Zheng
Author_Institution :
Tsinghua Univ., Beijing
Abstract :
Spectral clustering is a widely-used algorithm in the field of information retrieval, data mining, machine learning and many others. It can help to cluster a large number of data into several categories without requiring any additional information about the dataset or the categories, so that people can find information by categories easily. In this paper, we parallelize the algorithm proposed by Andrew Y. Ng, Michael I. Jordan and Yair Weiss. We provide two versions of implementation: one is parallelized in OpenMP; the other is programmed in the NVIDIA CUDA (compute unified device architecture), which is the environment provided by NVIDIA to program on its CUDA-Enabled GPGPUs (general-purpose graphic processing unit). We can achieve about three times speedup in OpenMP and around ten times speedup using CUDA in our experiments.
Keywords :
information retrieval; parallel algorithms; pattern clustering; GPGPU; NVIDIA CUDA; OpenMP; compute unified device architecture; data mining; general-purpose graphic processing unit; information retrieval; machine learning; multicore processors; spectral clustering algorithm; Clustering algorithms; Data mining; Fluid dynamics; Graphics; Information retrieval; Machine learning algorithms; Multicore processing; Partitioning algorithms; Search engines; Testing;
Conference_Titel :
Computer Systems Architecture Conference, 2008. ACSAC 2008. 13th Asia-Pacific
Conference_Location :
Hsinchu
Print_ISBN :
978-1-4244-2682-9
Electronic_ISBN :
978-1-4244-2683-6
DOI :
10.1109/APCSAC.2008.4625449
