Article

Free access

The interconnection problem - a tutorial

Author:

David W. HightowerAuthors Info & Claims

DAC '73: Proceedings of the 10th Design Automation Workshop

Pages 1 - 21

Published: 25 June 1973 Publication History

Abstract

This paper represents a fairly extensive survey of the literature on the interconnection problem. The topics covered are: Pin Assignment, Layering, Ordering, Wire List Determination, Spanning Trees, Rectilinear Steiner Trees and Wire Layout. In addition, several new ideas are presented which could provide for better wire layout. Algorithms are presented in a way that makes them easy to understand and hence, to discuss and apply. Formal statement of the algorithms can be found in the references cited.

References

[1]

Loberman, H. and Weinberger, A., "Formal Procedures for Connecting Terminals with a Minimum Total Wire Length." J. ACM, Vol. 4(Oct., 1957), pp. 428-437.

Digital Library

[2]

Lass, S., "Automated Printed Circuit Routing with a Stepping Aperture." Comm. ACM, Vol. 12, No. 5, May, 1969.

Digital Library

[3]

Gilbert, E. and Pollak, H., "Steiner Minimal Trees." SIAM J. Math., Vol. 16(1968), pp. 1-29.

Digital Library

[4]

Hardgrave, W., "On the Relationship Between the Traveling Salesman and Longest Path Problems." Bell System Monograph No. 4336.

[5]

Freitag, H., "Design Automation for Large Scale Integration." IBM Watson Research Center, Yorktown Heights, N. Y., Presented at the Western Electronic Showland Convention, August 22-26, 1966.

[6]

Lin, S., "Computer Solutions of the Traveling Salesman Problem," Bell System Technical Journal, Vol. 44, 1965, pp. 2245-2269

[7]

Altman, G. et al, "Automation of Computer Panel Wiring." Trans. AIEE, Vol. 79, Part 1(May, 1960), pp. 118-125.

[8]

Michle, W. "Link-Length Minimization in Networks." J. Oper. Res., Vol. 6(1958), pp. 232-243.

Digital Library

[9]

Mikami, K. and Tabushi, K., "A Computer Program for Optimal Routing of Printed Circuit Connectors." IFIPS Proc., Vol. 1475-1478.

[10]

Brown, R. and Putnam, G., "The Automation of Backwiring Design and Topological Layout." AIEE Trans. (1962), pp. 136-139.

[11]

Akers, S., "A Modification of Lee's Path Connection Algorithm." IEEE Trans. on Elec. Comp., Vol. EC-16, No. 1 (February, 1967), pp. 97-98.

[12]

Hitchcock, R., "Cellular Wiring and the Cellular Modeling Technique." Proc. 6th Design Automation Workshop, 1969, pp. 25-41.

Digital Library

[13]

Kruscal, J., "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proc. Amer. Math. Soc., Vol. 7(1956) pp. 48-50.

[14]

Ramamoorthy, C., "Analysis of Graphs by Connectivity Considerations." J. ACM, Vol. 13 (April, 1966), pp. 211-222.

Digital Library

[15]

Hanan, M., "On Steiner's Problem with Rectilinear Distance." SIAM J. Appl. Math., Vol. 14, No. 2 (March, 1966), pp. 255-265.

Digital Library

[16]

Geyer, J., "Connection Routing Algorithm for Printed Circuit Boards." IEEETCT, Vol. C-20, January, 1971.

[17]

Dantzig, G., et al, "Solution of a Large Scale Traveling Salesman Problem." J. Oper. Res., Vol. 2, (1954), pp. 394-410.

[18]

Breuer, M., "Recent Developments in Design Automation." Computer, (May, 1972), pp. 23-35.

Digital Library

[19]

Hanan, M. and Kurtzberg, J., "A Review of the Placement and Quadratic Assignment Problems." IBM Research Report, RC 3046, April, 1970.

[20]

Hanan, M. and Oden, P., "A Wiring Problem for Large Scale Integrated Circuits." IBM Research Report No. RC-1615, May 17, 1966.

