A “Dogleg” channel router

ABSTRACT

This paper presents an algorithm for interconnecting two sets of terminals across an intervening channel. It is assumed that the routing is done on two distinct levels with all horizontal paths being assigned to one level and all vertical paths to the other. Connections between the levels are made through contact windows. A single net may result in many horizontal and vertical segments. Experimental results indicate that this algorithm is very successful in routing channels that contain severe constraints. Usually, the routing is accomplished within one track of the mathematical lower bound. The routing algorithm presented here was developed as part of LTX, a computer-aided design system for integrated circuit layout and was implemented on an HP-2100 minicomputer. A typical channel (300 terminals, 100 nets) can be routed in less than 5 seconds. Routing results are presented both for polycell chips under development at Bell Laboratories and for examples that exist in the published literature. For the latter, reductions of 10% in the wiring area were typical.

REFERENCES

• 1: Lee, C. Y., "An Algorithm for Path Connections and Its Applications," IRE Transactions on Electronic Computers, pp. 346-365, September 1961.
• 2: 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]
• 3: Roland L. Mattison, A high quality, low cost router for MOS/LSI, Proceedings of the 9th workshop on Design automation, p.94-103, June 26-28, 1972 [doi>10.1145/800153.804934]
• 4: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• 5: B. W. Kernighan , D. G. Schweikert , G. Persky, An optimum channel-routing algorithm for polycell layouts of integrated circuits, Proceedings of the 10th workshop on Design automation, p.50-59, June 25-27, 1973
• 6: Tokinori Kozawa , Hiroshi Horino , Tadakatu Ishiga , Junya Sakemi , Shoji Sato, Advanced LILAC - an Automated Layout Generation system for MOS/LSIs, Proceedings of the 11th workshop on Design automation, p.26-46, January 1974
• 7: G. Persky , D. N. Deutsch , D. G. Schweikert, LTX - a system for the directed automatic design of LSI circuits, Proceedings of the 13th conference on Design automation, p.399-407, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804840]
• 8: Kozawa, T., Horino, H., Watanabe, K., Nagata, M. and Hukuda, H., "Block and Track Method for Automated Layout Generation of MOS-LSI Arrays," IEEE International Solid-State Circuits Conference, Digest of Technical Papers, Vol. XV, IEEE Cat. No. 72C3-ISSCC, pp. 62-3 and pp. 214-215 (1972).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance