VLSI circuit partitioning by cluster-removal using iterative improvement techniques

Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm 3 and Kr-ishnamurthys 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.