GENAC: an automatic cell synthesis tool

ABSTRACT

We present a solution to the layout problem of cell synthesis, which achieves multiple optimization objectives. In particular, we propose a new hierarchical method for fast and optimal placement of the transistors in a cell. The method minimizes the number of diffusion breaks, and allows a further pursuit of a secondary optimization objective, such as routing channel density. For cells with non-uniform transistor widths, the transistors are folded in such a way as to optimize a cost function which is a good approximation to the area of the final(compacted) layout of the cell. We also analyze the characteristic nature of routing in cell generation problem, and design an algorithm for doing routing over the transistors; such routing reduces the routing channel density in the central region of the cell. The routing in the central region is completed by a new channel router at, or near, the channel density. The algorithms are implemented in a system call GENAC. The input to GENAC is a transistor net list, describing the connectivity as well as the size and type of each transistor. The output is a synthesized layout of the cell in symbolic language.

REFERENCES

• 1: P.W. Kollaritsch and N. Weste, "Topologizer: An Expert System Translator of Transistor Connectivity to SymboLic Layout," Proceedings ESSCIR.C,1984.
• 2: L.W. Nagel, "ADVICE for Ci.rcuit Simulation," Proceedings of the 1980 International Symposium on Circuits and Systems," Houston, Texas, April 28, 1980.
• 3: N. Weste, "MULGA - An Interactive Symbolic Layout System for the Designa of Integrated Circuits," Bell System Technical Journal, vol.60, No.6, July-Aug. 1981, pp.823-857.
• 4: B.D. Ackland, M.N. Condict, A.E. Dunlop, J.P. F;ishbum, D.D, HiLt, V.E. Kelly, K.W. Keutzer, H.S. Moscovitz, J.D. Tauke, "The IMAGES Symbolic Layout Language," lieu Laboratories Technical Memorandum 52231-85-02-08-01TM, May 1, 1986.
• 5: T.Uehara and W.M.vanCleemput, "Optimal layout of CMOS functional arrays," IEEE Trans. Comput., vol. C- 30, 5, pp.305-312, May 1981.
• 6: R.Nair, A. Bruss, and J.Reif, "L~near time algorithms for optimal CMOS layout," in VI_SI: Atgo6_thms and Architectures, P.Bertolazzi and F.Luccio, Eds. New York: Elsevier North-Holland, 1985, pp.327-338.
• 7: 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]
• 8: D.t-Lill, "SC2--A hybrid automatic layout system," Proc. ICCAD, Nov. 1985, pp. 172-174.
• 9: S. Wimer, R.Y. Pinter, and I.A. Feldman, "Optimal Chaining of CMOS Transistors in a Functional Cell," IEEE Trans. on CAD, vol, CAD-6, No.5, 1987, pp.795.
• 10: S.Goto, I. Cederbaum, B.S. Ting, "Suboptimal Solution of the Backboard Ordering with Channel Capacity Constraint," IEEE Trans. on Circuits and Systems, Nov.1977, pp.645-652.
• 11: I.T. Li, "Algorithms for Gate Matrix Layout," Proc. 1983 IEEE Int. Syrup. Circuits and Systems. May, 1983, pp. 1013-1016.
• 12: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• 13: 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]
• 14: T. Yoshimura and E.S. Kuh, "Efficient Algorithms for Channel Routing," IEEE Trans. on CAD of Integrated Circuits and Systems, voI.CAD-1, Jan.1982, pp.25-35.
• 15: R. Varadarajan, to be published.
• 16: C.J. Poirier, "EXELLERATOR: Automatic Leaf Cell Layout Agent," ICCAD November, 1987.
• 17: Y.-L. S. Lin , D. D. Gajski, LES: a layout expert system, Proceedings of the 24th ACM/IEEE conference on Design automation, p.672-678, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37996]
• 18: T. Lengauer and R. Muller, "Linear Algorithms for Optimizing the Layout of Dynamic CMOS Ceils," IEEE Trans. on Circuits and Systems, vol.35, No.3, March 1988, pp.279-285.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

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

General Terms:
Algorithms, Design, Performance