More Web Proxy on the site http://driver.im/

Article

Free access

Global wiring on a wire routing machine

Authors:

Ray VillaniAuthors Info & Claims

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

Pages 224 - 231

Published: 01 January 1982 Publication History

Abstract

A new global wiring algorithm designed for implementation on special purpose physical design machines is described. This algorithm computes more accurate estimates of wiring channel demand and supply than other known algorithms. It also makes better use of this information in determining wire routes. By exploiting the parallel processing capability of an interconnected array of microcomputers, the global wiring is completed effectively and quickly even for large chips.

References

[1]

S. Akers, "Routing," in Design Automation of Digital Systems: Theory and Techniques, Vol. 1, M. A. Breuer, Ed., Englewood Cliffs, New Jersey: Prentice-Hall, 1972, pp. 283-333.

[2]

T. Blank, M. Stefik and W. vanCleemput, "A Parallel Bit Map Processor Architecture for DA Algorithms," Proceedings of the 19th Design Automation Conference, Nashville, Tennessee, 1981, pp. 837-845.

Digital Library

[3]

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

[4]

K. A. Chen, M. Feuer, K. H. Khokhani, N. Nan and S. Schmidt, "The Chip Layout Problem: An Automatic Wiring Procedure," Proceedings of the 14th Design Automation Conference, New Orleans, Louisiana, 1977, pp. 298-302.

Digital Library

[5]

M. Hanan and J. D. Lesser, "Wire-routing Techniques for Masterslice and Programmable LSI Chips," IBM T. J. Watson Research Center, Yorktown Heights, New York, Research Report RC 7111, 1978.

[6]

W. R. Heller, W. F. Mikhail and W. E. Donath, "Prediction of Wiring Space Requirements in LSI," Journal of Design Automation and Fault Tolerant Computing, vol. 2, no. 2, 1978, pp. 117-144.

[7]

S. J. Hong, R. Nair and E. Shapiro "A Physical Design Machine," in VLSI 81, J. P. Gray, Ed., London: Academic Press, 1981, pp. 257-266.

[8]

C. Y. Lee, "An Algorithm for Path Connections and Its Applications," IRE Transactions on Electronic Computers, EC-10, 1961, pp. 346-365.

[9]

D. T. Lee, S. J. Hong and C. K. Wong, "Number of vias: A Control Parameter for Global Wiring of High Density Chips," IBM Journal of Research and Development, vol. 25, no. 4, 1981, pp. 261-271.

Digital Library

[10]

E.F. Moore, "Shortest Path through a Maze," in Annals of the Computation Laboratory, Cambridge, Massachusetts: Harvard University Press, Cambridge, Massachusetts, 1959, pp. 285-292.

[11]

F. Rubin, "The Lee Connection Algorithm," IEEE Transactions on Computers, vol. C-23, 1974, pp. 907-914.

[12]

H. Shiraishi and F. Hirose, "Efficient Placement and Routing Techniques for Master-Slice LSI," Proceedings of the 17th Design Automation Conference, San Diego, California, 1980, pp. 458-464.

Digital Library

[13]

J. Soukup, "Fast Maze Router," Proceedings of the 15th Design Automation Conference, Las Vegas, Nevada, 1978, pp. 100-102.

Digital Library

[14]

J. Soukup, "Global Router," Proceedings of the 16th Design Automation Conference, San Diego, California, 1979, pp. 481-484.

Digital Library

[15]

J. Soukup and J. C. Royle, "On Hierarchical Routing," Journal of Digital Systems, vol. V, no. 3, 1981, pp. 265-289.

[16]

J. Soukup and U. W. Stockburger, "Routing in Theory and Practice," Proceedings of the First Annual Conference on Computer Graphics in CAD/CAM Systems, Cambridge, Massachusetts, 1979, pp. 129-146.

Cited By

Moffitt MRoy JMarkov IPan DNam G(2008)The coming of age of (academic) global routingProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353662(148-155)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353662
Xing ZChandy JBanerjee P(1997)Parallel Global Routing Algorithms for Standard CellsProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661353Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661353
Brouwer RBanerjee PSmith R(1991)PHIGUREProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123429(650-653)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123429
Show More Cited By

Index Terms

Global wiring on a wire routing machine
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

On global wire ordering for macro-cell routing
DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

In an automatic routing system for macro-cell layout the wiring area is decomposed into a number of smaller regions. These regions are routed separately by a detailed router such as a channel router or a switch-box router. The position of the pins at ...
Multi-layer global routing considering via and wire capacities
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity ...
Multilayer global routing with via and wire capacity considerations

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

9
Total Citations
View Citations
225
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)11

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moffitt MRoy JMarkov IPan DNam G(2008)The coming of age of (academic) global routingProceedings of the 2008 international symposium on Physical design10.1145/1353629.1353662(148-155)Online publication date: 13-Apr-2008
https://dl.acm.org/doi/10.1145/1353629.1353662
Xing ZChandy JBanerjee P(1997)Parallel Global Routing Algorithms for Standard CellsProceedings of the 11th International Symposium on Parallel Processing10.5555/645607.661353Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.5555/645607.661353
Brouwer RBanerjee PSmith R(1991)PHIGUREProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123429(650-653)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123429
Won YSahni SEl-Zig Y(1990)A Hardware Accelerator for Maze RoutingIEEE Transactions on Computers10.1109/12.4629139:1(141-145)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1109/12.46291
Won YSahni SEl-ziq Y(1987)A hardware accelerator for maze routingProceedings of the 24th ACM/IEEE Design Automation Conference10.1145/37888.38014(800-806)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/37888.38014
Watanabe TSugiyama YThomas D(1986)A new routing algorithm and its hardware implementationProceedings of the 23rd ACM/IEEE Design Automation Conference10.5555/318013.318105(574-580)Online publication date: 2-Jul-1986
https://dl.acm.org/doi/10.5555/318013.318105
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
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
Kane RSahni SLambert POfek HO'Neill LPistilli PLosleben PNash JShaklee DPreas BLerman H(1984)A systolic design rule checkerProceedings of the 21st Design Automation Conference10.5555/800033.800803(243-250)Online publication date: 25-Jun-1984
https://dl.acm.org/doi/10.5555/800033.800803

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten