Probability-based approaches to VLSI circuit partitioning

Authors
Citation
S. Dutt et Wy. Deng, Probability-based approaches to VLSI circuit partitioning, IEEE COMP A, 19(5), 2000, pp. 534-549
Citations number
36
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Eletrical & Eletronics Engineeing
Journal title
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
ISSN journal
0278-0070 → ACNP
Volume
19
Issue
5
Year of publication
2000
Pages
534 - 549
Database
ISI
SICI code
0278-0070(200005)19:5<534:PATVCP>2.0.ZU;2-O
Abstract
Iterative-improvement two-way min-cut partitioning is an important phase in most circuit placement tools, and finds use in many other computer-aided d esign (CAD) applications. Most iterative improvement techniques for circuit netlists like the Fiduccia-Mattheyses (FM) method compute the gains of nod es using local netlist information that is only concerned with the immediat e improvement in the cutset, This can lead to misleading gain information. Krishnamurthy suggested a lookahead (LA) gain calculation method to amelior ate this situation; however, as we show, it leaves room for improvement. We present here a probabilistic gain computation approach called probabilisti c partitioner (PROP) that is capable of capturing the future implications o f moving a node at the current time. We also propose an extended algorithm SHRINK-PROP that increases the provability of removing recently "perturbed" nets (nets whose nodes have been moved for the first time) from the cutset , Experimental results on medium- to large-size ACM/SIGDA benchmark circuit s show that PROP and SHRINK-PROP outperform previous iterative-improvement methods like FM (bq. about 30% and 37%, respectively) and LA (by about 27% and 34%, respectively). Both PROP and SHRINK-PROP also obtain much better c utsizes than many recent state-of-the-art partitioners like EIG1, WINDOW ME LO, PARABOLI, GFM and CMetis (by 4.5% to 67%). Our empirical timing results reveal that PROP is appreciably Faster than most recent techniques, We als o obtain results on the more recent ISPD-98 benchmark suite that show simil ar substantial mincut improvements by PROP and SHRINK-PROP over FM (24% and 31%, respectively). it is also noteworthy that SHRINK-PROP's results are w ithin 2.5% of those obtained by hMetis. one of the best multilevel partitio ners. However. the multilevel paradigm is orthogonal to SHRINK-PROP. Furthe r, since it is a "flat" partitioner, it has advantages over hMetis in parti tion-driven placement applications.