Combining problem reduction and adaptive multistart: a new technique for superior iterative partitioning

Abstract

VLSI netlist partitioning has been addressed chiefly by iterative methods (e.g. Kernighan-Lin and Fiduccia-Mattheyses) and spectral methods (e.g. Hagen-Kahng). Iterative methods are the de facto industry standard, but suffer diminished stability and solution quality when instances grow large. Spectral methods have achieved high-quality solutions, particularly for the ratio cut objective, but suffer excessive memory requirements and the inability to capture practical constraints (preplacements, variable module areas, etc.). This work develops a new approach to Fiduccia-Mattheyses (FM)-based iterative partitioning. We combine two concepts: (1) problem reduction using clustering and the two-phase FM methodology and (2) adaptive multistart, i.e. the intelligent selection of starting points for the iterative optimization, based on the results of previous optimizations. The resulting clustered adaptive multistart (CAMS) methodology substantially improves upon previous partitioning results in the literature, for both unit module areas and actual module areas, and for both the min-cut bisection and minimum ratio cut objectives. The CAMS method is surprisingly fast and has very stable solution quality, even for large benchmark instances. It has been applied as the basis of a clustering methodology within an industry placement tool.