基于GPU的密度峰值并行聚类算法（英文）

发布时间：2018-10-15 06:39

【摘要】：基于密度峰值的聚类方法 DP(density peak)由于其新颖有效的特点而广泛应用于科学研究。然而,当确定集群中心时,DP会对每对数据点操作多次,从而导致较高的计算复杂度。在本文中,我们提出了一种基于GPU(graphics processing unit)的高效并行密度峰值算法。我们分析密度峰值聚类算法的原理来研究其计算瓶颈,并评估其并行的潜力。根据分析,我们提出了CUDA-DP(compute unified device architecture-DP),一种针对GPU架构的高效并行密度峰值聚类算法,并用CUDA实现了这种并行方法。具体来说,我们使用共享内存减少了全局内存访问量。更进一步,为了利用GPU的合并访问机制,我们将CUDA-DP程序的数据结构从AOS(array of structures)重构为SOA(structure of arrays)。另外,我们分别引入二进制搜索方法和采样方法,以避免对距离矩阵进行排序造成的计算开销。实验结果表明,与基于CPU的密度峰值实现相比,CUDA-DP可以实现超过45倍的加速。
[Abstract]:DP (density peak), a clustering method based on peak density, is widely used in scientific research because of its novel and effective characteristics. However, when the cluster center is determined, DP operates on each pair of data points multiple times, resulting in high computational complexity. In this paper, we propose an efficient parallel peak density algorithm based on GPU (graphics processing unit). We analyze the principle of peak density clustering algorithm to study its computational bottleneck and evaluate its parallelism potential. According to the analysis, we propose CUDA-DP (compute unified device architecture-DP), an efficient parallel density peak clustering algorithm for GPU architecture, and implement this parallel method with CUDA. Specifically, we use shared memory to reduce global memory access. Further, in order to take advantage of GPU's merge access mechanism, we reconstruct the data structure of CUDA-DP programs from AOS (array of structures) to SOA (structure of arrays). In addition, the binary search method and the sampling method are introduced to avoid the computational overhead caused by sorting the distance matrix. The experimental results show that CUDA-DP can achieve more than 45 times acceleration compared with the density peak realization based on CPU.
【作者单位】： National
【基金】：supported by the National Basic Research Program(973)of China(No.2014CB340303) the National Natural Science Foundation of China(Nos.61502509 and 61222205) the Program for New Century Excellent Talents in University the Fok Ying-Tong Education Foundation(No.141066)
【分类号】：TP311.13

【参考文献】