A new 2-way multi-level partitioning algorithm

Partitioning is a fundamental problem in the design of VLSI circuits. In re cent years, the multi-level partitioning approach has been used with succes s by a number of researchers. This paper describes a new multi-level partit ioning algorithm (PART) that combines a blend of iterative improvement and clustering, biasing of node gains, and local uphill climbs. PART is competi tive with recent state-of-the-art partitioning algorithms. PART was able to find new lower cuts for many benchmark circuits. Under suitably mild assum ptions, PART also runs in linear time.