The layout synthesizer: an automatic Netlist-to-Layout system

ABSTRACT

A system generating compacted physical layouts from MOS transistor netlists has been developed. It uses a novel graph-theoretical placement algorithm to simultaneously maximize diffusion sharing and minimize the wiring area. The algorithm is not limited to circuits that have equal numbers of NMOS and PMOS transistors. A special-purpose router using either one-layer or two-layer metal is described. Experimental results for area efficiency and run-time performance are very promising.

REFERENCES

• 1: Donald G. Baltus , Jonathan Allen, SOLO: a generator of efficient layouts from optimized MOS circuit schematics, Proceedings of the 25th ACM/IEEE conference on Design automation, p.445-452, June 12-15, 1988, Atlantic City, New Jersey, United States
• 2: Y. E. Cho , A. J. Kroenjak , D. E. Stockton, FLOSS: an approach to automated layout for high-volume designs, Papers on Twenty-five years of electronic design automation, p.138-141, June 1988 [doi>10.1145/62882.62895]
• 3: K. Hall, "An r-Dimensional Quadratic Placement Algorithm," Management Science, vol. 17, pp. 219-229, Nov. 1970.
• 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: D. Hill, "Sc2: A Hybrid Automatic Layout System,'" Proceedings of the ICCAD, pp. 172-174, 1985.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: P. Kollaritsch and N. Weste, "TOPOLOGIZER: An Expert System Translator of Transistor Connectivity ~) Symbolic Cell Layout," IEEE Journal of Solid-State Circuits, Vol. Sc-20, No. 3, pp.799-804, 1985.
• 8: E. Lawler, "Combinatorial Optimization:: Networks and Matroids,"Holt, Rinehm-t and Winston, 1976.
• 9: Y. Liao and C. Wong, "An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraint's", IEEE Transaction on CAD, Vol. CAD-2, No. 2, pp. 62-69, April 1983.
• 10: Y. Lin and D. Gajski, "LES: A Layout Expert System," IEEE Transactions on CAD, Vol. CAD-7, no. 8, pp. 868- 876, August 1988.
• 11: F. Mailhot and G. DeMicheli, "Automatic Layout ~md Optimization of Static CMOS Cells," Proceedings of the ICCD, pp. 180-185, 1988.
• 12: R. L. Maiasz , J. P. Hayes, Layout optimization of CMOS functional cells, Proceedings of the 24th ACM/IEEE conference on Design automation, p.544-551, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37969]
• 13: R. Nair, A. Bruss, and J. Reif, "Linear Time Algorithms for Optimal CMOS Layout," VLSI: Algorithms and Architectures, pp. 327-338, 1985.
• 14: Yoichi Shiraishi , Jun'ya Sakemi , Makoto Kutsuwada , Akira Tsukizoe , Takashi Satoh, A high packing density module generator for CMOS logic cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.439-444, June 12-15, 1988, Atlantic City, New Jersey, United States
• 15: T. Uehara, and W. vanCleemput, "Optimal layout of CMOS Functional Arrays," IEEE Transactions on Computers, Vol. C-30, No. 5, pp. 305-312, 1981.
• 16: S. Wimer, R. Pinter, and J. Feldmart, "O$~timal Chaining of CMOS Transistors in a Functional Cell," IEEE Transactions on Computer-Aided Design, Vol. CAD-30, No. 5, pp. 795-801, 1987.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout

General Terms:
Algorithms, Design, Experimentation, Theory