Article

Probabilistic congestion prediction

Authors:

Jurjen Westra,

Chris Bartels,

Patrick GroeneveldAuthors Info & Claims

ISPD '04: Proceedings of the 2004 international symposium on Physical design

Pages 204 - 209

https://doi.org/10.1145/981066.981110

Published: 18 April 2004 Publication History

Get Access

Abstract

Congestion is a fundamental problem in VLSI design flows. Typically, it is handled by feeding back density information to the placers and routers. Fast and accurate congestion estimation is key in order to obtain a design flow with less iterations and higher predictability.Fast congestion prediction is based on an accurate approximation of the actual routing engine. In this paper we show experimentally that the number of two-pin nets with more than two bends in the actual router is negligible. It is also established that the ratio between the number of L-shapes and Z-shapes is more or less a constant.A fast and accurate algorithm for congestion prediction is developed. The above observations are translated into probabilities, that are used to "smear" out a net over its possible realizations. Extensive experimental evidence is provided using industrial designs.

References

[1]

H-M. Chen et al., "Integrated Floorplanning and Interconnect Plannig", International Conference on Computer Aided Design, pages 354--357, 1999.

Digital Library

Google Scholar

[2]

J. Cong and P. H. Madden, "Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs", Design Automation Conference, pages 356--361, 1998.

Digital Library

Google Scholar

[3]

R. T. Hadsell and P. H. Madden, "Improved Global Routing through Congestion Estimation", Design Automation Conference, pages 28--31, 2003.

Digital Library

Google Scholar

[4]

J. Lou, S. Krishnamoorthy and H. S. Sheng, "Estimating Routing Congestion using Probabilistic Analysis", International Symposium on Physical Design, pages 112--117, 2001.

Digital Library

Google Scholar

[5]

Y. Ma et al, "Dynamic Gobal Buffer Planning Optimization Based on Detail Block Locating and Congestion Analysis", Design Automation Conference, pages 806--811, 2003.

Digital Library

Google Scholar

[6]

Magma Design Automation, "Blast Chip 4.0 User Guide".

Google Scholar

[7]

P. N. Parakh, R. B. Brown and K. A. Sakallah, "Congestion Driven Quadratic Placement", Design Automation Conference, pages 275--278, 1998.

Digital Library

Google Scholar

[8]

M. Wang, X. Yang, K. Egoru and M. Sarrafzadeh, "Multi-center congestion estimation and minimization during placement", International Symposium on Physical Design, pages 147--152, 2000.

Digital Library

Google Scholar

[9]

X. Yang, R. Kastner and M. Sarrafzadeh, "Congestion Estimation During Top-down Placement", International Symposium on Physical Design, pages 164--169, 2001.

Digital Library

Google Scholar

Cited By

View all

Berndt AMeinhardt C(2024)CeConP: Exploring Node Centrality for Early Routing Congestion Prediction2024 IEEE 15th Latin America Symposium on Circuits and Systems (LASCAS)10.1109/LASCAS60203.2024.10506148(1-5)Online publication date: 27-Feb-2024
https://doi.org/10.1109/LASCAS60203.2024.10506148
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
Zhou ZPan YLemieux GIvanov A(2023)MEDUSA: A Multi-Resolution Machine Learning Congestion Estimation Method for 2D and 3D Global RoutingACM Transactions on Design Automation of Electronic Systems10.1145/359076828:5(1-25)Online publication date: 9-Sep-2023
https://dl.acm.org/doi/10.1145/3590768
Show More Cited By

Index Terms

Probabilistic congestion prediction
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Prediction and reduction of routing congestion
ISPD '06: Proceedings of the 2006 international symposium on Physical design

Routing congestion is a critical issue in deep submicron design technology and it becomes one of the most challenging problems in today's design flow. This paper presents a true probabilistic congestion prediction method based on router's intelligence ...
Physical hierarchy generation with routing congestion control
ISPD '02: Proceedings of the 2002 international symposium on Physical design

