BDS: a BDD-based logic optimization system

ABSTRACT

This paper describes a new BDD-based logic optimization system, BDS. It is based on a recently developed theory for BDD-based logic decomposition, which supports both algebraic and Boolean factorization. New techniques, which are crucial to the manipulation of BDDs in a partitioned Boolean network environment, are described in detail. The experimental results show that BDS has a capability to handle very large circuits. It offers a superior runtime advantage over SIS, with comparable results in terms of circuit area and often improved delay.

REFERENCES

• 1: Richard Rudell, Design of a logic synthesis system (tutorial), Proceedings of the 33rd annual conference on Design automation, p.191-196, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240554]
• 2: S.B. Akers, "Functional Testing with Binary Decision Diagrams," in Eighth Annual Conference on Fault- Tolerant Computing, 1978, pp. 75-82.
• 3: 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]
• 4: Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
• 5: Yung-Te Lai, Kuo-Rueih Pan, and Massoud Pedram, "OBDD-Based Function Decomposition: Algorithms and Implementattion," IEEE Trans. on CAD, vol. 15, no. 8, pp. 977-990, August 1996.
• 6: Shih-Chieh Chang, M. Marek-Sadowska, and T. Hwang, "Technology Mapping for TLU FPGA's Based on Decomposition of Binary Decision Diagrams," IEEE Trans. on CAD, vol. 15, no. 10, pp. 1226-1235, October 1996.
• 7: Jason Cong , Yuzheng Ding, Beyond the combinatorial limit in depth minimization for LUT-based FPGA designs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.110-114, November 07-11, 1993, Santa Clara, California, United States
• 8: K. Yano, Y. Sasaki, K. Rikino, and K. Seki, "Top-Down Pass Transistor Logic Design," IEEE J. Solid-State Circuits, vol. 31, no. 6, pp. 792~803, June 1996.
• 9: P. Buch, A. Narayan, R. Newton, and A. Sangiovanni-Vincentelli, "On Synthesizing Pass Transistor Logic," in Intl. Workshop on Logic Synthesis, 1997.
• 10: J. L. Burns, Area-Oriented Synthesis for Pass-Transistor Logic, Proceedings of the International Conference on Computer Design, p.160, October 05-05, 1998
• 11: Kevin Karplus, USING IF-THEN-ELSE DAGs FOR MULTI-LEVEL LOGIC MINIMIZATION, University of California at Santa Cruz, Santa Cruz, CA, 1988
• 12: Valeria Bertacco , Maurizio Damiani, The disjunctive decomposition of logic functions, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.78-82, November 09-13, 1997, San Jose, California, United States
• 13: Ted Stanion and Carl Sechen, "Boolean Division and Factorization Using Binary Decision Diagrams," IEEE Trans. on CAD, vol. 13, no. 9, pp. 1179-1184, September 1994.
• 14: S. Minato, "Fast Factorization Method for Implicit Cube Set Representation," IEEE Trans. on CAD, vol. 15, no. 4, pp. 377-384, April 1996.
• 15: M. A. Thornton , V. S. S. Nair, Behavioral synthesis of combinational logic using spectral-based heuristics, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.2, p.219-230, April 1999 [doi>10.1145/307988.308000]
• 16: S. Yamashita, K. Yano, Y. Sasaki, Y. Akita, H Chikata, K. Rikino, and K Seki, "Pass-Transistor/CMOS Collaborated Logic: The Best of Both Worlds," in Symposium on VLSI Circuits Digest of Technical Papers, 1997, pp. 31-32.
• 17: C. Yang and M. Ciesielski, "Synthesis for Mixed CMOS/PTL Logic: Preliminary Results," in International Workshop on Logic Synthesis, 1999.
• 18: BDD Decomposition for Efficient Logic Synthesis, Proceedings of the 1999 IEEE International Conference on Computer Design, p.626, October 10-13, 1999
• 19: E. Sentovich et al., "SIS: A System for Sequential Circuit Synthesis," Tech. Rep. UCB/ERL M92/41, ERL, Dept. of EECS, Univ. of California, Berkeley., 1992.
• 20: http: //www. ecs. umass, edu/ece/labs/vlsicad/ciesielski, html.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Simulation; Optimization
  B.8 Performance and Reliability

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