Multilevel hypergraph partitioning: applications in VLSI domain

摘要

In this paper, we present a new hypergraph-partitioning algorithmnthat is based on the multilevel paradigm. In the multilevel paradigm, ansequence of successively coarser hypergraphs is constructed. A bisectionnof the smallest hypergraph is computed and it is used to obtain anbisection of the original hypergraph by successively projecting andnrefining the bisection to the next level finer hypergraph. We havendeveloped new hypergraph coarsening strategies within the multilevelnframework. We evaluate their performance both in terms of the size ofnthe hyperedge cut on the bisection, as well as on the run time for annumber of very large scale integration circuits. Our experiments shownthat our multilevel hypergraph-partitioning algorithm producesnhigh-quality partitioning in a relatively small amount of time. Thenquality of the partitionings produced by our scheme are on the averagen6%-23% better than those produced by other state-of-the-art schemes.nFurthermore, our partitioning algorithm is significantly faster, oftennrequiring 4-10 times less time than that required by the other schemes.nOur multilevel hypergraph-partitioning algorithm scales very well fornlarge hypergraphs. Hypergraphs with over 100 000 vertices can benbisected in a few minutes on today's workstations. Also, on the largenhypergraphs, our scheme outperforms other schemes (in hyperedge cut)nquite consistently with larger margins (9%-30%)