cuMIS: A Unified Scalable Framework for Computing Maximal Independent Sets on Trillion-Edge Graphs
This paper addresses the problem of computing a maximal independent set (MIS), defined as a set of vertices where no two vertices are connected by an edge and no additional vertex can be added without violating the independence property. While several GPU-accelerated algorithms exist to find the MIS efficiently, the problem remains challenging for graphs exceeding the memory of a single GPU. In this paper, we present cuMIS, a unified scalable framework for computing MIS on single-GPU, multi-GPU, and distributed multi-node configurations. cuMIS employs a data-driven approach that processes only an active set of undecided vertices for reduced memory access and a degree-aware workload distribution that mitigates imbalance and thread divergence. Our results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 × , respectively, while maintaining comparable or superior solution quality. Finally, we demonstrate that cuMIS scales effectively to process trillion-edge graphs in distributed multi-node environments where existing approaches fail to operate.