Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces TC-MIS, a novel algorithm that leverages Tensor Cores (TCs) to accelerate Maximal Independent Set (MIS) computation by reformulating key phases as sparse matrix-vector multiplication (SpMV). By tiling the graph adjacency matrix and employing Warp Matrix Multiply-Accumulate (WMMA) operations, TC-MIS transforms irregular graph traversal into regular, massively parallel computation suitable for TCs. Experiments across various TC-enabled GPU architectures demonstrate significant speedups, achieving up to 44.38x improvement over state-of-the-art methods while maintaining solution quality.
Tensor Cores, typically used for ML/DL, unlock up to 44x speedups for Maximal Independent Set computations on graphs.
Maximal Independent Set (MIS) in a graph is a fundamental problem with applications in resource allocation, scheduling, and network optimization. Although graphs are inherently un-structured and challenging for GPU parallelism due to irregular memory access and workload imbalance, specialized GPU algorithms have achieved good performance, processing million-vertex graphs in milliseconds. Modern GPUs are equipped with Tensor Cores (TCs), specialized units for matrix operations with 8-16x higher throughput than CUDA Cores (CCs), which are extensively used for ML, DL, and inference tasks but remain largely unexplored for graph algorithms. In this paper, we present TC-MIS, a TC-accelerated algorithm that reformulates key phases of MIS computation as sparse matrix-vector multiplication (SpMV). TC-MIS tiles the graph adjacency matrix and employs Warp Matrix Multiply-Accumulate (WMMA) operations to transform irregular graph traversal into regular, massively parallel computation. Our evaluation across TC-enabled microarchitectures (Ampere, Ada Lovelace, Hopper, Blackwell) demonstrates that TC-MIS achieves an average speedup of 2.84x on RTX A5000, 4.84x on L40S, 18.80x on H200 GPUs, and 5.20x on RTX 5080 with a maximum speedup of 44.38x on H200 GPU over state-of-the-art methods, while maintaining solution quality comparable to that obtained by established heuristics that produce near-maximum independent sets.