Large-Step Markov Chain Variants for VLSI Netlist Partitioning

We examine the utility of the Large-Step Markov Chain (LSMC) technique [13], a variant of the iterated descent heuristic of Baum [2], for VLSI netlist bipartitioning. LSMC iteratively nds a local optimum solution according to some greedy search (in our case, the Fiduccia-Mattheyses heuristic) and then perturbs this local optimum via a \kick move " into the starting solution of the next greedy descent. We empirically evaluate several intuitive types of kick moves to determine which is best suited to the VLSI netlist biparti-tioning domain. Experiments show that LSMC with an ap-propriately chosen kick move can yield results that are com-petitive with the best known results in the literature. On-going work examines the variation of the optimal kick move with the underlying partitioning engine. Since LSMC can itself be viewed as a \partitioning engine", other research directions include the use of LSMC within hybrid-genetic and two-phase approaches. 1