DocumentCode :
2250798
Title :
VLSI circuit partitioning by cluster-removal using iterative improvement techniques
Author :
Shantanu Dutt ; Wenyong Deng
Author_Institution :
Dept. of Electr. Eng., Minnesota Univ., Minneapolis, MN, USA
fYear :
1996
fDate :
10-14 Nov. 1996
Firstpage :
194
Lastpage :
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 :
VLSI; circuit layout CAD; computational complexity; integrated circuit testing; iterative methods; ACM/SIGDA benchmark circuits; CAD; Fiduccia-Mattheyses algorithm; VLSI circuit partitioning; cluster-removal; iterative improvement techniques; look-ahead algorithm; partition quality; spectral partitioner MELO; Central Processing Unit; Clustering algorithms; Integrated circuit interconnections; Iterative algorithms; Iterative methods; Logic design; Modems; Partitioning algorithms; Pins; Very large scale integration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer-Aided Design, 1996. ICCAD-96. Digest of Technical Papers., 1996 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA, USA
Print_ISBN :
0-8186-7597-7
Type :
conf
DOI :
10.1109/ICCAD.1996.569591
Filename :
569591
Link To Document :
بازگشت