|
|||||
|
|
Accelerating Louvain community detection algorithm on graphic processing unit |
|
| Authors: | Mohammadi Maryam Fazlali Mahmood Hosseinzadeh Mehdi |
| Affiliation: | 1.Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran ;2.Department of Computer and Data Sciences, Faculty of Mathematical Sciences, Shahid Beheshti University, Tehran, Iran ;3.Institute of Research and Development, Duy Tan University, Da Nang, 550000, Vietnam ;4.Mental Health Research Center, Psychosocial Health Research Institue, Iran University of Medical Sciences, Tehran, Iran ; |
| Abstract: | The Louvain community detection algorithm is a hierarchal clustering method categorized in the NP-hard problem. Its execution time to find communities in large graphs is, therefore, a challenge. Parallelization is an effective solution for amortizing Louvain's execution time. In this paper, we propose an adaptive CUDA Louvain method (ACLM) algorithm that benefits from the graphic processing unit (GPU). ACLM uses the shared memory in GPU, as well as the optimal number of threads in the GPU blocks. These features minimize parallelization overhead and accelerate the calculation of modularity parameters. The proposed algorithm allocates threads to each block based on the number of required streaming multiprocessors (SMs) and warps on GPU. The implementation results show that ACLM can effectively accelerate the execution time by 77% compared to the competitive method in the large graph benchmarks. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |