Presentation
BlasPart: A Deterministic Parallel Partitioner for Balanced Large-Scale Hypergraph Partitioning
DescriptionBalanced hypergraph partitioning is a fundamental problem in applications like VLSI design, high-performance computing, etc. Nowadays, large-scale hypergraphs become more common due to the increasing complexity of modern systems. Thus, fast and high-quality deterministic partitioning algorithms are largely in demand. Regarding the quality of partitioning, balance is a critical concern when the number of partitions increases. In this paper, we propose BlasPart, a deterministic parallel algorithm for balanced large-scale hypergraph partitioning. BlasPart leverages a recursive multilevel bisection framework to achieve high-quality partitions while ensuring deterministic outcomes. A level-dependent balance constraint is also proposed to further improve the efficiency and effectiveness of the proposed partitioner. Extensive experiments, with comparisons to the state-of-the-art partitioners (hMETIS, BiPart, and Mt-KaHyPar-SDet), demonstrate that BlasPart achieves better balance and scalability while maintaining competitive partitioning quality and efficiency. BlasPart runs 3.33× faster than Mt-KaHyPar-SDet on average for a 4096-way partitioning task on six benchmarks.
Event Type
Research Manuscript
TimeTuesday, June 2411:15am - 11:30am PDT
Location3004, Level 3
EDA
EDA7: Physical Design and Verification