MG-αGCD: Accelerating Graph Community Detection on Multi-GPU Platforms

Graph community detection is widely applied in fields such as genetic engineering and social network analysis.As the scale of input graphs continues to grow and multi-GPU platforms become increasingly prevalent, utilizing the storage capacity and computational power of these platforms to scale graph community detection algorithms has become more feasible.However, existing multi-GPU graph community detection methods are constrained by the traditional CPUdominated communication model, and fail to simultaneously account for the irregular sparse memory access patterns and the latency disparities between local and remote communication.Consequently, they do not fully exploit modern high-speed GPU interconnect technologies.Furthermore, while current solutions propose various strategies to mitigate the decline in clustering quality during parallelization, these approaches are often inefficient or compromise clustering quality.Finally, to address the high memory overhead of the algorithms, existing Multi-GPU solutions extend the graph size limit at the cost of reduced performance.To address these challenges, we propose MG-GCD, a novel graph community detection algorithm designed for multi-GPU platforms.First, MG-GCD introduces a loading balancing and latency-aware computation-communication pipeline that effectively mitigates the overhead of highlatency remote communication.Second, MG-GCD incorporates a bidirectional probing heuristic to enhance execution efficiency while outperforming existing methods in clustering quality.Lastly, MG-GCD employs a two-phase graph coarsening algorithm consisting of a symbolic phase and a numeric phase, which significantly reduces GPU peak memory usage and minimizes data transfers between CPU and