Article

Free access

The minimum width routing of A 2-row 2-layer polycell-layout

Authors:

Tatsuya Kawamoto,

Yoji KajitaniAuthors Info & Claims

DAC '79: Proceedings of the 16th Design Automation Conference

Pages 290 - 296

Published: 25 June 1979 Publication History

PDF eReader

Abstract

This paper presents a new routing principle that leads to an algorithm to realize the minimum width of the 2-layer channel area between two rows of terminals to be interconnected. Besides the theoretical results, practically applicable routing algorithms based on our principle are developed.

References

[1]

[1] C.Y. Lee, "An Algorithm for Path Connections and Its Applications," IRE Trans. on Electronic Computers, 346-365 (1961).

Crossref

Google Scholar

[2]

[2] A. Hashimoto and J. Stevens, "Wire Routing by Optimizing Channel Assignment within Large Apertures," Proc. 8th Design Automation Workshop, 155-169 (1971).

Digital Library

Google Scholar

[3]

[3] T. Asano, T. Kitahashi, K. Tanaka, H. Horino and T. Amano, "Realizabillty of Wiring for Building-Block Type LSI," Trans. IECE Japan, 56-A, 9, 489-496 (1973).

Google Scholar

[4]

[4] B.W. Kernighan, D.G. Schweikert and G. Persky, "An Optimum Channel-Routing Algorithm for Polycell Layouts of Integreted Circuits," Proc. 14th Design Automation Workshop, 417-124 (1977).

Google Scholar

[5]

[5] Y. Sugiyama and K. Kani, "A Routing Method of Multi-chip LSI," Trans. IECE Japan, 58-C, 4, 201-208 (1975).

Google Scholar

[6]

[6] D.N. Deutsch, "A "Dogleg" Channel Router," Proc. 13th Design Automation Workshop (1976).

Digital Library

Google Scholar

[7]

[7] G. Persky, D.N. Deutsch and D.G. Schweikert, "LTX-A Minicomputer-Based System For Automated LSI Layout," J. of Design Automation and Fault Tolerant Computing, 14-5, 217-255 (1977).

Google Scholar

[8]

[8] G. Persky, "PRO-An Automatic String Placement Program for Polycell Layout," Proc. 14th Design Automation Workshop, 417-424 (1977).

Digital Library

Google Scholar

[9]

[9] R.S. Fisher, "A Multi-Pass, Multi-Algorithm Approach to PCB Routing, "Proc. 15th Design Automation Workshop, 82-91 (1978).

Digital Library

Google Scholar

Cited By

View all

Kajitani YKoh CSze C(2013)Coding the objects in place and route CADProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451933(62-65)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451933
Takahashi AKoh CSze C(2013)Dawn of computer-aided designProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451930(58-58)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451930
Nakatake SSakanushi KKajitani YKawakita MYasuura H(1998)The channeled-BSGProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289064(418-425)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289064
Show More Cited By

Index Terms

The minimum width routing of A 2-row 2-layer polycell-layout
1. Hardware
  1. 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

2-Dilated flattened butterfly: A nonblocking switching topology for high-radix networks

High-performance computing is highly dependent on the communication network connecting the nodes. In this paper, we propose a 2-Dilated flattened butterfly (2DFB) network which provides non-blocking performance for relatively low cost overhead. We study ...
Deadlock-Free Multicast Wormhole Routing in 2-D Mesh Multicomputers

Multicast communication services, in which the same message is delivered from a sourcenode to an arbitrary number of destination nodes, are being provided in new-generationmulticomputers. Broadcast is a special case of multicast in which a message is ...
Tofu Interconnect 2: System-on-Chip Integration of High-Performance Interconnect
ISC 2014: Proceedings of the 29th International Conference on Supercomputing - Volume 8488

The Tofu Interconnect 2 Tofu2 is a system interconnect designed for the Fujitsu's next generation successor to the PRIMEHPC FX10 supercomputer. Tofu2 inherited the 6-dimensional mesh/torus network topology from its predecessor, and it increases the link ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '79: Proceedings of the 16th Design Automation Conference

June 1979

578 pages

Publisher

IEEE Press

Publication History

Published: 25 June 1979

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

11
Total Citations
View Citations
84
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)6

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kajitani YKoh CSze C(2013)Coding the objects in place and route CADProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451933(62-65)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451933
Takahashi AKoh CSze C(2013)Dawn of computer-aided designProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451930(58-58)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451930
Nakatake SSakanushi KKajitani YKawakita MYasuura H(1998)The channeled-BSGProceedings of the 1998 IEEE/ACM international conference on Computer-aided design10.1145/288548.289064(418-425)Online publication date: 1-Nov-1998
https://dl.acm.org/doi/10.1145/288548.289064
Wieners-Lummer CJohnson D(1990)Manhattan channel routing with good theoretical and practical performanceProceedings of the first annual ACM-SIAM symposium on Discrete algorithms10.5555/320176.320233(465-474)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.5555/320176.320233
Rivest RFiduccia C(1988)A Greedy channel routerPapers on Twenty-five years of electronic design automation10.1145/62882.62912(256-262)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/62882.62912
Baker BBhatt SLeighton FJohnson DFagin RFredman MHarel DKarp RLynch NPapadimitriou CRivest RRuzzo WSeiferas J(1983)An approximation algorithm for manhattan routingProceedings of the fifteenth annual ACM symposium on Theory of computing10.1145/800061.808779(477-486)Online publication date: 1-Dec-1983
https://dl.acm.org/doi/10.1145/800061.808779
Gopal ICoppersmith DWong C(1983)Optimal Wiring of Movable TerminalsIEEE Transactions on Computers10.1109/TC.1983.167633332:9(845-858)Online publication date: 1-Sep-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676333
Pinter RCrabbe JRadke COfek H(1982)On routing two-point nets across a channelProceedings of the 19th Design Automation Conference10.5555/800263.809305(894-902)Online publication date: 1-Jan-1982
https://dl.acm.org/doi/10.5555/800263.809305
Rivest RFiduccia CCrabbe JRadke COfek H(1982)A “greedy” channel routerProceedings of the 19th Design Automation Conference10.5555/800263.809239(418-424)Online publication date: 1-Jan-1982
https://dl.acm.org/doi/10.5555/800263.809239
Terai MKanada HSato KYahara TCrabbe JRadke COfek H(1982)A consideration of the number of horizontal grids used in the routing of a masterslice layoutProceedings of the 19th Design Automation Conference10.5555/800263.809196(121-128)Online publication date: 1-Jan-1982
https://dl.acm.org/doi/10.5555/800263.809196
Show More Cited By

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

2-Dilated flattened butterfly: A nonblocking switching topology for high-radix networks

Deadlock-Free Multicast Wormhole Routing in 2-D Mesh Multicomputers

Tofu Interconnect 2: System-on-Chip Integration of High-Performance Interconnect