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%)
Users
Please
log in to take part in the discussion (add own reviews or comments).