Article

Free access

Hardware support for automatic routing

Authors:

E. Damm,

H. Gethöffer,

K. Kaiser,

E. Damm GmbHAuthors Info & Claims

DAC '82: Proceedings of the 19th Design Automation Conference

Pages 219 - 223

Published: 01 January 1982 Publication History

PDF eReader

Abstract

A system for automatic routing based on an iterative application of Lee's algorithm is presented. An extended cell admissibility is defined for continuous design rules in coarse rectangular grids. Combined hardware and software design strategies are applied towards the definition of data structures and their kernel primitives for automatic routing. The hardware architecture and the implementation of specific structures are discussed. The resulting extended routing unit is used in a CAD system. Thus the throughput of the iterative router is improved by a factor of 5 compared to the equivalent software process. Finally the architecture of a high speed stand-alone routing processor is presented.

References

[1]

C.Y. Lee: "An Algorithm for Path Connections and its Applications", IRE Trans. Elect. Comp., EC-10, Sept. 1961, pp. 346 - 365.

Google Scholar

[2]

S. Akers: "Routing", Chapter 6 in Design Automation of Digital Systems: Theory and Techniques. M. A. Breuer, ed. Prentice-Hall 1972.

Google Scholar

[3]

F. Rubin: "The Lee Path Connection Algorithm", IEEE Trans. on Comp., C-23, Sept. 1974, pp. 907 - 914.

Google Scholar

[4]

F. Rubin: "An Iterative Technique for Printed Wire Routing", Proc. 11th DA Conf., 1974, pp. 308 - 313.

Digital Library

Google Scholar

[5]

J.H. Hoel: "Some Variations of Lee's Algorithm", IEEE Trans. on Comp., C-25, Jan. 1976, pp. 19 - 24.

Google Scholar

[6]

E. Damm: "Der kuerzeste Weg in einem Gitternetz mit Hindernissen", Angewandte Informatik, May 1977, pp. 213 - 216.

Google Scholar

[7]

J. Soukup: "Fast Maze Router", Proc. 15th DA Conf., Las Vegas, June 1978, pp. 100 - 101,

Digital Library

Google Scholar

[8]

P. Agrawal and M. A. Breuer: "Some Theoretical Aspects of Algorithmic Routing", Conf. Proc. 14th DA Conf., 1977, pp. 23 - 31.

Digital Library

Google Scholar

[9]

J. Soukup: "Global Router", Proc. 16th DA Conf., June 1979, pp. 481 - 484.

Digital Library

Google Scholar

[10]

M. A. Breuer and K. Shamsa: "A Hardware Router", J. Digital Systems, vol. 4, 1981, issue 4, pp. 393 - 408.

Google Scholar

[11]

E. Damm: "Rasterbezogenes automatisches Routing", unpublished report, Kaiser & Dr. Damm GmbH, D 6102 Mühlheim, Fed. Rep. Germany, June 1981.

Google Scholar

[12]

J. Backus: "Can Programming be Liberated from the von Neumann Style ? A Functional Style and its Algebra of Programs", CACM vol. 21, no 18.

Digital Library

Google Scholar

Cited By

View all

Spiers TEdwards D(1987)A high performance routing engineProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.38013(793-799)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.38013
Kawamura KUmeda MShiraishi HThomas D(1986)Hierarchical dynamic routerProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318164(803-809)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318164
Hancock JDasGupta SThomas D(1986)Tutorial on parallel processing for design automation applications (tutorial session)Proceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318025(69-77)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318025
Show More Cited By

Index Terms

Hardware support for automatic routing

Recommendations

Automatic generation of hardware/software interfaces
ASPLOS '12

Enabling new applications for mobile devices often requires the use of specialized hardware to reduce power consumption. Because of time-to-market pressure, current design methodologies for embedded applications require an early partitioning of the ...
Run-Time Reconfiguration for Automatic Hardware/Software Partitioning
RECONFIG '10: Proceedings of the 2010 International Conference on Reconfigurable Computing and FPGAs

Parameterisable configurations allow very fast run-time reconfiguration in FPGAs. The main advantage of this new concept is the automated tool flow that converts a hardware design into a more resource-efficient run-time reconfigurable design without a ...
Automatic generation of hardware/software interfaces
ASPLOS '12

Enabling new applications for mobile devices often requires the use of specialized hardware to reduce power consumption. Because of time-to-market pressure, current design methodologies for embedded applications require an early partitioning of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '82: Proceedings of the 19th Design Automation Conference

January 1982

919 pages

ISBN:0897910206

Publisher

IEEE Press

Publication History

Published: 01 January 1982

Check for updates

Qualifiers

Article

Acceptance Rates

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

5
Total Citations
View Citations
206
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

Spiers TEdwards D(1987)A high performance routing engineProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.38013(793-799)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.38013
Kawamura KUmeda MShiraishi HThomas D(1986)Hierarchical dynamic routerProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318164(803-809)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318164
Hancock JDasGupta SThomas D(1986)Tutorial on parallel processing for design automation applications (tutorial session)Proceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318025(69-77)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318025
Finch AMackenzie KBalsdon GSymonds GOfek HO'Neill L(1985)A method for gridless routing of printed circuit boardsProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317937(509-515)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317937
Spira PHage COfek HO'Neill L(1985)Hardware acceleration of gate array layoutProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317913(359-366)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317913

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.

Abstract

References

Cited By

Index Terms

Recommendations

Automatic generation of hardware/software interfaces

Run-Time Reconfiguration for Automatic Hardware/Software Partitioning

Automatic generation of hardware/software interfaces

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations