An efficient transistor folding algorithm for row-based CMOS layout design

ABSTRACT

In timing-driven layout synthesis, transistor sizes tend to besignificantly different from each other and thus the use of conventionallayout approaches can cause inefficient area utilization.We propose an efficient algorithm to find the optimaltransistor folding sizes in row-based designs.Our algorithmfinds optimal folding sizes given a CMOS circuit with m pairsof pMOS and nMOS transistors in O(m{2} log m) time complexitywith the effective reduction of the solution space.MCNCbenchmark circuits are used to demonstrate the area-efficiencyof the physical layouts with optimal folding sizes.

REFERENCES

• 1: S. S. Sapatnekar et al., "An exact solution to the transistor sizing problem for CMOS circuits using convex optimization," IEEE Trans. CAD, pp. 1621-1634, Nov. 1993.
• 2: J. P. Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," Proc. 1985 1CCAD, pp. 326-328, 1985.
• 3: J. Shyu et al., "Opt!mization-based transistor sizing," IEEE J. Solid-State C'ircuits, pp. 400-409, Apr. 1988.
• 4: Z. Dai and K. Asada, "MOSIZ: A two-step transistor sizing algorithm based on optimal timing assingment method for multi-stage complex gates," Proc. 1989 CICC, pp. 17.3.1-17.3.4, May 1989.
• 5: Yung-Ching Hsieh , Chi-Yi Hwang , Youn-Long Lin , Yu-Chin Hsu, LiB: a cell layout generator, Proceedings of the 27th ACM/IEEE conference on Design automation, p.474-479, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123343]
• 6: T. W. Her and D. F. Wong, "Cell Area Minimization by Transistor Folding," Proc. 1993 Euro-DAC, pp.172-177, 1993.
• 7: T. Uehara and W. M. VanCleemput. "Optimal layout of CMOS functional arrays," Proc. IEEE Transactions of Computers, vol. 30, pp. 305-312, May 1981.
• 8: J. Kim and S. M. Kang, "High Performance CMOS Macromodule Layout Synthesis," Proc 199~ ISCAS, 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation; Layout

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification