Article

A fast congestion estimator for routing with bounded detours

Authors:

Zhiwei TangAuthors Info & Claims

ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation Conference

Pages 666 - 670

Published: 27 January 2004 Publication History

Abstract

Congestion estimation is an important issue for the success of the VLSI layout. Fast congestion estimation provides an efficient means to adjust the placement and routability. A probabilistic model of interconnections enables designers to quickly predict routing congestion. We propose a powerful and fast estimation approach which allows wires to have bounded-, length detours to bypass congestions. Our method is more realistic and precise than the previous work. It is much faster than a global router for estimation purpose. The experimental results demonstrate the effectiveness of the method on routing benchmarks.

References

[1]

C.-C. Chang, J. Cong, D. Pan, and X. Yuan, "Multilevel global placement with congestion control," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 4, pp. 395--409, July 2002.

Digital Library

[2]

J. Cong and Z. Pan, "Interconnect performance estimation models for synthesis and design planning," ACM/IEEE Int'l Workshop on Logic Synthesis, pp. 427--433, June, 1998.

[3]

UCLA, http://www.ece.ucsb.edu/~kastner/labyrinth/.

[4]

X. Yang, R. Kastner and M. Sarrafzadeh, "Congestion estimation during top-down placement," IEEE Transactions on Computer-Aided Design (TCAD), vol 21, no. 1, pp. 72--80, January 2002.

Digital Library

[5]

M. Wang and M. Sarrafzadeh, "On the behavior of congestion minimization during placement," Proc. Int. Symp. Physical Design, pp. 145--150, Apr. 1999.

Digital Library

[6]

H. Chen, H. Zhou, F. Y. Young, D. F. Wong, H. Yang, N. A. Sherwani "Integrated floorplanning and interconnect planning," ICCAD 1999: 354--357.

Digital Library

[7]

J. Lou, S. Thakur, S. Krishnamoorthy, and H. S. Sheng, "Estimating routing congestion using probabilistic analysis," IEEE Trans. Computer-Aided Design, 21(1), pp. 32--41, 2002.

Digital Library

[8]

S. D. Brown, J. Rose, and Z. G. Vrabesic, "A stochastic model to predict the routability of field programmable gate arrays," IEEE Trans. Computer-Aided Design, 12(12), pp. 1827--1838, 1993.

Digital Library

[9]

A. A. El Gamal, "Two-dimensional stochastic model for interconnections in master slice integrated circuits," IEEE Trans. Circuit & Systems, 28(2), pp. 127--138, 1981.

[10]

A. A. El Gamal and Z. A. Syed, "A stochastic model for interconnections in custom integrated circuits," IEEE Trans. Circuit & Systems, 28(9), pp. 888--894, 1981.

[11]

F. J. Kurdahi and A. C. Parker, "Techniques for area estimation of VLSI layouts," IEEE Trans. Computer-Aided Design, 8(1), pp. 81--92, 1986.

Digital Library

[12]

N. Sherwani. Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers, 1995.

Digital Library

[13]

M. Hall. Combinatorial theory, 2nd ed. New York: John Wiley & Sons, 1986.

Digital Library

[14]

M. Percy and A. Macmahon. Combinatory Analysis. New York: Chelsea, 1960.

[15]

Technical report, Portland State University.

Cited By

Taghavi TDabiri FNahapetian ASarrafzadeh MKennings AMandoiu I(2007)Tutorial on congestion predictionProceedings of the 2007 international workshop on System level interconnect prediction10.1145/1231956.1231961(15-24)Online publication date: 17-Mar-2007
https://dl.acm.org/doi/10.1145/1231956.1231961
He FSong XGu MCheng LYang GTang ZSun J(2006)A combinatorial congestion estimation approach with generalized detoursComputers & Mathematics with Applications10.1016/j.camwa.2005.05.01351:6-7(1113-1126)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1016/j.camwa.2005.05.013

Recommendations

Routing congestion estimation with real design constraints
DAC '13: Proceedings of the 50th Annual Design Automation Conference

To address the routability issue, routing congestion estimators (RCE) become essential in industrial design flow. Recently, several RCEs [1-4] based on global routing engines are developed, but they typically ignore the effects of routing on timing so ...
A combinatorial congestion estimation approach with generalized detours

Congestion estimation plays an important role in the physical layout of VLSI design. This paper presents a new probabilistic estimation model that improves the previous estimators by relaxing the constraint on detours in a route. The model is more ...
A fast congestion estimator for routing with bounded detours

Congestion estimation is an important issue for design automation of the VLSI layout. Fast congestion estimation provides an efficient means to adjust the placement and wire planning. A probabilistic model of interconnections enables designers to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '04: Proceedings of the 2004 Asia and South Pacific Design Automation Conference

January 2004

957 pages

ISBN:0780381750

General Chair:
Masaharu Imai
Osaka University

Sponsors

IPSJ: Information Processing Society of Japan
IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE: Institute of Electronics, Information and Communication Engineers

Publisher

IEEE Press

Publication History

Published: 27 January 2004

Check for updates

Author Tags

Qualifiers

Article

Conference

ASPDAC04

Sponsor:

IPSJ
SIGDA
IEICE

ASPDAC04: Asia and South Pacific Design Automation Conference 2004

January 27 - 30, 2004

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
183
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Taghavi TDabiri FNahapetian ASarrafzadeh MKennings AMandoiu I(2007)Tutorial on congestion predictionProceedings of the 2007 international workshop on System level interconnect prediction10.1145/1231956.1231961(15-24)Online publication date: 17-Mar-2007
https://dl.acm.org/doi/10.1145/1231956.1231961
He FSong XGu MCheng LYang GTang ZSun J(2006)A combinatorial congestion estimation approach with generalized detoursComputers & Mathematics with Applications10.1016/j.camwa.2005.05.01351:6-7(1113-1126)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1016/j.camwa.2005.05.013

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.

Media

Figures

Other

Tables

View Table of Contents