Improved algorithms for hypergraph bipartitioning

Abstract

Multilevel Fiduccia-Mattheyses MLFM hypergraph partitioning 3, 22, 24 is a fundamental optimization in VLSI CAD physical design. The leading implementation, hMetis 23 , has since 1997 pro veditself substantially superior in both runtime and solution quality t o e v en v ery recent w orks e.g., 13, 17, 25 . In this work, we present t w o sets of results: i new techniques for at FM-based hypergraph partitioning which is the core of multilev el implementations, and ii a new multilev el implementation that o ers leadingedge performance.