Article

Optimizing yield in global routing

Author:

Dirk MüllerAuthors Info & Claims

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

Pages 480 - 486

https://doi.org/10.1145/1233501.1233598

Published: 05 November 2006 Publication History

Get Access

Abstract

We present the first efficient approach to global routing that takes spacing-dependent costs into account and provably finds a near-optimum solution including these costs. We show that this algorithm can be used to optimize manufacturing yield. The core routine is a parallelized fully polynomial approximation scheme, scaling very well with the number of processors. We present results showing that our algorithm reduces the expected number of defects in wiring by more than 10 percent on state-of-the-art industrial chips.

References

[1]

C. Albrecht, "Global routing by new approximation algorithms for multicommodity flow", in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 20, pp. 622--632, 2001.

Digital Library

Google Scholar

[2]

R. C. Carden IV, J. Li and C.-K. Cheng, "A global router with a theoretical bound on the optimum solution", in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 15, pp. 208--216, 1996.

Digital Library

Google Scholar

[3]

S. E. Dreyfus and R. A. Wagner, "The Steiner problem in graphs", in Networks, vol. 1, pp. 195--207, 1972.

Crossref

Google Scholar

[4]

N. Garg and J. Könemann, "Faster and simpler algorithms for multicommodity flow and other fractional packing problems", in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 300--309, 1998.

Digital Library

Google Scholar

[5]

T.-Y. Ho, Y.-W. Chang, S.-J. Chen and D.-T. Lee, "A fast crosstalk-and performance-driven multilevel routing system", in Proceedings of the IEEE international Conference on Computer-Aided Design, Nov. 2003.

Digital Library

Google Scholar

[6]

J. Hu and S. S. Sapatnekar, "A survey on multi-net global routing for integrated circuits", in Integration, the VLSI Journal, vol. 31, pp. 1--49, 2001.

Google Scholar

[7]

T. Jing, X. Hong, H. Bao, Y. Cai, J. Xu, C. Cheng and J. Gu, "Utaco: A unified timing and congestion optimizing algorithm for standard cell global routing", in Proceedings of the Asia and South Pacific Design Automation Conference, pp. 834--839, 2003.

Digital Library

Google Scholar

[8]

W. Maly, "Modeling of lithography related yield losses for CAD of VLSI circuits", IEEE Transactions on Computer-Aided Design, vol. CAD-4, pp. 166--177, July 1985.

Google Scholar

[9]

P. Raghavan, "Randomized rounding and discrete ham-sandwich theorems: provably good algorithms for routing and packing problems", Ph.D. thesis, Report No. UCB/CSD 87/312, University of California, Berkeley, 1986.

Digital Library

Google Scholar

[10]

P. Raghavan and C. D. Thompson, "Randomized rounding: a technique for provably good algorithms and algorithmic proofs", in Combinatorica, vol. 7, pp. 365--374, 1987.

Digital Library

Google Scholar

[11]

F. Shahrokhi and D. W. Matula, "The maximum concurrent flow problem", in Journal of the ACM, vol. 37, pp. 318--334, 1990.

Digital Library

Google Scholar

[12]

J. Vygen, "Near Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption", in Integer Programming and Combinatorial Optimization; Proceedings of the 10th International IPCO Conference; LNCS 3064 (G. Nemhauser, D. Bienstock, eds.), pp. 308--324, Springer, Berlin 2004,

Google Scholar

[13]

J. Xu, X. Hong, T. Jing, Y. Cai and J. Gu, "A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design", in Proceedings of the Asia and South Pacific Design Automation Conference, pp. 847--850, 2003.

Digital Library

Google Scholar

Cited By

View all

Held SMüller DRotter DTraub VVygen JMarculescu DLiu F(2015)Global Routing with Inherent Static Timing ConstraintsProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840834(102-109)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840834
Gester MMüller DNieberg TPanten CSchulte CVygen J(2013)BonnRouteACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210318:2(1-24)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442103
Gester MMüller DNieberg TPanten CSchulte CVygen JGroeneveld PSciuto DHassoun S(2012)Algorithms and data structures for fast and good VLSI routingProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228441(459-464)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228441
Show More Cited By

Index Terms

Optimizing yield in global routing

Recommendations

A Multithreaded Initial Detailed Routing Algorithm Considering Global Routing Guides
2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
Detailed routing is the most complicated and time-consuming stage in VLSI design and has become a critical process for advanced node enablement. To handle the high complexity of modern detailed routing, initial detailed routing is often employed to ...
The ISPD global routing benchmark suite
ISPD '08: Proceedings of the 2008 international symposium on Physical design

This paper describes the ISPD global routing benchmark suite and related contests. Total 16 global routing benchmarks are produced from the ISPD placement contest benchmark suite using a variety of publicly available academic placement tools. The ...
Geometry Independent Wirelength Estimation Method in VLSI Routing
VLSID '13: Proceedings of the 2013 26th International Conference on VLSI Design and 2013 12th International Conference on Embedded Systems

VLSI routing imposes a major challenge with shrinking dimension and enhanced functionality of a chip. In this paper, we propose a partition driven wire length estimation technique that generates routing solution without any prior knowledge of placement, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Held SMüller DRotter DTraub VVygen JMarculescu DLiu F(2015)Global Routing with Inherent Static Timing ConstraintsProceedings of the IEEE/ACM International Conference on Computer-Aided Design10.5555/2840819.2840834(102-109)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.5555/2840819.2840834
Gester MMüller DNieberg TPanten CSchulte CVygen J(2013)BonnRouteACM Transactions on Design Automation of Electronic Systems10.1145/2442087.244210318:2(1-24)Online publication date: 11-Apr-2013
https://dl.acm.org/doi/10.1145/2442087.2442103
Gester MMüller DNieberg TPanten CSchulte CVygen JGroeneveld PSciuto DHassoun S(2012)Algorithms and data structures for fast and good VLSI routingProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228441(459-464)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228441
Hu JRoy JMarkov ISaxena PChang Y(2010)Completing high-quality global routesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735035(35-41)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.1145/1735023.1735035
Cho MYuan KBan YPan D(2009)ELIADIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201887628:7(1006-1016)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2018876
Pan DCho MKyung CChoi KHa S(2008)Synergistic physical synthesis for manufacturability and variability in 45nm designs and beyondProceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356860(220-225)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356860
Cho MYuan KBan YPan DFix L(2008)ELIADProceedings of the 45th annual Design Automation Conference10.1145/1391469.1391598(504-509)Online publication date: 8-Jun-2008
https://dl.acm.org/doi/10.1145/1391469.1391598
Moffitt MRoy JMarkov IPan DNam G(2008)The coming of age of (academic) global routingProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353662(148-155)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353662
Ozdal MWong MGielen G(2007)ArcherProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326174(488-495)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326174
Sinha SChiang CGielen G(2007)A methodology for fast and accurate yield factor estimation during global routingProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326173(481-487)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326173
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Multithreaded Initial Detailed Routing Algorithm Considering Global Routing Guides

The ISPD global routing benchmark suite

Geometry Independent Wirelength Estimation Method in VLSI Routing