NDLI: Track Routing and Optimization for Yield

Content Provider	IEEE Xplore Digital Library
Author	Minsik Cho Hua Xiang Puri, R. Pan, D.Z.
Copyright Year	1982
Abstract	In this paper, we propose track routing and optimization for yield (TROY), the first track router for the optimization of yield loss due to random defects. As the probability of failure (POF), which is an integral of the critical area and the defect size distribution, strongly depends on wire ordering, sizing, and spacing, track routing can play a key role in effective wire planning for yield optimization. However, a straightforward formulation of yield-driven track routing can be shown to be integer nonlinear programming, which is a nondeterministic polynomial-time complete problem. TROY overcomes the computational complexity by combining two effective techniques, i.e., the minimum Hamiltonian path (MHP) from graph theory and the second-order cone programming (SOCP) from mathematical optimization. First, TROY performs wire ordering to minimize the critical area for short defects by finding an MHP. Then, TROY carries out optimal wire sizing/spacing through SOCP optimization based on the given wire order. Since the SOCP can be optimally solved in near linear time, TROY efficiently achieves globally optimal wire sizing/spacing for the minimal POF.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	872
Ending Page	882
Page Count	11
File Size	1103511
File Format	PDF
ISSN	02780070
Volume Number	27
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-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	Routing Wire Polynomials Computational complexity Graph theory Mathematical programming Very large scale integration Production facilities Fabrication Yield estimation yield Minimum Hamiltonian path (MHP) physical design random defects second-order cone programming (SOCP) track routing
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

Single-layer global routing

On multiterminal single bend wirability

Channel density reduction by routing over the cells

Conflict-free channel definition in building-block layout

Spanning graph-based nonrectilinear steiner tree algorithms

Channel density reduction by routing over the cells

BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP

Hierarchical Wire Routing

COP: a Crosstalk OPtimizer for gridded channel routing

Track Routing and Optimization for Yield

Similar Documents

Single-layer global routing

On multiterminal single bend wirability

Channel density reduction by routing over the cells

Conflict-free channel definition in building-block layout

Spanning graph-based nonrectilinear steiner tree algorithms

Channel density reduction by routing over the cells

BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP

Hierarchical Wire Routing

COP: a Crosstalk OPtimizer for gridded channel routing

Track Routing and Optimization for Yield