research-article

Algorithms and data structures for fast and good VLSI routing

Authors:

Jens VygenAuthors Info & Claims

DAC '12: Proceedings of the 49th Annual Design Automation Conference

Pages 459 - 464

https://doi.org/10.1145/2228360.2228441

Published: 03 June 2012 Publication History

Get Access

Abstract

We present advanced data structures and algorithms for fast and high-quality global and detailed routing in modern technologies. Global routing is based on a combinatorial approximation scheme for min-max resource sharing. Detailed routing uses exact shortest path algorithms, based on a shape-based data structure for pin access and a two-level track-based data structure for long-distance connections. All algorithms are very fast. We demonstrate their superiority over traditional approaches by a comparison to an industrial router (on 32nm and 22nm chips). Our router is over two times faster, has 5% less netlength, 20% less vias, and reduces detours by more than 90%.

References

[1]

C. Alpert, Z. Li, M. Moffitt, G. Nam, J. Roy, and G. Tellez. What makes a design difficult to route. In Proc. ISPD, pages 7--12, 2010.

Digital Library

Google Scholar

[2]

C. Chu and Y.-C. Wong. FLUTE: Fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. Computer-Aided Design Integr. Circuits Syst., 27:70--83, 2008.

Digital Library

Google Scholar

[3]

A. Hetzel. A sequential detailed router for huge grid graphs. In Proc. DATE, pages 332--339, 1998.

Digital Library

Google Scholar

[4]

J. Humpola. Schneller Algorithmus für kürzeste Wege in irregulären Gittergraphen. Diploma Thesis, University of Bonn, 2009.

Google Scholar

[5]

B. Korte, D. Rautenbach, and J. Vygen. BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proc. IEEE, 95:555--572, 2007.

Crossref

Google Scholar

[6]

J. Maßberg and T. Nieberg. Rectilinear paths with minimum segment lengths. Discrete Appl. Math., to appear.

Google Scholar

[7]

D. Müller. Optimizing yield in global routing. In Proc. ICCAD, pages 480--486, 2006.

Digital Library

Google Scholar

[8]

D. Müller. Fast Resource Sharing in VLSI Routing. PhD thesis, University of Bonn, 2009.

Google Scholar

[9]

D. Müller, K. Radke, and J. Vygen. Faster min-max resource sharing in theory and practice. Math. Prog. Comp., 3:1--35, 2011.

Crossref

Google Scholar

[10]

T. Nieberg. Gridless pin access in detailed routing. In Proc. DAC, pages 170--175, 2011.

Digital Library

Google Scholar

[11]

S. Peyer, D. Rautenbach, and J. Vygen. A generalization of dijkstra's shortest path algorithm with applications to VLSI routing. J. Discrete Algorithms, 7:377--390, 2009.

Digital Library

Google Scholar

[12]

P. E. Hart and N. J. Nilsson and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 2:100--107, 1968.

Crossref

Google Scholar

[13]

J. Salowe. Rip-up and reroute. In C. Alpert, D. Mehta, and S. Sapatnekar, editors, Handbook of Algorithms for Physical Design Automation, pages 615--626. CRC Press, 2009.

Google Scholar

[14]

J. Vygen. Near-optimum global routing with coupling, delay bounds, and power consumption. In Proc. IPCO, pages 308--324, 2004.

Crossref

Google Scholar

Cited By

View all

Yao PZhang PZhu W(2023)Pathfinding Model and Lagrangian-Based Global Routing2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247969(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247969
Jia XCai YZhou QYu B(2018)A Multicommodity Flow-Based Detailed Router With Efficient Acceleration TechniquesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269327037:1(217-230)Online publication date: Jan-2018
https://doi.org/10.1109/TCAD.2017.2693270
Brazil MZachariasen MBrazil MZachariasen M(2015)Rectilinear Steiner TreesOptimal Interconnection Trees in the Plane10.1007/978-3-319-13915-9_3(151-218)Online publication date: 2015
https://doi.org/10.1007/978-3-319-13915-9_3
Show More Cited By

Index Terms

Algorithms and data structures for fast and good VLSI routing
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Very large scale integration design

Recommendations

Area-I/O flip-chip routing for chip-package co-design considering signal skews

The area-input/output (I/O) flip-chip package provides a high chip-density solution to the demand of more I/Os in very large scale integration designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In ...
A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs

Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct logical and/or technological problems in the circuit. ...
Full-Chip Routing Considering Double-Via Insertion

As the technology node advances into the nanometer era, via-open defects are one of the dominant failures due to the copper cladding process. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '12: Proceedings of the 49th Annual Design Automation Conference

June 2012

1357 pages

ISBN:9781450311991

DOI:10.1145/2228360

General Chair:
Patrick Groeneveld
Magma Design Automation, Inc., San Jose, CA
,
Program Chairs:
Donatella Sciuto
Politecnico di Milano, Milano, Italy
,
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]

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '12

Sponsor:

EDAC
SIGDA

DAC '12: The 49th Annual Design Automation Conference 2012

June 3 - 7, 2012

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
368
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yao PZhang PZhu W(2023)Pathfinding Model and Lagrangian-Based Global Routing2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247969(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247969
Jia XCai YZhou QYu B(2018)A Multicommodity Flow-Based Detailed Router With Efficient Acceleration TechniquesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.269327037:1(217-230)Online publication date: Jan-2018
https://doi.org/10.1109/TCAD.2017.2693270
Brazil MZachariasen MBrazil MZachariasen M(2015)Rectilinear Steiner TreesOptimal Interconnection Trees in the Plane10.1007/978-3-319-13915-9_3(151-218)Online publication date: 2015
https://doi.org/10.1007/978-3-319-13915-9_3
Jia XCai YZhou QChen GLi ZLi ZChang Y(2014)MCFRouteProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691446(397-404)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691446
Wei YSze CViswanathan NLi ZAlpert CReddy LHuber ATellez GKeller DSapatnekar S(2014)Techniques for scalable and effective routability evaluationACM Transactions on Design Automation of Electronic Systems10.1145/256666319:2(1-37)Online publication date: 28-Mar-2014
https://dl.acm.org/doi/10.1145/2566663
Jia XCai YZhou QChen GLi ZLi Z(2014)MCFRoute: A detailed router based on multi-commodity flow method2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2014.7001382(397-404)Online publication date: Nov-2014
https://doi.org/10.1109/ICCAD.2014.7001382
Zhang YChu C(2013)RegularRouteIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2012.221449121:9(1655-1668)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1109/TVLSI.2012.2214491
Chang FTsay RMak WChen S(2013)MANAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2013.226587832:10(1557-1568)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1109/TCAD.2013.2265878
MaíBerg JNieberg T(2013)Rectilinear paths with minimum segment lengthsDiscrete Applied Mathematics10.1016/j.dam.2011.12.003161:12(1769-1775)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.dam.2011.12.003

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

Area-I/O flip-chip routing for chip-package co-design considering signal skews

A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs

Full-Chip Routing Considering Double-Via Insertion