research-article

High-performance routing at the nanometer scale

Authors:

Igor L. MarkovAuthors Info & Claims

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

Pages 496 - 502

Published: 05 November 2007 Publication History

Abstract

In this work we describe significant improvements to core routing technologies and outperform the best results from the ISPD '07 Global Routing Contest, as well as previous literature, in terms of route completion, runtime and total wirelength. In particular, our router, FGR, improves upon wirelengths produced by BoxRouter and MaizeRouter in March 2007 by 9.9% and 8.4%, respectively. Additionally, we reveal the mathematical basis of negotiated-congestion routing, offer comprehensive analysis of existing routing techniques and discuss several applications at the nanometer scale.

References

[1]

S. N. Adya, I. L. Markov and P. G. Villarrubia, "On Whitespace and Stability in Physical Synthesis," Integration: the VLSI Journal 39(4), pp. 340--362, 2006.

Digital Library

[2]

C. Albrecht, "Global Routing by New Approximations for Multicom-modity Flow," IEEE TCAD 20(5), pp. 622--632, 2001.

Digital Library

[3]

E. Bozorgzadeh, R. Kastner and M. Sarrafzadeh, "Creating and Exploiting Flexibility in Rectilinear Steiner Trees," IEEE TCAD 22(5), pp. 605--615, 2003.

Digital Library

[4]

M. Cho and D. Z. Pan, "BoxRouter: A New Global Router Based on Box Expansion and Progressive ILP," In Proc. DAC, pp. 373--378, 2006.

Digital Library

[5]

M. Cho, H. Xiang, R. Puri and D. Z. Pan, "Wire Density Driven Global Routing for CMP Variation and Timing," In Proc. ICCAD, pp. 487--492, 2006.

Digital Library

[6]

C. C. N. Chu and Y.-C. Wong, "Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design," In Proc. ISPD, pp. 28--35, 2005.

Digital Library

[7]

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.

Digital Library

[8]

W. A. Dees, Jr. and P. G. Karger, "Automated Rip-up and Reroute Techniques," In Proc. DAC, pp. 432--439, 1982.

Digital Library

[9]

R. Goering, "IC Routing Contest Boosts CAD Research," EE Times, March 22, 2007. http://www.eetimes.com/showArticle.jhtml?articleID=198500084

[10]

R. Hadsell and P. H. Madden, "Improved Global Routing through Congestion Estimation," In Proc. DAC, pp. 28--34, 2003.

Digital Library

[11]

J. Hu and S. S. Sapatnekar, "A Survey on Multi-net Global Routing for Integrated Circuits," Integration, the VLSI Journal 31(1), pp. 1--49, 2001.

[12]

ISPD 1998 Global Routing benchmark suite. http://www.ece.ucsb.edu/?kastner/labyrinth

[13]

ISPD 2007 Global Routing Contest and benchmark suite. http://www.sigda.org/ispd2007/rcontest/

[14]

A. B. Kahng, I. I. Mandoiu and A. Zelikovsky, "Highly Scalable Algorithms for Rectilinear and Octilinear Steiner Trees," In Proc. ASP-DAC, pp. 827--833, 2003.

Digital Library

[15]

R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh, "Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling," IEEE TCAD 21(7), pp. 777--790, 2002.

Digital Library

[16]

Lagrange multipliers. http://en.wikipedia.org/wiki/Lagrange_multipliers

[17]

K.-Y. Lee and T.-C. Wang, "Post-routing Redundant Via Insertion for Yield/Reliability Improvement," In Proc. ASP-DAC, pp. 303--308, 2006.

Digital Library

[18]

C.-W. Lin et. al., "Recent Research and Emerging Challenges in Physical Design for Manufacturability/Reliability," In Proc. ASP-DAC, pp. 238--243, 2007.

[19]

C.-W. Lin et. al., "Efficient Obstacle-avoiding Rectilinear Steiner Tree Construction," In Proc. ISPD, pp. 127--134, 2007.

Digital Library

[20]

D. McGrath, "Routing Technology Came from Within Cadence, execs say," EE Times, Sept. 8, 2006. http://www.eetimes.com/showArticle.jhtml?articleID=192700243

[21]

L. McMurchie and C. Ebeling, "PathFinder: A Negotiation-based Performance-driven Router for FPGAs," In Proc. FPGA, 1995.

Digital Library

[22]

M. Moffitt, Personal communication, March 2007.

[23]

M. Pan and C. Chu, "FastRoute: A Step to Integrate Global Routing into Placement," In Proc. ICCAD, pp. 464--471, 2006.

Digital Library

[24]

M. Pan and C. Chu, "FastRoute 2.0: A High-quality and Efficient Global Router," In Proc. ASP-DAC, pp. 250--255, 2007.

Digital Library

[25]

H. Ren, D. Z. Pan and P. G. Villarubia, "True Crosstalk Aware Incremental Placement with Noise Map," In Proc. ICCAD, pp. 402--409, 2004.

Digital Library

[26]

J. A. Roy and I. L. Markov, "Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement," IEEE TCAD 26(4), pp. 632--644, 2007.

Digital Library

[27]

L. K. Scheffer, "Physical CAD Changes to Incorporate Design for Lithography and Manufacturability," In Proc. ASP-DAC, pp. 768--773, 2004.

