Generation of layouts from MOS circuit schematics: a graph theoretic approach

ABSTRACT

A graph model is proposed to capture the topological properties of metal-oxide semiconductor (MOS) transistors and interconnections among transistors. A set of algorithms is devised for the enumeration of layout topologies of a circuit from its graph model. Layout topologies are presented in stick diagrams. The algorithms select a set of embedded layout topologies with the “fewest” number of jumpers for layout generation and compaction. Layouts for circuits with up to 36 transistors have been generated successfully. The layouts corresponding to the topologies generated and selected by the algorithms are, in most cases, smaller than compact hand layouts. The worst case computational complexity is O(n 2), where n is the number of transistors in the circuit.

REFERENCES

• 1: W. Wolf, J. Newkirk, R. Mathews and R. Dutton, "Dumbo, a schematic-to-layout compiler," in R. Bryant, (ed.), Proc. Third Caltech Conference on VLSI, Computer Science Press, pp. 379-394, 1983.
• 2: N. Rose and J. 01dfield, "Printed-wiring-board layout by computer," Electronics and Power, pp. 373-380, Oct. 1971.
• 3: W. Engl, D. Mlynski and P. Pernards, "Computer-aided topological design for integrated circuits," IEEE Trans. Circuit Theory, vol. CT-20, no. 6, pp. 717-725, 1973.
• 4: M. VanLier and R. Otten, "Automatic IC layout: the model and technology," IEEE Trans. on Circuits and Systems, vol. CAS-22, no. ii, pp. 845-854, 1975.
• 5: A. Goldstein and D. Schweikert, "A proper model for testing the planarity of electrical circuits," The Bell Sys. Tech. J., vol. 52, no. i, pp. 135-142, 1973.
• 6: W. VanCleemput, "Mathematical models for the circuit layout problem," IEEE Trans. Circuits and Systems, vol. CAS-23, no. 12, pp. 759-767, 1976.
• 7: T. Ng, A Graph Model and the Embedding of MOS Circuit, T.R. 5104, Gomputer Science Department, California Institute of Technology, 1983.
• 8: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 9: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 10: Y. Lao and C. Wong, "An algorithm to compact a VLSI symbolic layout with mixed constraints," IEEE Trans. CAD of IC and Sys., vol. CAD-2, no. 2, pp. 62-69, 1983. and Sys., Vol. CAD-2, No. 2, 62-69.
• 11: D. Johannsen, S~licon Compilation, T.R. 4530, Computer Science Department, California Institute of Technology, 1981.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies
      B.7.2 Design Aids
          Subjects: Layout

  J. Computer Applications

General Terms:
Algorithms, Design, Performance, Theory