VLSI circuit partitioning by cluster-removal using iterative improvement techniques
Authors:
- Wenyong DengWDWenyong Deng
- 23 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 194-200
Abstract
Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm and Krishnamurthy's Look-Ahead (LA) algorithm are widely used in VLSI CAD applications largely due to their time efficiency 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. However, 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 and the spectral partitioner MELO by about 17% and 23%, respectively, with less CPU time. This demonstrates the potential of iterative improvement algorithms in dealing with the increasing complexity of modern VLSI circuitry.Keywords
This publication has 13 references indexed in Scilit:
- Timing driven placement2003
- New faster Kernighan-Lin-type graph-partitioning algorithms2002
- A fast algorithm for performance-driven placement2002
- On implementation choices for iterative improvement partitioning algorithms2002
- Spectral Partitioning: The More Eigenvectors, The BetterProceedings of the 39th conference on Design automation - DAC '02, 1995
- A fast and robust network bisection algorithmIEEE Transactions on Computers, 1995
- Partitioning very large circuits using analytical placement techniques1994
- A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design1993
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- A Linear-Time Heuristic for Improving Network Partitions1982