Multilevel Hypergraph Partitioning: Applications in VLSI Domain

George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar
IEEE Transactions on VLSI Systems, Vol. 7, No. 1, pp. 69-79, 1999
Download Paper
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%).
This is an expanded version of the DAC 1997 paper, which introduced the algorithms of [hlink:[metis/hmetis/overview][hMETIS]].
Research topics: Circuit partitioning | hMETIS