A New 2‐way Multi‐level Partitioning Algorithm

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