Multilevel Hypergraph Partitioning: Application in VLSI Domain

Multilevel Hypergraph Partitioning: Application in VLSI Domain

1997 | George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar
This paper introduces a new multilevel hypergraph partitioning algorithm, hMETIS, designed for VLSI design applications. The algorithm is based on a multilevel paradigm, which involves constructing a sequence of successively coarser hypergraphs and refining the bisection of the smallest hypergraph to obtain a high-quality bisection of the original hypergraph. The authors evaluate the performance of hMETIS in terms of hyperedge cut size and runtime on various VLSI circuits. Experiments show that hMETIS produces partitionings that are 4% to 23% better in quality compared to other state-of-the-art schemes, while being significantly faster, often requiring 4 to 15 times less time. The algorithm scales well for large hypergraphs, with hypergraphs containing over 100,000 vertices being bisectioned in a few minutes on modern workstations. The paper also discusses the development of new hypergraph coarsening schemes and refinement algorithms, which enhance the quality and speed of the partitioning process.This paper introduces a new multilevel hypergraph partitioning algorithm, hMETIS, designed for VLSI design applications. The algorithm is based on a multilevel paradigm, which involves constructing a sequence of successively coarser hypergraphs and refining the bisection of the smallest hypergraph to obtain a high-quality bisection of the original hypergraph. The authors evaluate the performance of hMETIS in terms of hyperedge cut size and runtime on various VLSI circuits. Experiments show that hMETIS produces partitionings that are 4% to 23% better in quality compared to other state-of-the-art schemes, while being significantly faster, often requiring 4 to 15 times less time. The algorithm scales well for large hypergraphs, with hypergraphs containing over 100,000 vertices being bisectioned in a few minutes on modern workstations. The paper also discusses the development of new hypergraph coarsening schemes and refinement algorithms, which enhance the quality and speed of the partitioning process.
Reach us at info@study.space