BDD-based two variable sharing extraction

ABSTRACT

It has been shown that Binary Decision Diagram (BDD) based logic synthesis enjoys faster runtime than the classic logic synthesis systems based on Sum of Product (SOP) form. However, its synthesis quality has not been on par with the classic method due to the lack of an effective sharing extraction strategy. In this paper, we present the first sharing extraction algorithm that directly exploits the structural properties of BDD. While our sharing extraction algorithm is limited to two-variable, disjunctive factors, and therefore may miss sharing opportunities, we show that it can be made exact, incremental and polynomial.

REFERENCES

• 1: R. Brayton and C. McMullen. The decomposition and factorization of boolean expressions. In ISCAS Proceedings, pages 49--54, 1982.
• 2: Alan Mishchenko , Bernd Steinbach , Marek Perkowski, An algorithm for bi-decomposition of logic functions, Proceedings of the 38th conference on Design automation, p.103-108, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378353]
• 3: H. Sawada, S. Yamashita, and A. Nagoya. An efficient method for generating kernels on implicit cube set representations. In International Workshop on Logic Synthesis, 1999.
• 4: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanaha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli. SIS: A system for sequential circuits synthesis. Technical Report UCB/ERL M92/41, Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720, 1992.
• 5: Congguang Yang , Maciej Ciesielski , Vigyan Singhal, BDS: a BDD-based logic optimization system, Proceedings of the 37th conference on Design automation, p.92-97, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337323]
• 6: S. Yang. Logic synthesis and optimization benchmarks user guide version 3.0. Technical report, Microelectronics Center of North Carolina, P. O. Box 12889, Research Triangle Park, NC 27709, 1991.