[21]

Kernighan, B. and Lin, S., "An Efficient Heuristic Procedure for Partitioning Graphs." The Bell Sys. Tech. J. Vol. 49, No. 2, Feb. 1970, pp. 291-307.

[22]

Rose, N. et al, "Printed Wiring Board Layout by Computer." Electronics and Power, (October, 1971), pp. 376-379.

[23]

Harvey, J., "Automated Board Layout." Proc. Design Auto. Workshop, 1972, pp. 264-271.

Digital Library

[24]

Koren, N., "Pin Assignment in Automated Printed Circuit Board Design." Proc. Design Auto. Workshop, 1972, pp. 72-79.

Digital Library

[25]

Mah, L. and Steinberg, L., "Topologic Class Routing for Printed Circuit Boards." Proc. Design Auto. Workshop, 2972, pp. 80-93.

Digital Library

[26]

Mattison, R., "A High Quality, Low Cost Router for MOS/LSI." Proc. Design Auto. Workshop, 1972, pp. 94-103.

Digital Library

[27]

Oestreicher, D., "Automatic Printed Circuit Board Design." University of Utah Computer Science Division, UTEC-CSc-72-119, June, 1972.

[28]

Lee, C., "An Algoritm, for Path Connections and Its Applications." IRE Trans. On E. C. (September, 1961), pp. 346-365.

[29]

"Minutes of the Meeting of the IEEE Circuits Standards Committee." Naval Postgraduate School, Monterey, Calif., May 8-9, 1969.

[30]

Moore, E., "Shortest Path Through a Maze." Harvard University Press, Cambridge, Mass., Vol. 30 (1959), pp. 285-292.

[31]

Aramaki, I. et al, "Automation of Etching-Pattern Layout." Comm. ACM, Vol. 14, No. 11, November, 1971, pp. 720-730.

Digital Library

[32]

Heiss, S., "A Path Connection Algorithm for Multi-layer Boards." Proc. Design Auto. Workshop, 1968, pp. 6-1-6-14.

Digital Library

[33]

Abel, L., "On the Automated Layout of Multi-Layer Planar Wiring and a Related Graph Coloring Problem." Coordinated Science Laboratory Report No. R-546, University of Ill., January, 1972.

[34]

Brown, J. et al, "Design Automation and the Wrap System." Proc. Design Auto. Workshop, 1968, pp. 19-1-19-30.

Digital Library

[35]

Hightower, D., "A Solution to Line Routing Problems on the Continuous Plane." Proc. Design Auto. Workshop, 1969, pp. 1-24.

Digital Library

[36]

Hashimoto, A. and Stevens, J., "Wire Routing by Optimizing Channel Assignment within Large Apertures." Proc. Design Auto. Workshop, 1969, pp. 155-169.

Digital Library

[37]

Bittner, B. and Ulrich, J., "A Method for Improving the Location of Connecting Paths for Circuit Card Wiring." Thomas Bede Foundation Report No. R-68-128.

[38]

Cameron, S., referenced in article 18.

[39]

Freeman, "Multilayer Printed Wiring - Computer Aided Design." Proc. Design Auto. Workshop, 1967, pp. 16-1-16-28.

Digital Library

[40]

Ginsberg, G. et al, "An Updated Multilayer Printed Wiring CAD Capability." Proc. Design Auto. Workshop, 1969, pp. 145-154.

Digital Library

[41]

Fisk, C. and Isett, D., "ACCEL Automated Circuit Card Etching Layout." Proc. Design Auto. Workshop, 1965, pp. 5-32.

Digital Library

[42]

Hightower D. and Unger, B., "A Method for Rapid Testing of Beam Crossover Circuits." Proc. Design Auto. Workshop, 1972, pp. 144-156.

Digital Library

[43]

Abel, L., "On the Ordering of Connections for Automatic Wire Routing." IEEE Trans. on Comp. Nov, 1972.

Digital Library

[44]

Foster, J. "A Router for Multilayer Printed Wiring Back Planes." Proc. Design Automation Workshop, June, 1973.

