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

research-article

Diffusion-driven congestion reduction for substrate topological routing

Authors:

Xian-Long HongAuthors Info & Claims

ISPD '09: Proceedings of the 2009 international symposium on Physical design

Pages 175 - 180

https://doi.org/10.1145/1514932.1514970

Published: 29 March 2009 Publication History

Abstract

Off-chip substrate routing for high density packages is challenging, and the existing substrate routing algorithms often result in a large number of unrouted nets that have to be routed manually. This paper develops an effective yet efficient diffusion-driven method D-Router to improve routability by a simulated diffusion process based on the duality between congestion and concentration. Compared with a recently published A*-based algorithm used in a state of the art commercial tool and with similar routability and runtime as the negotiation based routing, D-Router reduces the number of unrouted nets by 4.6x with up to 94x runtime reduction.

References

[1]

F. Bossen. Anisotropic mesh generation with particles. In M.S. thesis, Univ. of CMU, 1996.

[2]

S. S. Chen, J. J. Chen, S. J. Chen, and C. C. Tsai. An automatic router for the pin grid array package. In Proc. Asia South Pacific Design Automation Conf., pages 275--281, 1999.

[3]

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

Digital Library

[4]

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

[5]

W. W. Dai, T. Dayan, and D. Staepelaere. Topological routing in SURF: generating a rubber-band sketch. In Proc. Design Automation Conf., pages 39--44, 1991.

Digital Library

[6]

Y. Kubo and A. Takahashi. A global routing method for 2-layer ball grid array packages. In Proc. Intl. Symp. Physical Design, pages 36--43, 2005.

Digital Library

[7]

S. H. Liu, G. Q. Chen, T. T. Jing, L. He, T. P. Zhang, R. Dutta, and X. L. Hong. Topological routing to maximize routability for package substrate. In Proc. Design Automation Conf., pages 566--569, 2008.

Digital Library

[8]

L. McMurchie and C. Ebeling. PathFinder: a negotiation-based performance-driven router for FPGAs. In Proc. ACM Intl. Symp. Field-Programmable Gate Arrays, pages 111--117, 1995.

Digital Library

[9]

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

Digital Library

[10]

R. Shi and C. K. Cheng. Efficient escape routing for hexagonal array of high density I/Os. In Proc. Design Automation Conf., pages 1003--1008, 2006.

Digital Library

[11]

D. Staepelaere, J. Jue, T. Dayan, and W. W. Dai. SURF: a rubber-band routing system for multichip modules. IEEE Trans. Design & Test of Computers., 10(4):18--26, 1993.

Digital Library

[12]

C. C. Tsai, C. M. Wang, and S. J. Chen. NEWS: a net-even-wiring system for the routing on a multilayer PGA package. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 17(2):182--189, 1998.

Digital Library

[13]

J. J. Xiong, Y. C. Wong, E. Sarto, and L. He. Constraint driven I/O planning and placement for chip-package co-design. In Proc. Asia South Pacific Design Automation Conf., pages 207--212, 2006.

Digital Library

[14]

M. F. Yu and W. W. Dai. Pin assignment and routing on a single-layer pin grid array. In Proc. Asia South Pacific Design Automation Conf., pages 203--208, 1995.

Digital Library

[15]

M. F. Yu, J. Darnauer, and W. W. Dai. Interchangeable pin routing with application to package layout. In Proc. Intl. Conf. Computer-Aided Design, pages 668--673, 1996.

Digital Library

Cited By

Yan J(2021)Via-Avoidance-Oriented Interposer Routing for Layer Minimization in 2.5-D IC DesignsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.311391829:11(1889-1902)Online publication date: Nov-2021
https://doi.org/10.1109/TVLSI.2021.3113918
Yan J(2019)Single-Layer GNR Routing for Minimization of Bending DelayIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816438:11(2099-2112)Online publication date: Nov-2019
https://doi.org/10.1109/TCAD.2018.2878164
(2018)Single-layer obstacle-aware routing for substrate interconnectionsIntegration, the VLSI Journal10.1016/j.vlsi.2015.04.00151:C(1-9)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.vlsi.2015.04.001
Show More Cited By

Index Terms

Diffusion-driven congestion reduction for substrate topological routing
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Topological routing to maximize routability for package substrate
DAC '08: Proceedings of the 45th annual Design Automation Conference

Compared with on-chip routers, the existing commercial tools for off-chip routing have a much lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we develop an effective, yet efficient, substrate ...
Effective congestion reduction for IC package substrate routing

Off-chip substrate routing for high-density packages is challenging due to requirements such as high density, lack of vertical detour, non-Manhattan routing, and primarily planar routing. The existing substrate routing algorithms often result in a large ...
Substrate topological routing for high-density packages

Off-chip substrate routing for high-density packages is on the critical path for time to market. Compared with on-chip routers, existing commercial tools for off-chip routing have lower routability and often result in a large number of unrouted nets for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '09: Proceedings of the 2009 international symposium on Physical design

March 2009

208 pages

ISBN:9781605584492

DOI:10.1145/1514932

General Chair:
Gi-Joon Nam
IBM Research
,
Program Chair:
Prashant Saxena
Synopsys

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISPD09

Sponsor:

ISPD09: International Symposium on Physical Design

March 29 - April 1, 2009

California, San Diego, 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

5
Total Citations
View Citations
135
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan J(2021)Via-Avoidance-Oriented Interposer Routing for Layer Minimization in 2.5-D IC DesignsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.311391829:11(1889-1902)Online publication date: Nov-2021
https://doi.org/10.1109/TVLSI.2021.3113918
Yan J(2019)Single-Layer GNR Routing for Minimization of Bending DelayIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.287816438:11(2099-2112)Online publication date: Nov-2019
https://doi.org/10.1109/TCAD.2018.2878164
(2018)Single-layer obstacle-aware routing for substrate interconnectionsIntegration, the VLSI Journal10.1016/j.vlsi.2015.04.00151:C(1-9)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1016/j.vlsi.2015.04.001
Yan JTseng YYen C(2014)Feasible region assignment of routing nets in single-layer routing2014 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2014.6865148(393-396)Online publication date: Jun-2014
https://doi.org/10.1109/ISCAS.2014.6865148
Liu SChen GJing THe LDutta RHong X(2010)Effective congestion reduction for IC package substrate routingACM Transactions on Design Automation of Electronic Systems10.1145/1754405.175441215:3(1-21)Online publication date: 10-Jun-2010
https://dl.acm.org/doi/10.1145/1754405.1754412

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