基于GPU的密度峰值并行聚类算法

2017年第18卷第7期

摘要

关键词

相关研究

回顶部

《信息与电子工程前沿（英文）》 >> 2017年第18卷第7期 doi: 10.1631/FITEE.1601786

基于GPU的密度峰值并行聚类算法

National Lab for Parallel and Distributed Processing, College of Computer, National University of Defense Technology, Changsha 410003, China

录用日期： 2017-09-20 发布日期： 2017-09-20

HTML22 PDF 19 收藏 0

摘要

基于密度峰值的聚类方法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倍的加速。

关键词

GPU ; 密度峰值 ; 聚类 ; 并行计算