Functional extension of structural logic optimization techniques

ABSTRACT

This work provides a generalization of structural logic optimization methods to general boolean networks. With this generalization, the nodes of the network are no longer restricted to simple gates and can be functions of any size. Within this framework, we present necessary and sufficient conditions to identify all the possible functional expansions of a node that allow to eliminate a wire elsewhere in the network. These conditions are also given for the case of multiple variable expansion, providing an incremental mechanism to perform functional transformations involving any number of variables that can be applied in a very efficient manner. On the other hand, we will show in this paper that relevant simplifications can be obtained when this framework is applied to the particular case of AND-OR-NOT networks, resulting in important savings in the computational effort. When compared to previous approaches, the experimental results show an important reduction in the number of computations required.

REFERENCES

• 1: 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
• 2: L. A. Entrena, K.-T. Cheng. "Combinational and Sequential Logic Optimization by Redundancy Addition and Removal". IEEE Transactions on CAD, vol.14, n. 7, p. 909-916. 1995.
• 3: S.-C. Chang, K.-T. Cheng, N.-S. Woo, M. Marek-Sadowska. "Post-layout logic restructuring using alternative wires". IEEE Transactions on CAD, vol.16, n. 6, p. 587-596. June, 1997.
• 4: S. C. Chang, M. Marek-Sadowska, K.-T. Cheng. "Perturb and Simplify: Multilevel Boolean Network Optimizer". IEEE Transactions on CAD, vol. 15, no. 12, p. 1494-1504. November 1996.
• 5: 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
• 6: Wolfgang Kunz , Dominik Stoffel , Vishwani D. Agrawal , Randal E. Bryant, Reasoning in Boolean Networks: Logic Synthesis and Verification Using Testing Techniques, Kluwer Academic Publishers, Norwell, MA, 1997
• 7: B. Rohfleisch, F. Brglez. "Introduction of permissible bridges with application to logic optimization after technology mapping". Proc. European Design & Test Conference (ED&TC), p. 87-93. February 1994.
• 8: 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]
• 9: Shih-Chieh Chang , Lukas P. P. P. van Ginneken , Malgorzata Marek-Sadowska, Fast Boolean optimization by rewiring, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.262-269, November 10-14, 1996, San Jose, California, United States
• 10: "SIS: A System for Sequential Circuit Synthesis" Report M92/41, University of California, Berkeley, May. 1992.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability

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

General Terms:
Design, Experimentation, Performance, Theory