Multilevel hypergraph partitioning: application in VLSI domain

Research output: Contribution to journalConference article

464 Scopus citations

Abstract

In this paper, we present a new hypergraph partitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We evaluate the performance both in terms of the size of the hyperedge cut on the bisection as well as run time on a number of VLSI circuits. Our experiments show that our multilevel hypergraph partitioning algorithm produces high quality partitioning in relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 4% to 23% better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4 to 15 times less time than that required by the other schemes. Our multilevel hypergraph partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100,000 vertices can be bisected in a few minutes on today's workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9% to 30%).

Original languageEnglish (US)
Pages (from-to)526-529
Number of pages4
JournalProceedings - Design Automation Conference
StatePublished - Jan 1 1997
EventProceedings of the 1997 34th Design Automation Conference - Anaheim, CA, USA
Duration: Jun 9 1997Jun 13 1997

Fingerprint Dive into the research topics of 'Multilevel hypergraph partitioning: application in VLSI domain'. Together they form a unique fingerprint.

  • Cite this