Implicit enumeration of structural changes in circuit optimization

ABSTRACT

We describe an implicit technique for enumerating structural choices in circuit optimization. The restructuring technique relies on the symbolic statements of functional decomposition which explores behavioral equivalence of circuit signals through rewiring and resubstitution. Using rigid, yet practical, formulation a rich variety of restructuring candidates is computed symbolically and applied incrementally to produce circuit changes with predictable structural effects. The restructuring technique is used to obtain much improved delays of the already optimized circuits along with their area savings. It is also applied to analyze benefits of optimizing circuit topology at the early steps of synthesis targeting its routability.

REFERENCES

• 1: L. Benini, P. Vuillod, and G. De Micheli. Iterative re-mapping for logic circuits. IEEE TCAD IC, CAD-17(10):948--964, October 1998.
• 2: Daniel Brand, Verification of large synthesized designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.534-537, November 07-11, 1993, Santa Clara, California, United States
• 3: R. K. Brayton and C. McMullen. The decomposition and fac-torization of Boolean expressions. In Proc. IEEE Int. Symp. Circ. and Syst., pages 29--54, May 1982.
• 4: R. K. Brayton, G. Hachtel, and A. Sangiovanni-Vincentelli. Multi-level logic synthesis. in Proc IEEE, vol. 78, no. 2, pages 264--300, February 1990.
• 5: F. M. Brown. Boolean Reasoning. Kluwer Academic Publishers, Boston, 1990.
• 6: 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]
• 7: Yiu-Hing Chan , Prabhakar Kudva , Lisa Lacey , Greg Northrop , Thomas Rosser, Physical synthesis methodology for high performance microprocessors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776009]
• 8: S.-C. Chang, M. Marek-Sadowska, and K.-T. Cheng, Perturb and Simplify: Multi-level Boolean Network Optimizer. IEEE TCAD IC, CAD-15(12):1494--1504, December 1996.
• 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: H. T. Heineken , J. Khare , W. Maly , P. K. Nag , C. Ouyang , W. A. Pleskacz, CAD at the design-manufacturing interface, Proceedings of the 34th annual conference on Design automation, p.321-326, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266123]
• 11: Victor Nikolayevich Kravets , Karem A. Sakallah, Constructive multi-level synthesis by way of functional properties, 2001
• 12: Victor N. Kravets , Karem A. Sakallah, Resynthesis of multi-level circuits under tight constraints using symbolic optimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.687-693, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774673]
• 13: Prabhakar Kudva , Andrew Sullivan , William Dougherty, Metrics for structural logic synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.551-556, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774653]
• 14: W. Kunz, D. Stoffel and P. Menon. Logic Optimization and Equivalence Checking by Implication Analysis. IEEE TCAD IC, CAD-16(3):266--281, March 1997.
• 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: Alan Mishchenko , Xinning Wang , Timothy Kam, A new enhanced constructive decomposition and mapping algorithm, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775871]
• 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: E. M. Sentovich et al. SIS: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41, UC Berkeley, May 1992.
• 20: 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]
• 21: 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.

INDEX TERMS

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

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

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
decomposition, optimization, physical synthesis, re-synthesis, technology mapping