Perturb and simplify: multi-level boolean network optimizer

ABSTRACT

In this paper, we discuss the problem of optimizing a multi-level logic combinational Boolean network. Our techniques apply a sequence of local perturbations and modifications of the network which are guided by the automatic test pattern generation ATPG based reasoning. In particular, we propose several new ways in which one or more redundant gates or wires can be added to a network. We show how to identify gates which are good candidates for local functionality change. Furthermore, we discuss the problem of adding and removing two wires, none of which alone is redundant, but when jointly added/removed they do not affect functionality of the network. We also address the problem of efficient redundancy computation which allows to eliminate many unnecessary redundancy tests. We have performed experiments on MCNC benchmarks and compared the results to those of misII and RAMBO. Experimental results are very encouraging.

REFERENCES

• 1: K.A. Bartlett et al, "Multilevel Logic Minimizing Using Implicit Don't cares," IEEE Trans. on CAD-7(6), pp. 723-740(June 1988).
• 2: C. L. Berman and L. H. Trevillyan. "Global Flow Optimization in Automatic Logic Design," IEEE Trans. CAD 10, pp. 557-564(May 1991).
• 3: D. Bostick et al, "The Boulder Optimal Logic Design System," Proc. ICCAD, pp. 62-65, 1987.
• 4: R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A.R. Wang, "MIS: Multi-level Interactive Logic Optimization System," IEEE Trans. on CAD, CAD-6(6), pp. 1062-1081(Nov. 1989).
• 5: Shih-Chieh Chang , Kwang-Ting Cheng , Nam-Sung Woo , Malgorzata Marek-Sadowska, Layout driven logic synthesis for FPGAs, Proceedings of the 31st annual conference on Design automation, p.308-313, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196388]
• 6: K.T. Cheng and L.A. Entrena, "Multi-Level Logic Optimization by Redundancy Addition and Removal," in Proc. European Conference On Design Automation, pp. 373-377, Feb. 1993.
• 7: Maurizio Damiani , Jerry Chih-Yuan Yang , Giovanni De Micheli, Optimization of combinational logic circuits based on compatible gates, Proceedings of the 30th international conference on Design automation, p.631-636, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165073]
• 8: 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
• 9: E. Detjens, G. Gannot, R. Rudell, A. L. Sangiovanni-Vincentelli and A. Wang, "Technology Mapping in MIS," Proc. ICCAD, pp. 116-119, 1987.
• 10: T. Kirkland , M. R. Mercer, A topological search algorithm for ATPG, Proceedings of the 24th ACM/IEEE conference on Design automation, p.502-508, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37963]
• 11: C.E.Leiserson, EM.Rose, and J.B.Saxe, "Optimizing synchronous circuit by retiming", in Proc. Third Caltech Conf. on VLSI, 1983.
• 12: 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]
• 13: M.Schulz and E.Auth, "Advanced Automatic Test Pattern Generation and Redundancy Identification Techniques," Proc. Fault Tolerant Computing Symposium, pp. 30-34 June 1988.

INDEX TERMS

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

General Terms:
Experimentation, Measurement, Performance, Theory