Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a GPU-accelerated multi-level hypergraph partitioning algorithm designed for problems with bounded partition size and distinct inbound hyperedge constraints. By materializing the hypergraph's incidence structure and exploiting set sparsity, the algorithm efficiently enforces constraints within nested iterations. The implementation achieves speedups up to 940x and improves connectivity by 2-26% compared to a sequential multi-level partitioner.
Achieve near-instant hypergraph partitioning with up to 940x speedup on GPU while simultaneously improving solution quality.
Hypergraph partitioning is a pervasive NP-hard problem, and accelerating its computation on GPU can both slice time-to-solution and raise quality of results. In this work, we implement a multi-level hypergraph partitioning algorithm on GPU targeting a specific set of problem constraints: bounded per-partition size and distinct inbound hyperedges. Manipulating hypergraphs requires long orders of nested iterations, and enforcing these constraints introduces further set operations amidst them. Hence, we design algorithms around our problem's specifics, materializing the hypergraph's incidence structure in memory and exploiting set sparsity. Our results show competitive speedups as high as 940x and 2-26% better results in connectivity over a sequential multi-level partitioner.