Digital Library

[28]

Z. Shen, C. C. N. Chu and Y. M. Li, "Efficient Rectilinear Steiner Tree Construction with Rectilinear Blockages," In Proc. ICCD, pp. 38--44, 2005.

Digital Library

[29]

K. So, "Solving Hard Instances of FPGA Routing with a Congestion-Optimal Restrained-Norm Path Search Space," In Proc. ISPD, pp. 151--158, 2007.

Digital Library

[30]

P. V. Srinivas et. al., "System and Method for Estimating Capacitance of Wires Based on Congestion Information," U.S. Patent 6519745, filed May 26, 2000, issued Feb. 11, 2003.

[31]

D. C. Wang, "Method for Estimating Routability and Congestion in a Cell Placement for Integrated Circuit Chip," U.S. Patent 5587923, filed Sept. 7, 1994, issued Dec. 24, 1996.

[32]

J. Westra, C. Bartels and P. Groeneveld, "Probabilistic Congestion Prediction," In Proc. ISPD, pp. 204--209, 2004.

Digital Library

[33]

J. Westra and P. Groeneveld, "Is Probabilistic Congestion Estimation Worthwhile?", In Proc. SLIP, pp. 99--106, 2005.

Digital Library

Cited By

Samanta RErzin ARaha SShamardin YTakhonov IZalyubovskiy V(2015)A provably tight delay-driven concurrently congestion mitigating global routing algorithmApplied Mathematics and Computation10.1016/j.amc.2014.11.062255:C(92-104)Online publication date: 15-Mar-2015
https://dl.acm.org/doi/10.1016/j.amc.2014.11.062
Hsu MKatta NLin HLin KTam KWang KChang Y(2014)Design and manufacturing process co-optimization in nano-technologyProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691480(574-581)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691480
Kahng ALee HLi JCavallaro JZhang TJones ALi H(2014)Horizontal benchmark extension for improved assessment of physical CAD researchProceedings of the 24th edition of the great lakes symposium on VLSI10.1145/2591513.2591540(27-32)Online publication date: 20-May-2014
https://dl.acm.org/doi/10.1145/2591513.2591540
Show More Cited By

Recommendations

High-Performance Routing at the Nanometer Scale

In this paper, we describe significant improvements to core routing technologies and outperform the best results from the International Symposium on Physical Design 2007 Global Routing Contest and the International Conference on Computer-Aided Design ...
Nanometer-scale standard cell library for enhanced redundant via1 insertion rate
GLSVLSI '11: Proceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI

Despite the rapid advances in process technology, via failure is still problematic in nanometer-scale semiconductor manufacturing. Adding redundant vias is the typical approach for improving yield and reliability. Standard cells are essential for ...
Crosstalk- and performance-driven multilevel full-chip routing

In this paper, we propose a novel framework for fast multilevel routing considering crosstalk and performance optimization. To handle the crosstalk minimization problem, we incorporate an intermediate stage of layer/track assignment into the multilevel ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

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

Upcoming Conference

ICCAD '24

Sponsor:
sigda

IEEE/ACM International Conference on Computer-Aided Design

October 27 - 31, 2024

New York , NY , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
304
Total Downloads

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

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Samanta RErzin ARaha SShamardin YTakhonov IZalyubovskiy V(2015)A provably tight delay-driven concurrently congestion mitigating global routing algorithmApplied Mathematics and Computation10.1016/j.amc.2014.11.062255:C(92-104)Online publication date: 15-Mar-2015
https://dl.acm.org/doi/10.1016/j.amc.2014.11.062
Hsu MKatta NLin HLin KTam KWang KChang Y(2014)Design and manufacturing process co-optimization in nano-technologyProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691480(574-581)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691480
Kahng ALee HLi JCavallaro JZhang TJones ALi H(2014)Horizontal benchmark extension for improved assessment of physical CAD researchProceedings of the 24th edition of the great lakes symposium on VLSI10.1145/2591513.2591540(27-32)Online publication date: 20-May-2014
https://dl.acm.org/doi/10.1145/2591513.2591540
Wei YLi ZSze CHu SAlpert CSapatnekar SMacii E(2013)CATALYSTProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485728(1873-1878)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485728
Yan TMa QChilstedt SWong MChen D(2013)A routing algorithm for graphene nanoribbon circuitACM Transactions on Design Automation of Electronic Systems10.1145/250505618:4(1-18)Online publication date: 25-Oct-2013
https://dl.acm.org/doi/10.1145/2505056
Pan MXu YZhang YChu C(2012)FastRouteVLSI Design10.1155/2012/6083622012(14-14)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1155/2012/608362
Zhang YChu CGroeneveld PSciuto DHassoun S(2012)GDRouterProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228469(597-602)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228469
Han SJeong KKahng ALu J(2011)Stability and scalability in global routingProceedings of the System Level Interconnect Prediction Workshop10.5555/2134224.2134235(1-6)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.5555/2134224.2134235
Han YAncajas DChakraborty KRoy SPhillips JHu AGraeb H(2011)Exploring high throughput computing paradigm for global routingProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132400(298-305)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132400
Xu YChu CPhillips JHu AGraeb H(2011)MGRProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132385(250-255)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132385
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents