NDLI: UTACO: a unified timing and congestion optimization algorithm for standard cell global routing

Content Provider	IEEE Xplore Digital Library
Author	Tong Jing Xian-Long Hong Jing-Yu Xu Hai-Yun Bao Chung-Kuan Cheng Jun Gu
Copyright Year	1982
Abstract	Timing performance and routability are two main goals of global routing. These two targets are mutually conflicting if we view and handle their effects independently. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. We formulate global routing as a multicommodity flow problem. The objective function is the slack of congestion with the clock period as the delay limit from registers and inputs to registers and outputs. The multicommodity flow is expressed by a linear-programming formulation as a primal problem. We then convert the primal problem into a dual formulation using the shadow price as the variables. The shadow price of a net is the sum of its congestion price and timing price. The primal and dual formulation offers theoretical upper and lower bounds of the routing solution. Throughout the optimization process, the difference of the two bounds reduces, which provides the user's insight into the quality of the solutions. Based on the new formulation, this paper presents the UTACO algorithm for standard cell global routing.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	358
Ending Page	365
Page Count	8
File Size	304370
File Format	PDF
ISSN	02780070
Volume Number	23
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-03-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	Timing Routing Costs Delay Clocks Computer science Very large scale integration Wire Optimization Joining processes
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

Zero skew clock-tree optimization with buffer insertion/sizing and wire sizing

TIGER: an efficient timing-driven global router for gate array and standard cell layout design

A timing-constrained simultaneous global routing algorithm

Timing optimization on routed designs with incremental placement and routing characterization

Single-layer global routing

Wire width planning for interconnect performance optimization

Optimal wiresizing under Elmore delay model

An adaptive timing-driven placement for high performance VLSIs

Timing and area optimization for standard-cell VLSI circuit design

UTACO: a unified timing and congestion optimization algorithm for standard cell global routing

Similar Documents

Zero skew clock-tree optimization with buffer insertion/sizing and wire sizing

TIGER: an efficient timing-driven global router for gate array and standard cell layout design

A timing-constrained simultaneous global routing algorithm

Timing optimization on routed designs with incremental placement and routing characterization

Single-layer global routing

Wire width planning for interconnect performance optimization

Optimal wiresizing under Elmore delay model

An adaptive timing-driven placement for high performance VLSIs

Timing and area optimization for standard-cell VLSI circuit design

UTACO: a unified timing and congestion optimization algorithm for standard cell global routing