A New 2-way Multi-level Partitioning Algorithm

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