hMETIS - Hypergraph & Circuit Partitioning

Current version: 1.5.3, 11/22/98 [Alpha version: 2.0pre1, 5/24/07]

hMETIS is a set of programs for partitioning hypergraphs such as those corresponding to VLSI circuits. The algorithms implemented by hMETIS are based on the multilevel hypergraph partitioning schemes developed in our lab.

The advantages of hMETIS are the following:

Provides high quality partitions!
On a wide range of hypergraphs arising in the VLSI domain hMETIS produces bisections that cut 10% to 300% fewer hyperedges than those cut by other popular algorithms such as PARABOLI, PROP, and CLIP-PROP, especially for circuits with over 100,000 cells, and circuits with non-unit cell area
It is extremely fast!
A single run of hMETIS is faster than a single run of simpler schemes such as FM, KL, or CLIP. Furthermore, because of its very good average cut characteristics, it produces high quality partitionings in significantly fewer runs. It can bisect circuits with over 100,000 vertices in a couple of minutes on Pentium-class workstations.