NDLI: Effective partition-driven placement with simultaneous level processing and global net views

Content Provider	IEEE Xplore Digital Library
Author	Ke Zhong Dutt, S.
Copyright Year	2000
Description	Author affiliation: Dept. of Electr. Eng. & Comput. Sci., Illinois Univ., Chicago, IL, USA (Ke Zhong)
Abstract	In this paper we take a fresh look at the partition-driven placement (PDP) paradigm for standard-cell placement for wire-length minimization. The goal is to develop several new algorithms for incorporation into a PDP framework that can rectify the well-known drawbacks of traditional PDP (increasingly localized view of nets with increasing levels of the partitioning tree, min cut objective, inaccuracy and cost of terminal propagation (TP), irreversibility of move decisions), while preserving its considerable advantages (time efficiency, flexibility in accurately incorporating many optimization metrics, and flexibility in satisfying most constraints). We have developed several novel techniques within a PDP-based framework that yield the best wire-length results so far on all but two of the MONO benchmark suite. Our major innovations are: (1) simultaneous level partitioning (SLP) in which we partition the entire circuit globally in every level of the partitioning tree, across the current cutline(s); (2) cell gain computation based on a global or distributed view of entire nets (thus obviating TP) and on the bounding-box (BB) minimization of nets (as opposed to mincut in prior PDP); (3) move irreversibility tackled in a pest-processing phase via vertical and horizontal swaps. Empirical results indicate that our PDP algorithm SPADE (for Simultaneous level Partitioning with Distributed lie., global] nEt views) provides almost 202 better wirelength results than an internal version of "regular" PDP with min-cut based gains, 10.8% better than the previous best PDP method QUAD, 10.6% better than TimberWolf (TW) 7.0, 15.846 better than the state-of-the-art force-directed technique from U. Munich (termed FD-98 here), and 15.3% better than the multilevel placement technique Snap-On. Besides TW7.0, we are also the only ones to report results on the approximately 100 K-cell circuit golem3 (12.2% better than TW7.0). Our run times are quite reasonable.
Starting Page	254
Ending Page	259
File Size	851403
Page Count	6
File Format	PDF
ISBN	0780364457
ISSN	10923152
DOI	10.1109/ICCAD.2000.896482
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2000-11-05
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Circuits Partitioning algorithms Constraint optimization Cost function Technological innovation Distributed computing Minimization Very large scale integration Delay Crosstalk
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications 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

An effective congestion-driven placement framework

Reporting of standard cell placement results

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

Performance-driven macrocell placement

VLSI placement using uncertain costs

Timing-driven partitioning-based placement for island style FPGAs

Optimal circuit clustering for delay minimization under a more general delay model

A new timing-driven standard cell placement algorithm

A novel timing-driven placement using genetic algorithm

Effective partition-driven placement with simultaneous level processing and global net views

Similar Documents

An effective congestion-driven placement framework

Reporting of standard cell placement results

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

Performance-driven macrocell placement

VLSI placement using uncertain costs

Timing-driven partitioning-based placement for island style FPGAs

Optimal circuit clustering for delay minimization under a more general delay model

A new timing-driven standard cell placement algorithm

A novel timing-driven placement using genetic algorithm

Effective partition-driven placement with simultaneous level processing and global net views