Multilevel hypergraph partitioning: Applications in vlsi domain

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 pro-jecting and refining the bisection to the next level finer hypergraph. We evaluate the performance both in terms of the size of the hyper-edge cut on the bisection as well as run time on a number of VLSI circuits. Our experiments show that our multilevel hypergraph par-titioning 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 al-gorithm 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. Hy-pergraphs with over 100,000 vertices can be bisected in a few min-utes on today’s workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consis-tently with larger margins (9 % to 30%).