Digital Library

[45]

Prim, R., "Shortest Connection Networks and Some Generalizations." Bell Sys. Tech J. Vol 36 (November, 1957).

[46]

Hightower, D. W., "Interconnection Techniques.", Proc. 1972 International Seminar on Design Automation. ILTAM, Jereusalem, Israel.

[47]

Adshead, H. G., "Optimizing Automatic Tracking of Multilayer Boards." AGARD Conference: Computer Aided Design for Electronic Circuits, Copenhagen, May, 1973.

[48]

Lapidot, Z. - private communication.

Cited By

Dees WSmith R(1981)Performance of interconnection rip-up and reroute strategiesProceedings of the 18th Design Automation Conference10.5555/800073.802333(382-390)Online publication date: 29-Jun-1981
https://dl.acm.org/doi/10.5555/800073.802333
Tsui RSmith R(1981)A high-density multilayer PCB router based on necessary and sufficient conditions for single row routingProceedings of the 18th Design Automation Conference10.5555/800073.802332(372-381)Online publication date: 29-Jun-1981
https://dl.acm.org/doi/10.5555/800073.802332
Lorenzetti MSmith RHassler ESmith RPistilli PAbel LCrabbe JBening LShaklee DRadke C(1980)An implementation of a saturated zone multi-layer printed circuit board routerProceedings of the 17th Design Automation Conference10.1145/800139.804536(255-262)Online publication date: 23-Jun-1980
https://dl.acm.org/doi/10.1145/800139.804536
Show More Cited By

Index Terms

The interconnection problem - a tutorial
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
  2. Integrated circuits
    1. Interconnect
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Estimating Pre-Placement FPGA Interconnection Requirements
VLSID '04: Proceedings of the 17th International Conference on VLSI Design

With increasing device and design sizes, InterconnectPlanning is fast becoming an important design issue for largeFPGA based designs. The fundamental requirement for interconnectplanning is the ability to estimate the routing requirementsof a given ...
Geometric interconnection and placement algorithms
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '73: Proceedings of the 10th Design Automation Workshop

June 1973

296 pages

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Press

Publication History

Published: 25 June 1973

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

6
Total Citations
View Citations
751
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dees WSmith R(1981)Performance of interconnection rip-up and reroute strategiesProceedings of the 18th Design Automation Conference10.5555/800073.802333(382-390)Online publication date: 29-Jun-1981
https://dl.acm.org/doi/10.5555/800073.802333
Tsui RSmith R(1981)A high-density multilayer PCB router based on necessary and sufficient conditions for single row routingProceedings of the 18th Design Automation Conference10.5555/800073.802332(372-381)Online publication date: 29-Jun-1981
https://dl.acm.org/doi/10.5555/800073.802332
Lorenzetti MSmith RHassler ESmith RPistilli PAbel LCrabbe JBening LShaklee DRadke C(1980)An implementation of a saturated zone multi-layer printed circuit board routerProceedings of the 17th Design Automation Conference10.1145/800139.804536(255-262)Online publication date: 23-Jun-1980
https://dl.acm.org/doi/10.1145/800139.804536
Nishioka IKurimoto TNishida HBrinsfield JSzygenda SHightower D(1977)A minicomputerized automatic layout system for two-layer printed wiring boardsProceedings of the 14th Design Automation Conference10.5555/800262.809099(1-11)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.5555/800262.809099
Dobes I(1977)A multi-contouring algorithmACM SIGDA Newsletter10.1145/1061447.10614487:2(2-11)Online publication date: 1-Jun-1977
https://dl.acm.org/doi/10.1145/1061447.1061448
Rau BHumcke DGaley JSzygenda SPistilli PDooner NBrinsfield JOlila J(1976)A new philosophy for interconnection on multilayer boardsProceedings of the 13th Design Automation Conference10.1145/800146.804818(225-231)Online publication date: 28-Jun-1976
https://dl.acm.org/doi/10.1145/800146.804818

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

Media

Figures

Other

Tables

View Table of Contents