Transistor reordering for power minimization under delay constraint

ABSTRACT

In this article we address the problem of optimization of VLSI circuits to minimize power consumption while meeting performance goals. We present a method of estimating power consumption of a basic or complex CMOS gate which takes the internal capacitances of the gate into account. This method is used to select an ordering of series-connected transistors found in CMOS gates to achieve lower power consumption. The method is very efficient when used by library-based design styles. We describe a multipass algorithm that makes use of transistor reordering to optimize performance and power consumption of circuits, has a linear time complexity per pass, and converges to a solution in a small number of passes. Transformations in addition to transistor reordering can be used by the algorithm. The algorithm has been benchmarked on several large examples and the results are presented.

REFERENCES

• 1: AGARWALA, S. AND BOSSHART, P. 1994. A linear time algorithm for timing directed optimizations. IEEE International Symposium on Circuits and Systems (May), 107-110.
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: BOBROW, D. G., DEMICHIEL, L. G., GABRIEL, R. G., KEENE, S. E., KICZALES, G., AND MOON, D. A. 1990.Common Lisp object system. In Common Lisp, Digital Press, Maynard, MA, 770-864.
• 4: Richard Burch , Farid Najm , Ping Yang , Timothy Trick, McPOWER: a Monte Carlo approach to power estimation, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.90-97, November 1992, Santa Clara, California, United States
• 5: Bradley S. Carlson , C. Y. Roger Chen, Performance enhancement of CMOS VLSI circuits by transistor reordering, Proceedings of the 30th international conference on Design automation, p.361-366, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164931]
• 6: K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
• 7: J. P. Fishburn, LATTIS: an iterative speedup heuristic for mapped logic, Proceedings of the 29th ACM/IEEE conference on Design automation, p.488-491, June 08-12, 1992, Anaheim, California, United States
• 8: A. Ghosh , S. Devadas , K. Keutzer , J. White, Estimation of average switching activity in combinational and sequential circuits, Proceedings of the 29th ACM/IEEE conference on Design automation, p.253-259, June 08-12, 1992, Anaheim, California, United States
• 9: HARARY, F. 1984. Combinatorial problems in graphical enumeration. In Applied Combinatorial Mathematics, E. F. Beckenbach, Ed., Wiley, New York.
• 10: HITCHCOCK, R. B., SMITH, G. L., AND CHENG, D. D. 1982. Timing analysis of computer hardware. IBM J. Res. Dev, 26, 1 (Jan.), 100-105.
• 11: Wen-Ben Jone , Chen-Liang Fang, Timing optimization by gate resizing and critical path identification, Proceedings of the 30th international conference on Design automation, p.135-140, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164637]
• 12: P. Kollaritsch , S. Lusky , D. Matzke , D. Smith , P. Stanford, A unified design representation can work, Proceedings of the 26th ACM/IEEE conference on Design automation, p.811-813, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74536]
• 13: LIN, B. AND DE MAN, H. 1993. Low-power driven technology mapping under timing constraint. In Proceedings of the International Conference on Computer Design, (Oct.) 421-427.
• 14: Farid N. Najm, Transition density, a stochastic measure of activity in digital circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.644-649, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127744]
• 15: NAJM, F. N. AND HAJJ, I. 1987. The complexity of test generation at transistor level. Rep. UILU-ENG-87-2280, Coordinated Science Lab., Univ. of Illinois at Urbana Champaign, Dec.
• 16: NAJM, F., BURCH, R., YANG, P., AND HAJJ, I. 1990. Probabilistic simulation for reliability analysis of CMOS VLSI circuits. IEEE Trans. Comput.-Aided Des. 9, 4 (April), 439-450.
• 17: PARKER, K. P. AND MCCLUSKEY, E.g. 1975. Probabilistic treatment of general combinatorial networks. IEEE Trans. Comput. C-24 (June), 668-670.
• 18: PRASAD, S. C. AND ROY, K. 1993. Circuit activity driven multi-level logic optimization for low-power reliable operation. In Proceedings of the European Design Automation Conference, (Feb.) 368-372.
• 19: RoY, K. AND PRASAD, S.C. 1993. Circuit activity based logic synthesis for low power reliable operation. IEEE Trans. VLSI Syst. 1, 4 (Dec.) 503-513.
• 20: SAKURAI, T. AND NEWTON, A.R. 1991. Delay analysis of series-connected MOSFET circuits. IEEE J. Solid-State Circuits 26, 2 (Feb.), 122-131.
• 21: SHOJI, M. 1988. CMOS Digital Circuit Technology. Prentice Hall, Englewood Cliffs, NJ.
• 22: Vivek Tiwari , Pranav Ashar , Sharad Malik, Technology mapping for lower power, Proceedings of the 30th international conference on Design automation, p.74-79, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164581]
• 23: TOUATI, H. J., ET AL. 1991. Delay optimization of combinational logic circuits by clustering and partial collapsing. In Proceedings of the IEEE International Conference on CAD, (Nov.) 188-191.
• 24: Hervé J. Touati , Cho W. Moon , Robert K. Brayton , Albert Wang, Performance-oriented technology mapping, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.79-97, March 1990, Boston, Massachusetts, United States
• 25: Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Technology decomposition and mapping targeting low power dissipation, Proceedings of the 30th international conference on Design automation, p.68-73, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164577]
• 26: John P. Uyemura, Fundamentals of MOS digital integrated circuits, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design, Performance

Keywords:
circuit optimization, critical path enumeration, gate input reordering, power estimation, transistor reordering