A topologically adaptable cellular router

ABSTRACT

This paper describes a printed circuit routing program based on a cellular least-cost path finding algorithm. The program uses four bits of random access storage per cell and provides a mechanism for programming the path-cost function to model a variety of physical constraints.

REFERENCES

• 1: C. S. Slemaker , R. C. Mosteller , L. W. Leyking , A. G. Livitsanos, A programmable printed-wiring router, Proceedings of the 11th workshop on Design automation, p.314-321, January 1974
• 2: James Riley Allen, A minimum cost path algorithm for printed circuit routing., 1976
• 3: G. J. Miron , S. R. Tarrant, The automatic printed wire routing system of BACKIS, Proceedings of the 12th conference on Design automation, p.311-316, January 1975
• 4: Moore, E. F., "The Shortest Path Through a Maze," Proceedings of an International Symposium on the Theory of Switching - Part 2, The Annals of the Computation Laboratory of Harvard University, Harvard University Press, Vol. 30(1959), pp. 285-292, April 1957. Bell System Monograph Number 3523.
• 5: Parks, H. L., "Three-dimensional IC packaging - with a twist," Electronics, Vol. 45, No. 3, pp. 62-65, January 1972.
• 6: Lee, C. Y., "An Algorithm for Path Connections and its Applications," IRE Transactions on Electronic Computers, Vol. EC-10, pp. 346-365, September 1961.
• 7: Danzig, A. C., "A Multiwire Writing Technology for Advanced Electronics Packaging," Proceedings of the Technical Program of the National Electronic Packaging and Production Conference, pp. 141-147, June 1973.

INDEX TERMS

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

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

General Terms:
Design, Performance