Fast printed circuit board routing

ABSTRACT

This paper describes the algorithms in a printed circuit board router used for fully automatic routing of high-density circuit boards. Completely automatic routing and running times of a few minutes have resulted from a new data structure for efficient representation of the routing grid, quick searches for optimal solutions, and generalizations of Lee's algorithm.

REFERENCES

• 1: Soukup J., "Circuit Layout", Proc. IEEE, Vol. 69No. 10October 1981, pp. 1281-1304.
• 2: Itaru Aramaki , Tomokazu Kawabata , Kazuhiko Arimoto, Automation of etching-pattern layout, Communications of the ACM, v.14 n.11, p.720-730, Nov. 1971 [doi>10.1145/362854.362886]
• 3: Tetsuo Asano, Parametric pattern router, Proceedings of the 19th conference on Design automation, p.411-417, January 1982
• 4: Moore E.F., "The Shortest Path Through a Maze", Proc. Int. Syrup. on Switching Theory, 1959, pp. 285-292, Harvard University Press
• 5: Lee C. Y., "An Algorithm for Path Connection and its Applications", IRE Transactions on Electronic Computers,September 1961, pp. 346-365.
• 6: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 7: Mikami K., Tabushi K., "A Computer Program for Optimal Routing of Printed Circuit Connectors", IFIPS, 1970, pp. 1475-1478.
• 8: W. Heyns , W. Sansen , H. Beke, A line-expansion algorithm for the general routing problem with a guaranteed solution, Proceedings of the 17th conference on Design automation, p.243-249, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804534]
• 9: Rubin F., "The Lee Connection Algorithm", IEEE Transactions on Computers, Vol. C-23 1974, pp. 907-914.
• 10: Robert K. Korn, An efficient variable-cost maze router, Proceedings of the 19th conference on Design automation, p.425-431, January 1982
• 11: Gary W. Clow, A global routing algorithm for general cells, Proceedings of the 21st conference on Design automation, p.45-51, June 25-27, 1984, Albuquerque, New Mexico, United States
• 12: William A. Dees, Jr. , Patrick G. Karger, Automated rip-up and reroute techniques, Proceedings of the 19th conference on Design automation, p.432-439, January 1982

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance