Logic transformation for low-power synthesis

ABSTRACT

In this article we present a new approach to the problem of local logic transformation for reducing power dissipation in logic circuits. The proposed approach overcomes one of the critical limitations common to the previous approaches of local logic transformations for low power, namely, a sequential greedy transformation that identifies signals with high switching activities and then resynthesizes the signals one by one. Instead, we identify a set of signal lines as a group for logic transformation, and determine an order of transformation of the signals with the maximum reduction of power dissipation in the circuit. As a practically feasible solution to this problem, we develop a power model called a finite state input transition (FIT) model, which allows the efficient measurement of the change of power dissipation of the circuit for every possible sequence of logic transformations among the signal lines. Experimental results show that the proposed approach performs an extensive local logic transformation, reducing power consumption by 33% on average without any increase of circuit delay.

REFERENCES

• 1: Alessandro Bogiolo , Luca Benini , Bruno Riccò, Power estimation of cell-based CMOS circuits, Proceedings of the 33rd annual conference on Design automation, p.433-438, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240601]
• 2: Chang, S. C., Marek-Sadowska, M., and Cheng, K. T. 1996. Perturb and simplify: Multilevel Boolean network optimizer. IEEE Trans. Comput. Aided Des. 15, 12 (Nov.), 1494--1504.
• 3: Olivier Coudert , Ramsey Haddad, Integrated resynthesis for low power, Proceedings of the 1996 international symposium on Low power electronics and design, p.169-174, August 12-14, 1996, Monterey, California, United States
• 4: George, B. J., Yeap, G., Wloka, M. G., Tyler, S. C., and Gossain, D. 1994. Power analysis for semi-custom design. In Proceedings of the IEEE Custom Integrated Circuits Conference, 249--252.
• 5: Jan-Min Hwang , Feng-Yi Chiang , TingTing Hwang, A re-engineering approach to low power FPGA design using SPFD, Proceedings of the 35th annual conference on Design automation, p.722-725, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277225]
• 6: Iman, S. and Pedram, M. 1996a. An approach for multilevel logic optimization targeting low power. IEEE Trans. Comput. Aided Des. 15, 8 (Aug.), 889--901.
• 7: Sasan Iman , Massoud Pedram, POSE: power optimization and synthesis environment, Proceedings of the 33rd annual conference on Design automation, p.21-26, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240522]
• 8: Kang, S. M. and Leblebici, Y. 1999. CMOS Digital Integrated Circuits: Analysis and Design. 2nd ed. McGraw-Hill, Hightstown, N.J.
• 9: Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, (April), 291--307.
• 10: Kunz, W. and Pradhan, D. K. 1994. Recursive learning: A new implication technique for efficient solutions to CAD problems: Test, verification and optimization. IEEE Trans. Comput. Aided Des. 13, 9 (Sept.), 1143--1158.
• 11: Jiing-Yuan Lin , Tai-Chien Liu , Wen-Zen Shen, A cell-based power estimation in CMOS combinational circuits, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.304-309, November 06-10, 1994, San Jose, California, United States
• 12: Marculescu, D., Marculescu, R., and Pedram, M. 1996. Information theoretic measures for power analysis. IEEE Trans. Comput. Aided Des. 15, 6 (June), 599--610.
• 13: Radu Marculescu , Diana Marculescu , Massoud Pedram, Switching activity analysis considering spatiotemporal correlations, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.294-299, November 06-10, 1994, San Jose, California, United States
• 14: S. Muroga , Y. Kambayashi , H. C. Lai , J. N. Culliney, The Transduction Method-Design of Logic Networks Based on Permissible Functions, IEEE Transactions on Computers, v.38 n.10, p.1404-1424, October 1989 [doi>10.1109/12.35836]
• 15: Najm, F. 1993. Transition density: A new measure of activity in digital circuits. IEEE Trans. Comput. Aided Des. 12, 2 (Feb.), 310--323.
• 16: Rajendran Panda , Farid N. Najm, Technology-dependent transformations for low-power synthesis, Proceedings of the 34th annual conference on Design automation, p.650-655, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266310]
• 17: Massoud Pedram, Power minimization in IC design: principles and applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.3-56, Jan. 1996 [doi>10.1145/225871.225877]
• 18: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 19: 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]
• 20: Janardhan H. Satyanarayana , Keshab K. Parhi, HEAT: hierarchical energy analysis tool, Proceedings of the 33rd annual conference on Design automation, p.9-14, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240520]
• 21: 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]
• 22: H. Ueda , K. Kinoshita, Low power design and its testability, Proceedings of the 4th Asian Test Symposium, p.361, November 23-24, 1995
• 23: Qi Wang , Sarma B. K. Vrudhula, Multi-level logic optimization for low power using local logic transformations, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.270-277, November 10-14, 1996, San Jose, California, United States
• 24: Shigeru Yamashita , Hiroshi Sawada , Akira Nagoya, A new method to express functional permissibilities for LUT based FPGAs and its applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.254-261, November 10-14, 1996, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles

General Terms:
Algorithms, Performance

Keywords:
Logic synthesis, logic transformation, low power, power estimation model