Article

Free access

Hierarchical dynamic router

Authors:

Kaoru Kawamura,

Masanobu Umeda,

Hiroshi ShiraishiAuthors Info & Claims

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

Pages 803 - 809

Published: 02 July 1986 Publication History

PDF eReader

Abstract

In this paper we will discuss a new automatic routing method for printed circuit boards(PCBs).

In the field of automatic PCB routing, several “rip-up and reroute” techniques (“dynamic routing”) have recently been proposed.

Dynamic routing works by changing one or more previously routed features, and identifying unrouted connections in a new configuration. Dynamic routing is an important idea, because it has the possibility of 100% completion by automating the wire embedding that was formerly done manually.

The method we propose here is based on dynamic routing. Its distinctive feature lies in the organization of three levels of hierarchy; grid routing, local dynamic routing, and global dynamic routing.

In recent experiments with this method, improvement in both routing completion rate and processing time has been obtained.

References

[1]

Hightower,D.W., "A Solution to Line-Routing Problems on Circuit Plane", Proc. 6th Design Automation Workshop, pp. 1-24, 1969.

Digital Library

Google Scholar

[2]

Lee,C.Y., "An Algorithm for Path Connection and its Applications", IRE Trans. on Electronic Computers, September, pp. 346-365, 1961.

Google Scholar

[3]

Bollinger,H., "A Mature DA System for PC Layout", Proc. International Printed Circuits Conference, pp.85-99, 1979.

Google Scholar

[4]

Finch,A.C., Mackenzie,K. J., Balsdon,G. J. and Symonds,G., "A Method for Gridless Routing of Printed Circuit Boards", Proc. 22nd Design Automation Conference, pp.509-515, 1985.

Digital Library

Google Scholar

[5]

Robert,L.J., "An Expert Approach to Completing Partially Routed Printed Cireult Boards", Proc. 22nd Design Automation Conference, pp.523-528, 1985.

Digital Library

Google Scholar

[6]

Dees,W.A. Jr. and Smith, R.J. II, "Performance of Intereonnection Rip-up and Reroute Strategies", Proe. 18th Design Automation Conference, pp.382-390, 1981.

Digital Library

Google Scholar

[7]

Dees,W.A.Jr. and Karger,P.G., "Automated Rip-up and Reroute Techniques", Proc. 19th Design Automation Conference, pp.432-439, 1982.

Digital Library

Google Scholar

[8]

Damm,E. and Gethoffer,H., "Hardware Support for Automatic Routing", Proe. 19th Design Automation Conference, pp219-223, 1982.

Digital Library

Google Scholar

[9]

Shiralshi,H., Ishli,M., Kurlta,S. and Nagamlne,M., "ICAD/PCB: Integrated Computer Aided Design System for Prlnted Circuit Boards", Proc. 19th Design Automation Conference, pp. 727-732, 1982.

Digital Library

Google Scholar

Cited By

View all

Moosa ZEdwards DMusgrave G(1995)An investigation of iterative routing algorithmsProceedings of the conference on European design automation10.5555/224270.224294(91-96)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224270.224294
Raith MBartholomeus MNewton A(1991)A new hypergraph based rip-up and reroute strategyProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127628(54-59)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127628
Chakraverti AChung MShaklee DNewton A(1988)Routing algorithm for gate array macro cellsProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285842(658-662)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285842

Index Terms

Hierarchical dynamic router

Recommendations

CAFE router: a fast connectivity aware multiple nets routing algorithm for routing grid with obstacles
ASPDAC '10: Proceedings of the 2010 Asia and South Pacific Design Automation Conference

In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a pin to the other pin greedily so that the wire length of ...
A new global router for modern designs
ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

In this paper, we present a new global router, NTHU-Route, for modern designs. NTHU-Route is based on iterative rip-ups and reroutes, and several techniques are proposed to enhance our global router. These techniques include (1) a history based cost ...
Analyzing and Modeling Router---Level Internet Topology
Information Networking. Towards Ubiquitous Networking and Services

Measurement studies on the Internet topology show that connectivities of nodes exhibit power---law attribute, but it is apparent that only the degree distribution does not determine the network structure, and especially true when we study the network---...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

July 1986

835 pages

ISBN:0818607025

Chairman:
Don Thomas
IBM, Thomas J. Watson Research Center, Yorktown Heights, NY

Publisher

IEEE Press

Publication History

Published: 02 July 1986

Check for updates

Qualifiers

Article

Acceptance Rates

DAC '86 Paper Acceptance Rate 124 of 300 submissions, 41%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
243
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moosa ZEdwards DMusgrave G(1995)An investigation of iterative routing algorithmsProceedings of the conference on European design automation10.5555/224270.224294(91-96)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224270.224294
Raith MBartholomeus MNewton A(1991)A new hypergraph based rip-up and reroute strategyProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127628(54-59)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127628
Chakraverti AChung MShaklee DNewton A(1988)Routing algorithm for gate array macro cellsProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285842(658-662)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285842

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

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

CAFE router: a fast connectivity aware multiple nets routing algorithm for routing grid with obstacles

A new global router for modern designs

Analyzing and Modeling Router---Level Internet Topology