A Multi-GPU Algorithm for Computing Maximal Independent Sets in Large Graphs

Computing a maximal independent set (MIS) of a graph is an important problem in many scientific applications.Several parallel algorithms exist to perform this computation quickly.Though the state-of-the-art GPU implementation is very efficient, it cannot process graphs that do not fit in the global memory of a single GPU.We propose MG-MIS, a multi-GPU algorithm that addresses this problem.It distributes the computation across the GPUs in a compute node and uses novel techniques to minimize inter-GPU communication.Our results show that, for graphs that require more than 32 GB memory, MG-MIS outperforms the state-of-the-art single-GPU code with UVM by a geometric mean of 17.73 on a system with 4 V100 GPUs, each with 32 GB global memory.For another set of graphs that require more than 12 GB memory, MG-MIS outperforms the same single-GPU code by 22.88 on a system with 2 RTX 3080 GPUs, each with a global memory of 12 GB.On average, the size of the MIS computed by MG-MIS is 2.6% smaller than that produced by the state-of-the-art single-GPU code.