Article

FastRoute: a step to integrate global routing into placement

Authors:

Chris ChuAuthors Info & Claims

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

Pages 464 - 471

https://doi.org/10.1145/1233501.1233596

Published: 05 November 2006 Publication History

Abstract

Because of the increasing dominance of interconnect issues in advanced IC technology, placement has become a critical step in the IC design flow. To get accurate interconnect information during the placement process, it is desirable to incorporate global routing into it. However, previous global routers are computationally expensive. It is impractical to perform global routing repeatedly during placement.

In this paper, we present an extremely fast and high-quality global router called FastRoute. In traditional global routing approaches, congestion is not considered during Steiner tree construction. So they have to rely on the time-consuming maze routing technique to eliminate routing congestion. Different from traditional approaches, we proposed a congestion-driven Steiner tree topology generation technique and an edge shifting technique to determine the good Steiner tree topologies and Steiner node positions. Based on the congestion-driven Steiner trees, we only need to apply maze routing to a small percentage of the two-pin nets once to obtain high quality global routing solutions. We also proposed a new cost function based on logistic function to direct the maze routing.

Experimental results show that FastRoute generates less congested solutions in 132x and 64x faster runtimes than the state-of-the-art academic global routers Labyrinth [1] and Chi Dispersion router [2], respectively. It is even faster than the highly-efficient congestion estimator FaDGloR [3]. The promising results make it possible to incorporate global routing directly into placement process without much runtime penalty. This could dramatically improve the placement solution quality. We believe this work will fundamentally change the way the EDA community look at and make use of global routing in the whole design flow.

References

[1]

R. Kastner, E. Bozogzadeh, and M. Sarrafzadeh. Predictable routing. In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pp. 110--113, 2000.

Digital Library

[2]

R. T. Hadsell and P. H. Madden. Improved global routing through congestion estimation. In Proc. ACM/IEEE Design Automation Conf., pp. 28--31, 2003.

Digital Library

[3]

J. Westra and P. Groeneveld. Is probabilistic congestion estimation worthwhile? In Proc. Intl. Workshop on System-Level Interconnect Prediction, pp. 99--106, 2005.

Digital Library

[4]

B. Halpin, C. Y. R. Chen and N. Sehgal. Timing driven placement using physical net constraints. In Proc. ACM/IEEE Design Automation Conf., pp. 780--783, 2001.

Digital Library

[5]

H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proc. ACM/IEEE Design Automation Conf., pp. 269--274, 1998.

Digital Library

[6]

U. Brenner, A. Rohe. An effective congestion-driven placement framework. In IEEE Trans. on Computer-Aided Design, vol. 22(4), pp. 387--394, 2003.

Digital Library

[7]

A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection produce routable placements? In Proc. ACM/IEEE Design Automation Conf., pp. 477--482, 2000.

Digital Library

[8]

M. Wang, X. Yang, and M. Sarrafzadeh. Dragon2000: Standard-cell placement tool for large industry circuits. In Proc. IEEE/ACM Intl. Conf. on Computer-Aided Design, pp. 260--263, 2000.

Digital Library

[9]

C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 20:622--631, 2001.

Digital Library

[10]

B. M. Riess, and G. G. Ettelt. SPEED: fast and efficient timing driven placement. Proc. Intl. Symp. on Circuits and Systems, pp. 377--380, 1995.

[11]

W. Swartz and C. Sechen. Timing Driven Placement for Large Standard Cell Circuits. In Proc. ACM/IEEE Design Automation Conf., pp. 211--215, 1995.

Digital Library

[12]

X. Yang, B.-K. Choi, and M. Sarrafzadeh. Timing-driven placement using design hierarchy guided constraint generation. In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pp. 177--184, 2002.

Digital Library

[13]

G. Stem, B. M. Riess, B. Rohfleisch and F. M. Johannes. Timing driven placement in interaction with netlist transformations. Proc. Intl. Symp. on Physical Design, pp. 36--41, 1997.

Digital Library

[14]

J. Lou, S. Krishnamoorthy, and H. Sheng. Estimating routing congestion using probabilistic analysis. In Proc. Intl. Symp. on Physical Design, pp. 112--117, 2001.

Digital Library

[15]

J. Westra, C. Bartels, and P. Groeneveld. Probabilistic congestion prediction. In Proc. Intl. Symp. on Physical Design, pp. 204--209, 2004.

Digital Library

[16]

A. B. Kahng and X. Xu. Accurate pseudo-constructive wirelength and congestion estimation. In Proc. Intl. Workshop on System-Level Interconnect Prediction(SLIP), pp. 61--68, 2003.

Digital Library

[17]

