Article

Free access

An efficient channel router

Author:

Takeshi YoshimuraAuthors Info & Claims

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

Pages 38 - 44

Published: 25 June 1984 Publication History

PDF eReader

Abstract

In the LSI chip layout design, channel routing is one of the key problems. The problem is to route a specified net list between two rows of terminals across a two layer channel.

This paper presents a new routing algorithm, which is an improved version of the classical “left edge algorithm”. The new algorithm uses a row by row approach, calculating an optimum net assignment to each row.

The algorithm was implemented for examples in previously published papers. Experimental results show that the new algorithm produces optimum solutions in most cases.

References

[1]

A. Hashimoto, J. Stevens, "Wire routing by optimizing channel assignment" Proc. 8th DA Conf., 1971, pp 214-224.

Digital Library

Google Scholar

[2]

T. Yoshimura, E.S. Kuh, "Efficient Algorithms for Channel Routing", IEEE Trans. on CAD of ICs and Systems, Vol. CAD-1, No 1, 1982, pp 25-35.

Google Scholar

[3]

R.L. Rivest, Fiduccia C.M., "A 'Greedy' Channel Router" Proc. 19th DA Conf., 1982, pp 418-424.

Digital Library

Google Scholar

[4]

M. Burstein, R. Pelavin, "Hierarchical Channel Router", Proc. 20th DA Conf., 1983, pp 591-597.

Digital Library

Google Scholar

[5]

A. Sangiovanni-Vincentelli, M. Santomauro, "YACR: Yet Another Channel Router", Proc. IEEE Int. Symp. Circ. & Syst., 1983, pp 327-331

Google Scholar

[6]

D. Deutsch, "A dogleg channel router", Proc. 13th DA Conf., 1976, pp 425-433.

Digital Library

Google Scholar

Cited By

View all

Okuda ROguri SSchweikert D(1992)An efficient routing algorithm for SOG cell generation on a dense gate-isolated layout styleProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.149670(676-681)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.149670
Fujii TMima YMatsuda TYoshimura TSchweikert D(1992)A multi-layer channel router with new style of over-the-cell routingProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.149635(585-588)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.149635
Masson CEscassut RBarbier DWiner DChevallier GNewton A(1991)Object oriented Lisp implementation of the CHEOPS VLSI floor planning and routing systemProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127677(259-264)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127677
Show More Cited By

Index Terms

An efficient channel router
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Buses and high-speed links
  2. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

An efficient multilayer MCM router based on four-via routing

In this paper, we present an efficient multilayer general area router, named V4R, for MCM and dense PCB designs. One unique feature of the V4R router is that it uses no more than four interconnection vias to route every net and yet produces high quality ...
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 ...
A three-layer gridless channel router with compaction
DAC '87: Proceedings of the 24th ACM/IEEE Design Automation Conference

This paper presents a channel router that is designed to handle channels having irregularly-spaced terminals on different layers. The development of this router has investigated combining several basic wiring functions in distinct stages to achieve the ...

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

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

6
Total Citations
View Citations
249
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)30

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Okuda ROguri SSchweikert D(1992)An efficient routing algorithm for SOG cell generation on a dense gate-isolated layout styleProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.149670(676-681)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.149670
Fujii TMima YMatsuda TYoshimura TSchweikert D(1992)A multi-layer channel router with new style of over-the-cell routingProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.149635(585-588)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.149635
Masson CEscassut RBarbier DWiner DChevallier GNewton A(1991)Object oriented Lisp implementation of the CHEOPS VLSI floor planning and routing systemProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127677(259-264)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127677
Edahiro MYoshimura TSmith R(1991)New placement and global routing algorithms for standard cell layoutsProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123427(642-645)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123427
Masson CBarbier DEscassut RWiner DChevallier GZeegers PAdshead GJess J(1990)CHEOPSProceedings of the conference on European design automation10.5555/949970.950027(250-256)Online publication date: 12-Mar-1990
https://dl.acm.org/doi/10.5555/949970.950027
McGehee R(1987)A practical moat routerProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.37921(216-222)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.37921

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

An efficient multilayer MCM router based on four-via routing

A new global router for modern designs

A three-layer gridless channel router with compaction