In this paper, we develop a multi-level physical hierarchy generation (mPG) algorithm integrated with fast incremental global routing for directly updating and optimizing congestion cost during placement. The fast global routing is achieved by using a ...
A congestion-driven placement framework with local congestion prediction
GLSVLSI '05: Proceedings of the 15th ACM Great Lakes symposium on VLSI

In this paper, we present a novel congestion-driven placement methodology. We analyze netlist structure and perform local congestion prediction to determine the amount of white space which will be attached to each cell. We place the modified netlist ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISPD '04: Proceedings of the 2004 international symposium on Physical design

April 2004

226 pages

ISBN:1581138172

DOI:10.1145/981066

General Chair:
Charles J. Alpert,
IBM
,
Program Chair:
Patrick Groeneveld
Eindhoven University

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: 18 April 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD04

Sponsor:

ISPD04: International Symposium on Physical Design 2004

April 18 - 21, 2004

Arizona, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

110
Total Citations
View Citations
941
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Berndt AMeinhardt C(2024)CeConP: Exploring Node Centrality for Early Routing Congestion Prediction2024 IEEE 15th Latin America Symposium on Circuits and Systems (LASCAS)10.1109/LASCAS60203.2024.10506148(1-5)Online publication date: 27-Feb-2024
https://doi.org/10.1109/LASCAS60203.2024.10506148
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
Zhou ZPan YLemieux GIvanov A(2023)MEDUSA: A Multi-Resolution Machine Learning Congestion Estimation Method for 2D and 3D Global RoutingACM Transactions on Design Automation of Electronic Systems10.1145/359076828:5(1-25)Online publication date: 9-Sep-2023
https://dl.acm.org/doi/10.1145/3590768
Hyun DKoh SJung YKim TShin Y(2023)Routability Optimization of Extreme Aspect Ratio Design through Non-uniform Placement Utilization and Selective Flip-flop StackingACM Transactions on Design Automation of Electronic Systems10.1145/357338728:4(1-19)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1145/3573387
Hung WChen YLin JYang YTsai CChao M(2023)DRC Violation Prediction After Global Route Through Convolutional Neural NetworkIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.327193231:9(1425-1438)Online publication date: Sep-2023
https://doi.org/10.1109/TVLSI.2023.3271932
Chen JKuang JZhao GHuang DYoung E(2023)PROS 2.0: A Plug-In for Routability Optimization and Routed Wirelength Estimation Using Deep LearningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.316825942:1(164-177)Online publication date: Jan-2023
https://doi.org/10.1109/TCAD.2022.3168259
Chen YSu MDing HWeng SLin ZBai X(2023)High-correlation 3D routability estimation for congestion-guided global routingThe Journal of Supercomputing10.1007/s11227-023-05553-080:3(3114-3141)Online publication date: 29-Aug-2023
https://doi.org/10.1007/s11227-023-05553-0
Chen XDi ZWu WWu QShi JFeng Q(2022)Detailed Routing Short Violation Prediction Using Graph-Based Deep Learning ModelIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2021.309342069:2(564-568)Online publication date: Feb-2022
https://doi.org/10.1109/TCSII.2021.3093420
Huang YLin CLiang WChen H(2021)Learning Based Placement Refinement to Reduce DRC Short Violations2021 International Symposium on VLSI Design, Automation and Test (VLSI-DAT)10.1109/VLSI-DAT52063.2021.9427321(1-4)Online publication date: 19-Apr-2021
https://doi.org/10.1109/VLSI-DAT52063.2021.9427321
Datta PMukherjee S(2021)OptiPlace: optimized placement solution for mixed-size designsAnalog Integrated Circuits and Signal Processing10.1007/s10470-021-01864-5Online publication date: 13-May-2021
https://doi.org/10.1007/s10470-021-01864-5
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.

Cited By

Index Terms

Recommendations

Prediction and reduction of routing congestion

Physical hierarchy generation with routing congestion control

A congestion-driven placement framework with local congestion prediction