Resynthesis of multi-level circuits under tight constraints using symbolic optimization

ABSTRACT

We apply recently introduced constructive multi-level synthesis in the resynthesis loop targeting convergence of industrial designs. The incremental ability of the resynthesis approach allows more predictable circuit implementations while allowing their aggressive optimization. The approach is based on a very general symbolic decomposition template for logic synthesis that uses information-theoretical properties of a function to infer its decomposition patterns (rather than more conventional measures such as literal counts). Using this template the decomposition is done in a Boolean domain unrestricted by the representation of a function, enabling superior implementation choices driven by additional technological constraints. The symbolic optimization is applied in resynthesis of industrial circuits which have tight timing constraints yielding their much improved timing properties.

REFERENCES

• 1: R. L. Ashenhurst. The decomposition of switching functions. Ann. Computation Lab., Harvard University, vol. 29, pages 74--116, 1959.
• 2: L. Benini, P. Vuillod, and G. De Micheli. Iterative re-mapping for logic circuits. IEEE TCAD IC, CAD-17(10):948--964, October 1998.
• 3: R. K. Brayton and F. Somenzi. Boolean relations and the incomplete specification of logic networks. In VLSI'89, August 1989.
• 4: R. K. Brayton, J. D. Cohen et al. Fast Recursive boolean function manipulation. In Proc. IEEE Int. Symp. Circ. and Syst., pages 58--62, May 1982
• 5: R. K. Brayton and C. McMullen. The decomposition and factorization of Boolean expressions. In Proc. IEEE Int. Symp. Circ. and Syst., pages 29--54, May 1982.
• 6: F. M. Brown. Boolean Reasoning. Kluwer Academic Publishers, Boston, 1990.
• 7: 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]
• 8: E. Cerny. An approach to unified methodology of combinational switching circuits. IEEE TC, 27(8), 1977.
• 9: H. A. Curtis. New Approach to the Design of Switching Circuits. Van Nostrand, Princeton, NJ, 1962.
• 10: John A. Darringer , Daniel Brand , John V. Gerbi , William H. Joyner, Jr. , Louise Trevillyan, LSS: a system for production logic synthesis, IBM Journal of Research and Development, v.28 n.5, p.537-545, September 1984
• 11: Victor N. Kravets , Karem A. Sakallah, M32: a constructive multilevel logic synthesis system, Proceedings of the 35th annual conference on Design automation, p.336-341, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277140]
• 12: Victor N. Kravets , Karem A. Sakallah, Constructive library-aware synthesis using symmetries, Proceedings of the conference on Design, automation and test in Europe, p.208-215, March 27-30, 2000, Paris, France [doi>10.1145/343647.343734]
• 13: 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
• 14: Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, BDD based decomposition of logic functions with application to FPGA synthesis, Proceedings of the 30th international conference on Design automation, p.642-647, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165078]
• 15: Eric Lehman , Yosinori Watanabe , Joel Grodstein , Heather Harkness, Logic decomposition during technology mapping, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.264-271, November 05-09, 1995, San Jose, California, United States
• 16: Rajeev Murgai , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Optimum functional decomposition using encoding, Proceedings of the 31st annual conference on Design automation, p.408-414, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196440]
• 17: J. P. Roth and R. Karp. Minimization over boolean graphs. IBM J. Res. and Develop., 6(2):227--238, April 1962.
• 18: Hamid Savoj, Don't cares in multi-level network optimization, University of California at Berkeley, Berkeley, CA, 1992
• 19: Hiroshi Sawada , Takayuki Suyama , Akira Nagoya, Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.353-358, November 05-09, 1995, San Jose, California, United States
• 20: C. Scholl, Multi-output functional decomposition with exploitation of don't cares, Proceedings of the conference on Design, automation and test in Europe, p.743-748, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 21: C. Scholl, D. Moller, P. Molitor, and R. Drechsler. BDD minimization using symmetries. IEEE TCAD IC, 18(2):81--100, February 1999.
• 22: E. M. Sentovich. SIS: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41, UC Berkeley, May 1992.
• 23: Subarnarekha Sinha , Robert K. Brayton, Implementation and use of SPFDs in optimizing Boolean networks, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.103-110, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288584]
• 24: F. Somenzi. CUDD: CU Decision Diagram Package. University of Colorado, Boulder, 2.1.2 edition, April 1997.
• 25: H. J. Touati, H. Savoj, and R. K. Brayton. Delay optimization of combinational logic circuits and partial collapsing. In Proc. 28th DAC, pages 188--191, June 1991.
• 26: Bernd Wurth , Klaus Eckl , Kurt Antreich, Functional multiple-output decomposition: theory and an implicit algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.54-59, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217506]
• 27: S. Yang. Logic synthesis and optimization benchmarks user guide -- ver. 3.0. MCNC, Res. Triangle Park, NC, Jan. 1991.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology; Modeling of computer architecture

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Languages

General Terms:
Standardization, Theory