Adaptive Methods for Netlist Partitioning

An algorithm that remains in use at the core of many partitioning systems is the Kernighan-Lin algorithm and a variant the Fidducia-Matheysses (FM) algorithm. To un-derstand the FM algorithm we applied principles of data engineering where visualization and statistical analysis are used to analyze the run-time behavior. We identified two improvements to the algorithm which, without clus-tering or an improved heuristic function, bring the perfor-mance of the algorithm near that of more sophisticated al-gorithms. One improvement is based on the observation, explored empirically, that the full passes in the FM algo-rithm appear comparable to a stochastic local restart in the search. We motivate this observation with a discussion of recent improvements in Monte Carlo Markov Chain meth-ods in statistics. The other improvement is based on the ob-servation that when an FM-like algorithm is run 20 times and the best run chosen, the performance trace of the al-gorithm on earlier runs is useful data for learning when to abort a later run. These improvements, implemented with a simple adaptive scheme, are orthogonal to techniques used in state-of-the-art implementations, and therefore should be applicable to other VLSI optimization algorithms.