Power optimization of technology-dependent circuits based on symbolic computation of logic implications

ABSTRACT

This paper presents a novel approach to the problem of optimizing combinational circuits for low power. The method is inspired by the fact that power analysis performed on a technology mapped network gives more realistic estimates than it would at the technology-independent level. After each node's switching activity in the circuit is determined, high-power nodes are eliminated through redundancy addition and removal. To do so, the nodes are sorted according to their switching activity, they are considered one at a time, and learning is used to identify direct and indirect logic implications inside the network. These logic implications are exploited to add gates and connections to the circuit; this may help in eliminating high-power dissipating nodes, thus reducing the total switching activity and power dissipation of the entire circuit. The process is iterative; each iteration starts with a different target node. The end result is a circuit with a decreased switching power. Besides the general optimization algorithm, we propose a new BDD-based method for computing satisfiability and observability implications in a logic network; futhermore, we present heuristic techniques to add and remove redundancy at the technology-dependent level, that is, restructure the logic in selected places without destroying the topology of the mapped circuit. Experimental results show the effectiveness of the proposed technique. On average, power is reduced by 34%, and up to a 64% reduction of power is possible, with a negligible increase in the circuit delay.

REFERENCES

• 1: R. Bahar , M. Burns , G. Hachtel , E. Macii , H. Shin , F. Somenzi, Symbolic computation of logic implications for technology-dependent low-power synthesis, Proceedings of the 1996 international symposium on Low power electronics and design, p.163-168, August 12-14, 1996, Monterey, California, United States
• 2: R. Iris Bahar , Gary D. Hachtel , Enrico Macii , Fabio Somenzi, A symbolic method to reduce power consumption of circuits containing false paths, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.368-371, November 06-10, 1994, San Jose, California, United States
• 3: R. Iris Bahar , Fabio Somenzi, Boolean techniques for low power driven re-synthesis, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.428-432, November 05-09, 1995, San Jose, California, United States
• 4: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 5: CHANDRAKASAN, A. P. AND BRODERSEN, R.W. 1995. Minimizing power consumption in digital cmos circuits. Proc. IEEE 83, 4 (Apr.), 498-523.
• 6: CHANDRAKASAN, A. P., POTKONJAK, M., MEHRA, R., RABEY, J., AND BRODERSON, R. W. 1995. Optimizing power using transformations. IEEE Trans. Comput.-Aided Des. Integr. Circuits 14, 1 (Jan. 1995), 12-31.
• 7: Shih-Chieh Chang , Malgorzata Marek-Sadowska, Perturb and simplify: multi-level boolean network optimizer, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.2-5, November 06-10, 1994, San Jose, California, United States
• 8: CHENG, K. T. AND ENTRENA, L. 1993. Multi-level logic optimization by redundancy addition and removal. In Proceedings of the IEEE European Conference on Design Automation (EURO-DAC '93), IEEE Computer Society Press, Los Alamitos, CA, 373-377.
• 9: CHO, H., HACHTEL, G. D., AND SOMENZI, F. 1993. Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration. IEEE Trans. Comput.- Aided Des. 12, 7 (July), 935-945.
• 10: Olivier Coudert , Ramsey Haddad , Srilatha Manne, New algorithms for gate sizing: a comparative study, Proceedings of the 33rd annual conference on Design automation, p.734-739, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240658]
• 11: Luis Entrena , Kwang-Ting Cheng, Sequential logic optimization by redundancy addition and removal, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.310-315, November 07-11, 1993, Santa Clara, California, United States
• 12: 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
• 13: Sasan Iman , Massoud Pedram, Multi-level network optimization for low power, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.372-377, November 06-10, 1994, San Jose, California, United States
• 14: Sasan Iman , Massoud Pedram, Logic extraction and factorization for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.248-253, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217537]
• 15: Sasan Iman , Massoud Pedram, Two-level logic minimization for low power, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.433-438, November 05-09, 1995, San Jose, California, United States
• 16: IYER, M. A. AND ABRAMOVICI, M. 1994. Low-cost redundancy identification for combinational circuits. In Proceedings of the 7th International Conference on VLSI Design (India, Jan. 1994), 315-318.
• 17: Jawahar Jain , Rajarshi Mukherjee , Masahiro Fujita, Advanced verification techniques based on learning, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.420-426, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217564]
• 18: Kurt Keutzer , Sharad Malik , Alexander Saldanha, Is redundancy necessary to reduce delay, Proceedings of the 27th ACM/IEEE conference on Design automation, p.228-234, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.128295]
• 19: Wolfgang Kunz, HANNIBAL: an efficient tool for logic verification based on recursive learning, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.538-543, November 07-11, 1993, Santa Clara, California, United States
• 20: Wolfgang Kunz , Prem R. Menon, Multi-level logic optimization by implication analysis, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.6-13, November 06-10, 1994, San Jose, California, United States
• 21: Wolfgang Kunz , Dhiraj K. Pradhan, Recursive Learning: An Attractive Alternative to the Decision Tree for Test Genration in Digital Circuits, Proceedings of the IEEE International Test Conference on Discover the New World of Test and Design, p.816-825, September 20-24, 1992
• 22: LIN, B. AND DE MAN, H. 1993. Low-power driven technology mapping under timing constraints. In Proceedings of the 1993 Conference on Computer Design (ICCD '93, Cambridge, MA, Oct. 3-6, 1993), IEEE Computer Society Press, Los Alamitos, CA, 421-427.
• 23: Enrico Macii , Massoud Pedram , Fabio Somenzi, High-level power modeling, estimation, and optimization, Proceedings of the 34th annual conference on Design automation, p.504-511, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266268]
• 24: Bernhard Rohfleisch , Alfred Kölbl , Bernd Wurth, Reducing power dissipation after technology mapping by structural transformations, Proceedings of the 33rd annual conference on Design automation, p.789-794, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240667]
• 25: Berhard Rohfleisch , Bernd Wurth , Kurt Antreich, Logic clause analysis for delay optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.668-672, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217608]
• 26: Kaushik Roy , Sharat Prasad, SYCLOP: Synthesis of CMOS Logic for Low Power Applications, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.464-467, October 11-14, 1992
• 27: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992
• 28: Amelia Shen , Abhijit Ghosh , Srinivas Devadas , Kurt Keutzer, On average power dissipation and random pattern testability of CMOS combinational logic networks, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.402-407, November 1992, Santa Clara, California, United States
• 29: 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]
• 30: TREVILLYAN, L., JOYNER, W., AND BERMAN, L. 1986. Global flow analysis in automatic logic design. IEEE Trans. Comput. C-35, 1 (Jan. 1986), 77-81.
• 31: 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]
• 32: P. Vuillod , L. Benini , G. De Micheli, Re-mapping for low power under tight timing constraints, Proceedings of the 1997 international symposium on Low power electronics and design, p.287-292, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263354]
• 33: YANG, S. 1991. Logic synthesis and optimization benchmarks user guide version 3.0. Microelectronics Center of North Carolina, Research Triangle Park, NC.

INDEX TERMS

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

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

General Terms:
Design

Keywords:
aids, automation, design synthesis, logic design