Multilevel hypergraph partitioning: Applications in VLSI domain

Research output: Contribution to journalArticlepeer-review

547 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 have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%-23% better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4-10 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%-30%).

Original languageEnglish (US)
Pages (from-to)69-79
Number of pages11
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume7
Issue number1
DOIs
StatePublished - 1999

Bibliographical note

Funding Information:
Manuscript received April 29, 1997; revised March 23, 1998. This work was supported under IBM Partnership Award NSF CCR-9423082, by the Army Research Office under Contract DA/DAAH04-95-1-0538, and by the Army High Performance Computing Research Center, the Department of the Army, Army Research Laboratory Cooperative Agreement DAAH04-95-2-0003/Contract DAAH04-95-C-0008.

Keywords

  • Circuit partitioning
  • Hypergraph partitioning
  • Multilevel algorithms

Fingerprint

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

Cite this