VLSI Circuit Partitioning by ClusterRemoval Using Iterative Improvement Techniques

Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm [3] and Kr-ishnamurthy's Look-Ahead (LA) algorithm [4] are widely used in VLSI CAD applications largely due to their time effi-ciency and ease of implementation. This class of algorithms is of the “local improvement ” type. They generate relatively high quality results for small and medium size circuits. How-ever, as VLSI circuits become larger, these algorithms are not so effective on them as direct partitioning tools. We propose new iterative-improvement methods that select cells to move with a view to moving clusters that straddle the two subsets of a partition into one of the subsets. The new algorithms significantly improve partition quality while preserving the advantage of time efficiency. Experimental results on 25 medium to large size ACM/SIGDA benchmark circuits show up to 70 % improvement over FM in cutsize, with an average of per-circuit percent improvements of about 25%, and a total cut improvement of about 35%. They also outperform the recent placement-based partitioning tool Paraboli [13] and the spectral partitioner MELO [14] by about 17 % and 23%, respectively, with less CPU time. This demonstrates the po-tential of iterative improvement algorithms in dealing with the increasing complexity of modern VLSI circuitry. 1