NDLI: Probability-based approaches to VLSI circuit partitioning

Content Provider	IEEE Xplore Digital Library
Author	Dutt, S. Wenyong Deng
Copyright Year	1982
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 design (CAD) applications. Most iterative improvement techniques for circuit netlists like the Fiduccia-Mattheyses (FM) method compute the gains of nodes using local netlist information that is only concerned with the immediate improvement in the cutset. This can lead to misleading gain information. Krishnamurthy suggested a lookahead (LA) gain calculation method to ameliorate this situation; however, as we show, it leaves room for improvement. We present here a probabilistic gain computation approach called probabilistic partitioner (PROP) that is capable of capturing the future implications of moving a node at the current time. We also propose an extended algorithm SHRINK-PROP that increases the probability 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 circuits show that PROP and SHRINK-PROP outperform previous iterative-improvement methods like FM (by about 30% and 37%, respectively) and LA (by about 27% and 34%, respectively). Both PROP and SHRINK-PROP also obtain much better cutsizes than many recent state-of-the-art partitioners like EIG1, WINDOW, MELO, PARABOLI, GFM and GMetis (by 4.5% to 67%), Our empirical timing results reveal that PROP is appreciably faster than most recent techniques. We also obtain results on the more recent ISPD-98 benchmark suite that show similar substantial mincut improvements by PROP and SHRINK-PROP over FM (24% and 31%, respectively). It is also noteworthy that SHRINK-PROP'S results are within 2.5% of those obtained by hMetis, one of the best multilevel partitioners. However, the multilevel paradigm is orthogonal to SHRINK-PROP. Further, since it is a "flat" partitioner, it has advantages over hMetis in partition-driven placement applications.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	534
Ending Page	549
Page Count	16
File Size	452441
File Format	PDF
ISSN	02780070
Volume Number	19
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-05-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Very large scale integration Design automation Timing Circuit testing Application software Iterative methods Partitioning algorithms Iterative algorithms Large scale integration Integrated circuit interconnections
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A connectivity based clustering algorithm with application to VLSI circuit partitioning

Path-Based Buffer Insertion

An efficient algorithm for VLSI network partitioning problem using a cost function with balancing factor

Legalizing a placement with minimum total movement

MARS-a multilevel full-chip gridless routing system

Net Cluster: A Net-Reduction-Based Clustering Preprocessing Algorithm for Partitioning and Placement

Multiway VLSI circuit partitioning based on dual net representation

Partitioning using second-order information and stochastic-gain functions

Hypergraph partitioning with fixed vertices [VLSI CAD]

Probability-based approaches to VLSI circuit partitioning

Similar Documents

A connectivity based clustering algorithm with application to VLSI circuit partitioning

Path-Based Buffer Insertion

An efficient algorithm for VLSI network partitioning problem using a cost function with balancing factor

Legalizing a placement with minimum total movement

MARS-a multilevel full-chip gridless routing system

Net Cluster: A Net-Reduction-Based Clustering Preprocessing Algorithm for Partitioning and Placement

Multiway VLSI circuit partitioning based on dual net representation

Partitioning using second-order information and stochastic-gain functions

Hypergraph partitioning with fixed vertices [VLSI CAD]

Probability-based approaches to VLSI circuit partitioning