A gridless router for industrial design rules

ABSTRACT

A point-to-point routing algorithm with three new features is presented. First, the router makes optimal use of oversized, rectangular contacts. Second, it allows different wire width on different layers, with the layers having complete freedom as to routing direction. These two features make the algorithm attractive for MOS layout applications. Finally it is able to realize all-angle routing and to accept all-angle obstacles, a feature interesting for hybrid and PCB routing. The router is gridless and guarantees a solution if one exists. Since it is based on computational geometry algorithms, it offers a low run-time complexity. The ideas have been implemented in a prototype version for 45° routing. The results indicate that the router performs well, even on large designs.

REFERENCES

• 1: C.Y. Lee. An algorithm for path connections and its applLcatlon. IRE Trans. on Electronic computers~ EC- 10:346-365, 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: Ulrich Lauther, A data structure for gridless routing, Proceedings of the 17th conference on Design automation, p.603-609, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804593]
• 4: K. Milmmi and K. Tabuchi. A computer program for optimal routing of printed circuit connectors. IFIPS Proc., H47:1475-1478, 1968.
• 5: 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]
• 6: T. Ohtsulci, M. Sato, and I. Kojima. Computational geometry approach to wire touting design. In Proc. 6th ECCTD, pages 565-567, 1983.
• 7: T. Ohtsuki and M. Sato. Gridless routers for two-layer interconnection. In Proc. ICCAD, pages 76-78, 1984.
• 8: T. Ohtsuki, Layout design and verification, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1986
• 9: M.J. Lorenzetti and D.S. Baeder. Physical Design Automation of VLSI Systems, chapter 5, Routing, pages 157-210. Benjamin/Cununings Publishing Company, Inc., 1986.
• 10: W.L Schiele and Th. Krilger. Report and Conclusion8 from the Analysi~ of Existing Point.to-Point Routers. Technical Report Deliverable C.4.2.1/Siemens/Y1- M9/1, Project Esprit-II 2260, 'SPRITE', September 1989.
• 11: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 12: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 13: W.L. Schiele and Th. Kr/iger. Ein rasterfreler Wegesuchalgorithmus fiir rechtwinklige und schr/ige Verdrahtung. AE~r, Electronics and Communication, 43(4):209-220, July/Aug. 1989.
• 14: E.W. Dijkstra. A note in connexion with graphs. Nu. merische Mathematik, (1):269-271, 1959.
• 15: K. M. Just , W. L. Schiele , T. Krüger, Plowing: modifying cells and routing 45:9D - layouts, Proceedings of the 26th ACM/IEEE conference on Design automation, p.702-705, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74508]
• 16: K.M. Just. Plowing: Incremental layout modification and compaction. In G.W. Zobrist, editor, Pvogress in Computer Aided VLSI Design, Ablex Publishing Corp., 1990. to appear.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design