Article

Free access

A switchbox router with obstacle avoidance

Authors:

Gordon T. Hamachi,

John K. OusterhoutAuthors Info & Claims

DAC '84: Proceedings of the 21st Design Automation Conference

Pages 173 - 179

Published: 25 June 1984 Publication History

PDF eReader

Abstract

Detour is the channel router used by the Magic layout system. Based on Rivest and Fiduccia's “greedy” channel router, Detour is capable of routing switchboxes and channels containing obstacles such as preexisting wiring. It jogs nets around multi-layer obstacles such as contacts, and routes over single-layer obstacles. If there are no obstacles, results are comparable to other good channel routers. Detour thus combines the effectiveness of traditional channel routers with the flexibility of net-at-a-time routers.

References

[1]

Burstein, M., and Pelavin, R., "Hierarchical Channel Router", Proc. 20th Design Automation Conference, Miami (1983).

Digital Library

Google Scholar

[2]

Burstein, M., and Pelavin, R., "Hierarchical Wire Routing", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems", Vol. CAD-2, No. 4, (Oct 1983).

Google Scholar

[3]

Chen, H., Private Communication.

Google Scholar

[4]

Chen, N. P., Hsu, C. P., and Kuh, E. S., "The Berkeley Building-Block Layout System for VLSI Design", ERL memo UCB/ERL M83/10, UC Berkeley, (Feb. 1983).

Google Scholar

[5]

Lee, C. Y., "An Algorithm for Path Connections and its Application", IRE Trans. on Electronic Computers (Sept. 1961), pp. 346-365.

Crossref

Google Scholar

[6]

Hightower, D., "A Solution to the Line Routing Problem on the Continuous Plane", Proceedings Design Automation Workshop, pp. 1-24, (1969).

Digital Library

Google Scholar

[7]

Ousterhout, J. K., Hamachi, G. T., Mayo, R. N., Scott, W. S., and Taylor, G. S., "Magic: A VLSI Layout System", Proc. 21st Design Automation Conference, Albuquerque (1984).

Digital Library

Google Scholar

[8]

Persky, G., D. Deutsch, and D. Schweikert, "LTX-A Minicomputer-Based System for Automated LSI Layout,", Journal of Design Automation and Fault-Tolerant Computing, Vol. 1, No. 3 (May 1977), pp. 217-255.

Google Scholar

[9]

Rivest, R. L., "The 'PI' (Placement and Interconnect) System", Proc. 19th Design Automation Conference, Las Vegas (1982).

Digital Library

Google Scholar

[10]

Rivest, R. L., and Fiduccia, C. M., "A Greedy Channel Router", Proc. 19th Design Automation Conference, Las Vegas (1982), pp. 418-424.

Digital Library

Google Scholar

[11]

Sangiovanni-Vincentelli, Alberto, Private Communication, February 1983

Google Scholar

[12]

Soukup, J., "Circuit Layout", Proceedings of the IEEE, Vol. 69, No. 10 (Oct. 1981), 1281-1304.

Crossref

Google Scholar

[13]

Soukup, J., Private Communication, Dec. 1983

Google Scholar

[14]

Yoshimura, T., and Kuh, E. S., "Efficient Algorithms for Channel Routing, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems", Vol. CAD-1, No. 1, (Jan 1982).

Google Scholar

Cited By

View all

Chang YTseng I(2013)A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygonsACM Transactions on Design Automation of Electronic Systems10.1145/250501518:4(1-18)Online publication date: 25-Oct-2013
https://dl.acm.org/doi/10.1145/2505015
Srinivasan AKuh EAdshead GJess J(1990)MOLEProceedings of the conference on European design automation10.5555/949970.950071(446-450)Online publication date: 12-Mar-1990
https://dl.acm.org/doi/10.5555/949970.950071
Jou JLee JSun YWang J(1990)An Efficient VLSI Switch-Box RouterIEEE Design & Test10.1109/54.579147:4(52-65)Online publication date: 1-Jul-1990
https://dl.acm.org/doi/10.1109/54.57914
Show More Cited By

Index Terms

A switchbox router with obstacle avoidance
1. Hardware
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
On whitespace and stability in physical synthesis

In the context of physical synthesis, large-scale standard-cell placement algorithms must facilitate incremental changes to layout, both local and global. In particular, flexible gate sizing, net buffering and detail placement require a certain amount ...
Computing area and wire length efficient routes for channels
VLSID '95: Proceedings of the 8th International Conference on VLSI Design

The first stage in channel routing is that of computing a routing solution S, for a given channel with as few tracks as possible. We consider a second stage in which it is desirable to reduce the total wire length without increasing area of routing. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '84: Proceedings of the 21st Design Automation Conference

June 1984

715 pages

ISBN:0818605421

Publisher

IEEE Press

Publication History

Published: 25 June 1984

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

DAC '84 Paper Acceptance Rate 116 of 290 submissions, 40%;

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

8
Total Citations
View Citations
283
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)9

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chang YTseng I(2013)A parallel dual-scanline algorithm for partitioning parameterized 45-degree polygonsACM Transactions on Design Automation of Electronic Systems10.1145/250501518:4(1-18)Online publication date: 25-Oct-2013
https://dl.acm.org/doi/10.1145/2505015
Srinivasan AKuh EAdshead GJess J(1990)MOLEProceedings of the conference on European design automation10.5555/949970.950071(446-450)Online publication date: 12-Mar-1990
https://dl.acm.org/doi/10.5555/949970.950071
Jou JLee JSun YWang J(1990)An Efficient VLSI Switch-Box RouterIEEE Design & Test10.1109/54.579147:4(52-65)Online publication date: 1-Jul-1990
https://dl.acm.org/doi/10.1109/54.57914
The KWong DCong JThomas D(1989)VIA minimization by layout modificationProceedings of the 26th ACM/IEEE Design Automation Conference10.1145/74382.74533(799-802)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1145/74382.74533
Kaplan D(1987)Routing with a scanning window-8Ma unified approachProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.37987(629-632)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.37987
Ng CThomas D(1986)An industrial world channel router for non-rectangular channelsProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318091(490-494)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318091
Joobbani RSiewiorek DOfek HO'Neill L(1985)WEAVERProceedings of the 22nd ACM/IEEE Design Automation Conference10.5555/317825.317869(266-272)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.5555/317825.317869
Ousterhout JHamachi GMayo RScott WTaylor GLambert POfek HO'Neill LPistilli PLosleben PNash JShaklee DPreas BLerman H(1984)MagicProceedings of the 21st Design Automation Conference10.5555/800033.800790(152-159)Online publication date: 25-Jun-1984
https://dl.acm.org/doi/10.5555/800033.800790

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

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

On whitespace and stability in physical synthesis

Computing area and wire length efficient routes for channels