TY - GEN
T1 - CUDA-DClust+
T2 - 28th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2021
AU - Poudel, Madhav
AU - Gowanlock, Michael
N1 - Funding Information:
We thank Eleazar Leal for providing the G-DBSCAN and CPU-DBSCAN source code used in our experiments. This material is based upon work supported by the National Science Foundation under Grant No. 2042155.
Publisher Copyright:
© 2021 IEEE.
PY - 2021
Y1 - 2021
N2 - Density-based clustering algorithms are widely used unsupervised data mining techniques to find the clusters of points in dense regions that are separated by low-density regions. This algorithm is inherently sequential and has limitations in its parallel implementation. There have been several parallel algorithms presented in the literature for multi-core CPUs and many-core GPUs. One such algorithm for the GPU is CUDA-DCLUST. In this paper, we propose a new GPU-accelerated DBSCAN algorithm with several optimizations. In comparison to prior work, our algorithm, Cuda-dclust+:(i) computes the indexing structure on the GPU, (ii) uses kernel fusion to combine the index search and cluster expansion kernels, which reduces communication and synchronization overhead with the host, and (iii) seed list management control is primarily given to the GPU rather than the CPU, which further decreases CPU-GPU communication overhead. We compare our algorithm to three state-of-the-art parallel algorithms in the literature on six real-world datasets. We find that our algorithm achieves a speedup of up to 23x over the fastest GPU algorithm.
AB - Density-based clustering algorithms are widely used unsupervised data mining techniques to find the clusters of points in dense regions that are separated by low-density regions. This algorithm is inherently sequential and has limitations in its parallel implementation. There have been several parallel algorithms presented in the literature for multi-core CPUs and many-core GPUs. One such algorithm for the GPU is CUDA-DCLUST. In this paper, we propose a new GPU-accelerated DBSCAN algorithm with several optimizations. In comparison to prior work, our algorithm, Cuda-dclust+:(i) computes the indexing structure on the GPU, (ii) uses kernel fusion to combine the index search and cluster expansion kernels, which reduces communication and synchronization overhead with the host, and (iii) seed list management control is primarily given to the GPU rather than the CPU, which further decreases CPU-GPU communication overhead. We compare our algorithm to three state-of-the-art parallel algorithms in the literature on six real-world datasets. We find that our algorithm achieves a speedup of up to 23x over the fastest GPU algorithm.
KW - Clustering
KW - DBSCAN
KW - GPGPU
KW - Graphics Processing Unit
KW - Machine Learning
KW - Outlier Detection
UR - http://www.scopus.com/inward/record.url?scp=85125642881&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85125642881&partnerID=8YFLogxK
U2 - 10.1109/HiPC53243.2021.00049
DO - 10.1109/HiPC53243.2021.00049
M3 - Conference contribution
AN - SCOPUS:85125642881
T3 - Proceedings - 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics, HiPC 2021
SP - 354
EP - 363
BT - Proceedings - 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics, HiPC 2021
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 17 December 2021 through 18 December 2021
ER -