R. W. Hamming. Error-detecting and error-correcting codes. Bell System Technical Journal, 29(2):147--160, 1950.

[18]

C. Chu, Y. Wong. Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design. In Proc. Intl. Symp. on Physical Design, pages 28--35, 2005.

Digital Library

[19]

M. Hanan. On Steiner's problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14:25--265, 1966.

[20]

D. von Seggern. CRC Standard Curves and Surfaces. Boca Raton, FL: CRC Press, 1993.

[21]

http://www.spec.org/

Cited By

Li WLiang RAgnesina AYang HHo CRajaram ARen HDe V(2024)DGR: Differentiable Global RouterProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3656530(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3656530
Liang RAgnesina ALiu WRen HHui-Ru Jiang IPosser G(2024)GPU/ML-Enhanced Large Scale Global Routing ContestProceedings of the 2024 International Symposium on Physical Design10.1145/3626184.3639693(269-274)Online publication date: 12-Mar-2024
https://dl.acm.org/doi/10.1145/3626184.3639693
Qi ZPeng QHu SYou H(2024)Effective Heterogeneous Graph Neural Network for Routing Congestion Prediction2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617734(369-373)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617734
Show More Cited By

Index Terms

FastRoute: a step to integrate global routing into placement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
  2. Hardware validation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

FastRoute: an efficient and high-quality global router

Modern large-scale circuit designs have created great demand for fast and high-quality global routing algorithms to resolve the routing congestion at the global level. Rip-up and reroute scheme has been employed by the majority of academic and ...
FastRoute 4.0: global router with efficient via minimization
ASP-DAC '09: Proceedings of the 2009 Asia and South Pacific Design Automation Conference

The number of vias generated during the global routing stage is a critical factor for the yield of final circuits. However, most global routers only approach the problem by charging a cost for vias in the maze routing cost function. In this paper, we ...
FastRoute 2.0: A High-quality and Efficient Global Router
ASP-DAC '07: Proceedings of the 2007 Asia and South Pacific Design Automation Conference

Because of the increasing dominance of interconnect issues in advanced IC technology, it is desirable to incorporate global routing into early design stages to get accurate interconnect information. Hence, high-quality and fast global routers are in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 2006 ACM.

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]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

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

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

61
Total Citations
View Citations
615
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li WLiang RAgnesina AYang HHo CRajaram ARen HDe V(2024)DGR: Differentiable Global RouterProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3656530(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3656530
Liang RAgnesina ALiu WRen HHui-Ru Jiang IPosser G(2024)GPU/ML-Enhanced Large Scale Global Routing ContestProceedings of the 2024 International Symposium on Physical Design10.1145/3626184.3639693(269-274)Online publication date: 12-Mar-2024
https://dl.acm.org/doi/10.1145/3626184.3639693
Qi ZPeng QHu SYou H(2024)Effective Heterogeneous Graph Neural Network for Routing Congestion Prediction2024 2nd International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA62518.2024.10617734(369-373)Online publication date: 10-May-2024
https://doi.org/10.1109/ISEDA62518.2024.10617734
Zou PCai ZLin ZMa CYu JChen J(2023)Incremental 3-D Global Routing Considering Cell Movement and Complex Routing ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321049342:6(2016-2029)Online publication date: Jun-2023
https://doi.org/10.1109/TCAD.2022.3210493
Liu SWang ZLiu FLin YYu BWong M(2023)Concurrent Sign-off Timing Optimization via Deep Steiner Points Refinement2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247794(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247794
Liu JYoung E(2023)EDGE: Efficient DAG-based Global Routing Engine2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247702(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247702
Kim SKim TBolchini CO'Connor IVerbauwhede IWille R(2022)Pin accessibility-driven placement optimization with accurate and comprehensive prediction modelProceedings of the 2022 Conference & Exhibition on Design, Automation & Test in Europe10.5555/3539845.3540031(778-783)Online publication date: 14-Mar-2022
https://dl.acm.org/doi/10.5555/3539845.3540031
Zang XWang FLiu JWong MMitra TYoung EXiong J(2022)ATLASProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549470(1-7)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549470
Baek KPark HKim SChoi KKim TMitra TYoung EXiong J(2022)Pin Accessibility and Routing Congestion Aware DRC Hotspot Prediction Using Graph Neural Network and U-NetProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549346(1-9)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549346
Fogaça MMonteiro EDanigno MOliveira IButzen PReis RXie Y(2020)Contributions to openroad from abroadProceedings of the 39th International Conference on Computer-Aided Design10.1145/3400302.3415737(1-8)Online publication date: 2-Nov-2020
https://dl.acm.org/doi/10.1145/3400302.3415737
Show More Cited By

View Options

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.

Figures

Tables

Media

View Table of Conten