More Web Proxy on the site http://driver.im/

research-article

Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing

Authors:

Yih-Lang LiAuthors Info & Claims

ASP-DAC '09: Proceedings of the 2009 Asia and South Pacific Design Automation Conference

Pages 570 - 575

Published: 19 January 2009 Publication History

Abstract

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseudorandom net-ordering routing and evolution-based rip-up and reroute using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and re-assignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wire length at a 1.42X and 25.84X faster routing speed. Besides, our layer assignment yields 3.5% to 5.6% fewer vias, 2.2% to 3.3% shorter wirelength and 13% to 27% less runtime than COLA.

References

[1]

R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh, "Pattern routing: use and theory for increasing predictability and avoiding coupling," IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, pages 777--790, July 2002.

Digital Library

[2]

R. T. Hadsell and P. H. Madden, "Improve global routing through congestion estimation," In Proc. Design Automation Conf., pages 28--31, 2003

Digital Library

[3]

M. Cho and D. Pan, "BoxRouter: A new global router based on box expansion and progressive ILP," In Proc. Design Automation Conf., pages 373--378, 2006.

Digital Library

[4]

M. Pan and C. Chu, "FastRoute: A step to integrate global routing into placement," In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 464--471, 2006.

Digital Library

[5]

M. Pan and C. Chu, "FastRoute 2.0: A high-quality and efficient global router," In Proc. Asia and South Pacific Design Automation Conf., pages 250--255, 2007.

Digital Library

[6]

http://www.sigda.org/ispd2007/contest.html

[7]

M. M. Ozdal and M. D. F. Wong, "ARCHER: A history-driven global routing algorithm," In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 488--495, 2007.

Digital Library

[8]

M. Cho, K. Lu, K. Yuan, and D. Z. Pan, "BoxRouter 2.0: Architecture and implementation of a hybrid and robust global router," In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 503--508, 2007

Digital Library

[9]

J. A. Roy and I. L. Markov, "High-performance routing at the nanometer scale," In Proc. IEEE/ACM Intl. Conf. Computer-Aided Design, pages 496--502, 2007

Digital Library

[10]

J.-R. Gao, P.-C. Wu, and T.-C Wang, "A new global router for modern designs", In Proc. Asia and South Pacific Design Automation Conf., pages 232--237, 2008.

Digital Library

[11]

L. McMurchie and C. Ebeling, "Pathfinder: A negotiation-based performance-driven router for FPGAs," In Proc. Of ACM Int'l Symp on Field-Programmable Gate Arrays, pages 111--117, 1995.

Digital Library

[12]

M. D. Moffitt, "MaizeRouter: Engineering an effective global router," In Proc. Asia and South Pacific Design Automation Conf., pages 232--237, 2008.

Digital Library

[13]

http://www.ispd.cc/contests/ispd08rc.html

[14]

C. Chu, Y. Wong, "Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design," In Proc. Intl. Symp. On Physical Desgin, pages 28--35, 2005

Digital Library

[15]

Y.-L. Lin, Y.-C. Hsu, and F.-S. Tsai, "SILK: A simulated evolution router," IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 8, No. 10, pages 1108--1114, Oct. 1989.

Digital Library

[16]

N. J. Naclerio, S. Masuda, and K. Nakajima, "The via minimization problem is NP-complete," IEEE Trans. Comput, pages 1604--1608, Nov., 1989.

Digital Library

[17]

T.-H. Lee, T.-C. Wang, "Congestion-constrained layer assignment for via minimization in global routing," IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, Ni. 9, pages 1643--1656, Sep. 2008.

Digital Library

Cited By

Liu DYu BChowdhury SPan D(2016)Incremental layer assignment for critical path timingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898033(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898033
Ao JDong SChen SGoto SKoh CSze C(2013)Delay-driven layer assignment in global routing under multi-tier interconnect structureProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451942(101-107)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451942
Liu WLi YHu JKoh C(2012)Optimizing the antenna area and separators in layer assignment of multi-layer global routingProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160946(137-144)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160946
Show More Cited By

Recommendations

Congestion-Constrained Layer Assignment for Via Minimization in Global Routing

In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-...
Congestion driven global routing and cross point assignment
Efficient Rerouting Algorithms for Congestion Mitigation
ISVLSI '09: Proceedings of the 2009 IEEE Computer Society Annual Symposium on VLSI

Congestion mitigation and overflow avoidance are two of the major goals of the global routing stage. With a significant increase in the chip size and routing complexity,congestion and overflow have become critical issues in physical design automation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '09: Proceedings of the 2009 Asia and South Pacific Design Automation Conference

January 2009

902 pages

ISBN:9781424427482

General Chair:
Kazutoshi Wakabayashi
NEC Corporation

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IPSJ SIGSLDM: Information Processing Society of Japan - SIG System LSI Design Methodology
IEICE ESS: Institute of Electronics, Information and Communication Engineers - Engineering Sciences Society

Publisher

IEEE Press

Publication History

Published: 19 January 2009

Check for updates

Qualifiers

Research-article

Conference

ASPDAC '09

Sponsor:

SIGDA
IPSJ SIGSLDM
IEICE ESS

ASPDAC '09: Asia and South Pacific Design Automation Conference

January 19 - 22, 2009

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

11
Total Citations
View Citations
213
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu DYu BChowdhury SPan D(2016)Incremental layer assignment for critical path timingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898033(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898033
Ao JDong SChen SGoto SKoh CSze C(2013)Delay-driven layer assignment in global routing under multi-tier interconnect structureProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451942(101-107)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451942
Liu WLi YHu JKoh C(2012)Optimizing the antenna area and separators in layer assignment of multi-layer global routingProceedings of the 2012 ACM international symposium on International Symposium on Physical Design10.1145/2160916.2160946(137-144)Online publication date: 25-Mar-2012
https://dl.acm.org/doi/10.1145/2160916.2160946
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
Liu WLi YChao KPhillips JHu AGraeb H(2011)High-quality global routing for multiple dynamic supply voltage designsProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132387(263-269)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132387
Liu WLi Y(2011)Negotiation-based layer assignment for via count and via overflow minimizationProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950924(539-544)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950924
Lee TChang YWang TChang YHu J(2011)An enhanced global router with consideration of general layer directivesProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960411(53-60)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960411
Chang YLee TWang TScheffer LPhillips JHu A(2010)GLADEProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133496(319-323)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133496
Lee TWang TScheffer LPhillips JHu A(2010)Simultaneous antenna avoidance and via optimization in layer assignment of multi-layer global routingProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133495(312-318)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133495
Liu WKao WLi YChao KSapatnekar S(2010)Multi-threaded collision-aware global routing with bounded-length maze routingProceedings of the 47th Design Automation Conference10.1145/1837274.1837324(200-205)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837324
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.

Media

Figures

Other

Tables

View Table of Contents