Parallel Canopy Clustering on GPUs
Parallel Canopy Clustering on GPUs
复制标题
DOI：
10.1007/978-3-319-22849-5_23
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
Yusuke Kozawa;Fumitaka Hayashi;Toshiyuki Amagasa;H. Kitagawa
中科院分区：
文献类型：
--
作者：
Yusuke Kozawa;Fumitaka Hayashi;Toshiyuki Amagasa;H. Kitagawa
Canopy聚类是标准聚类算法（如ask-means聚类和分层聚类）的预处理方法。冠层聚类可以大大降低聚类算法的计算量。然而，如果我们naïvely实现它，树冠集群本身也可能需要大量的时间来处理大量数据。为了解决这个问题，我们在gpu上提出了高效的树冠聚类算法和实现，gpu最近已经发展为通用多核处理器。本文不仅加快了原始冠层聚类的计算速度，而且提出了一种基于网格索引的聚类算法。该算法将数据划分为单元，以减少冗余计算，同时利用图形处理器的并行性。实验表明，在GPU上的实现比在两个八核cpu上的多线程SIMD实现平均快2倍。
Canopy clustering is a preprocessing method for standard clustering algorithms such ask-means and hierarchical agglomerative clustering. Canopy clustering can greatly reduce the computational cost of clustering algorithms. However, canopy clustering itself may also take a vast amount of time for handling massive data, if we naïvely implement it. To address this problem, we present efficient algorithms and implementations of canopy clustering on GPUs, which have evolved recently as general-purpose many-core processors. We not only accelerate the computation of original canopy clustering, but also propose an algorithm using grid index. This algorithm partitions the data into cells to reduce redundant computations and, at the same time, to exploit the parallelism of GPUs. Experiments show that the proposed implementations on the GPU is 2 times faster on average than multi-threaded, SIMD implementations on two octa-core CPUs.