Local transformation techniques for multi-level logic circuits utilizing circuit symmetries for power reduction

ABSTRACT

In this pap er, we present sever al optimization techniques for power reduction utilizing circuit symmetries. There are four kinds of symmetries that we dete ct in a given circuit implementation. First, we pr op ose an algorithm for dete cting the four different typ es ofsymmetries in a given circuit implementation of a Boole an function. Sever alre-synthesis techniques utilizing such symmetries are prop ose d. These techniques enable us to optimize power consumption and delay with no (or very little) ar ea overhead. We have carrie dout experiments on MCNC benchmark circuits to demonstrate the efficiency of the prop ose dtechniques. The aver age power reduction is 14% with little or none ar ea and/or delay overhead.

REFERENCES

• 1: Ft. K. Brayton, G. D. Hachtel, and A. L. Sangiovanii-Vincentelli. Multilevel logic synthesis. Proceedings of the IEEE, 78(2):264- 300, February 1990.
• 2: S. R. Das and C. L. Sheng. On detecting total and partial symmetry of switching functions. IEEE Transactions on Computers, 20(3):352-355, March 1971.
• 3: Donald L. Dietmeyer and Peter R. Schneider. Identification of symmetry, redundancy and equivalence of boolean functions. IEEE Transactions on Electronic Computers, EC-16(6):804- 817, December 1967.
• 4: Colin R. Edwards and S. L. Hurst. A digital synthesis procedure under function symmetries and mapping methods. IEEE Transactions on Computers, C-27(11):985-997, November 1978.
• 5: Sasan Iman and Massoud Pedram. An approach for multilevel logic optimization targeting low power. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(8):889-901, August 1996.
• 6: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
• 7: Wolfgang Kunz and Dhiraj K. Pradhan. Recursive learning: A new implication technique for efficient solutions to cad problems = test, verification, and optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(9):1069-1078, September 1994.
• 8: 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
• 9: Dirk Möller , Janett Mohnke , Michael Weber, Detection of symmetry of Boolean functions represented by ROBDDs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.680-684, November 07-11, 1993, Santa Clara, California, United States
• 10: 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]
• 11: 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]
• 12: Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States
• 13: 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]
• 14: 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
• 15: 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]
• 16: Vivek Tiwari , Sharad Malik , Pranav Ashar, Guarded evaluation: pushing power management to logic synthesis/design, Proceedings of the 1995 international symposium on Low power design, p.221-226, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224120]
• 17: Chien-Chung Tsai , Malgorzata Marek-Sadowska, Generalized Reed-Muller Forms as a Tool to Detect Symmetries, IEEE Transactions on Computers, v.45 n.1, p.33-40, January 1996 [doi>10.1109/12.481484]
• 18: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
  B.8 Performance and Reliability

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

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

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