EFFICIENT BIPARTITIONING ALGORITHM FOR SIZE-CONSTRAINED CIRCUITS

A novel module-migration bipartitioner (MMP) for VLSI circuits is prop osed. MMP uses an efficient module migration process, which can relax the size constraints temporarily and intensify the capability of escap ing from local optima, as its iterative improvement mechanism. Besides evaluating the same module gain when performing the Fiduccia-Mattheys es (FM) algorithm for selecting the module to move, MMP also examines the connection strengths between modules, thus capturing more global i mplications of module moving. Moreover, MMP is robust with a self-adju sted probabilistic function set which can reduce the sensitivity of so me key parameters. Experiments on circuits allowing different deviatio ns from exact bipartition show that MMP is stable on solution quality and that it not only performs much better than FM, but also outperform s many state-of-the-art bipartitioners.