【摘要】：基于密度峰值的聚類方法 DP(density peak)由于其新穎有效的特點(diǎn)而廣泛應(yīng)用于科學(xué)研究。然而,當(dāng)確定集群中心時,DP會對每對數(shù)據(jù)點(diǎn)操作多次,從而導(dǎo)致較高的計算復(fù)雜度。在本文中,我們提出了一種基于GPU(graphics processing unit)的高效并行密度峰值算法。我們分析密度峰值聚類算法的原理來研究其計算瓶頸,并評估其并行的潛力。根據(jù)分析,我們提出了CUDA-DP(compute unified device architecture-DP),一種針對GPU架構(gòu)的高效并行密度峰值聚類算法,并用CUDA實現(xiàn)了這種并行方法。具體來說,我們使用共享內(nèi)存減少了全局內(nèi)存訪問量。更進(jìn)一步,為了利用GPU的合并訪問機(jī)制,我們將CUDA-DP程序的數(shù)據(jù)結(jié)構(gòu)從AOS(array of structures)重構(gòu)為SOA(structure of arrays)。另外,我們分別引入二進(jìn)制搜索方法和采樣方法,以避免對距離矩陣進(jìn)行排序造成的計算開銷。實驗結(jié)果表明,與基于CPU的密度峰值實現(xiàn)相比,CUDA-DP可以實現(xiàn)超過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

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 Yaobin He;Fan Zhang;Ye Li;Jun Huang;Ling Yin;Chengzhong Xu;;Multiple Routes Recommendation System on Massive Taxi Trajectories[J];Tsinghua Science and Technology;2016年05期

2 Jiaxin Li;Dongsheng Li;Yuming Ye;Xicheng Lu;;Efficient Multi-Tenant Virtual Machine Allocation in Cloud Data Centers[J];Tsinghua Science and Technology;2015年01期

【共引文獻(xiàn)】

相關(guān)期刊論文 前5條

1 Ke-shi GE;Hua-you SU;Dong-sheng LI;Xi-cheng LU;;基于GPU的密度峰值并行聚類算法（英文）[J];Frontiers of Information Technology & Electronic Engineering;2017年07期

2 Lizhao Liu;Wentu Gao;Jian Liu;Huayi Yin;Huarong Xu;Shunzhi Zhu;;Multi-Embed Nonlinear Scale-Space for Image Trust Root Generation[J];中國通信;2016年11期

3 Yun-xiang ZHAO;Wan-xin ZHANG;Dong-sheng LI;Zhen HUANG;Min-ne LI;Xi-cheng LU;;負(fù)載均衡的分布式指紋識別系統(tǒng)（英文）[J];Frontiers of Information Technology & Electronic Engineering;2016年08期

4 Zhaoning ZHANG;Dongsheng LI;Kui WU;;Large-scale virtual machines provisioning in clouds:challenges and approaches[J];Frontiers of Computer Science;2016年01期

5 Zi-yang LI;Yi-ming ZHANG;Dong-sheng LI;Peng-fei ZHANG;Xi-cheng LU;;VirtMan:design and implementation of a fast booting system for homogeneous virtual machines in iVCE[J];Frontiers of Information Technology & Electronic Engineering;2016年02期

【二級參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 LI Ming;Andrey Lukyanenko;Sasu Tarkoma;Antti Yl-Jski;;數(shù)據(jù)中心網(wǎng)絡(luò)中的MPTCP Incast（英文）[J];中國通信;2014年04期

2 Waseem Ahmed;Yongwei Wu;;Estimation of Cloud Node Acquisition[J];Tsinghua Science and Technology;2014年01期

3 Wei Chen;Junwei Cao;Yuxin Wan;;QoS-Aware Virtual Machine Scheduling for Video Streaming Services in Multi-Cloud[J];Tsinghua Science and Technology;2013年03期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 馬伯寧;王晨昊;湯曉安;匡綱要;;基于GPU的二維離散小波變換快速計算[J];國防科技大學(xué)學(xué)報;2011年03期

2 ZW;;3D游戲利器 主流嵌入式處理器GPU逐個看[J];電腦迷;2011年19期

3 王志國;王貴錦;施陳博;苗權(quán);林行剛;;積分圖像的快速GPU計算[J];計算機(jī)應(yīng)用研究;2011年10期

4 盧永菁;王東;;基于GPU的高速網(wǎng)絡(luò)入侵檢測系統(tǒng)設(shè)計[J];計算機(jī)工程與應(yīng)用;2011年33期

5 儲t熆，

本文編號：2271690