Selective Minterms Based Tabular Method for BDD Manipulations

Authors: P. W. C. Prasad, A. Assi, M. Raseen, A. Harb

Abstract:

The goal of this work is to describe a new algorithm for finding the optimal variable order, number of nodes for any order and other ROBDD parameters, based on a tabular method. The tabular method makes use of a pre-built backend database table that stores the ROBDD size for selected combinations of min-terms. The user uses the backend table and the proposed algorithm to find the necessary ROBDD parameters, such as best variable order, number of nodes etc. Experimental results on benchmarks are given for this technique.

Keywords: Tabular Method, Binary Decision Diagram, BDD Manipulation, Boolean Function.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1055337

References:

[1] K. Priyank, "VLSI Logic Test, Validation and Verification, Properties & Applications of Binary Decision Diagrams," Department of Electrical and Computer Engineering University of Utah, Salt Lake City, UT 84112.
[2] R. E. Bryant, "On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication," IEEE Trans. Computers, Vol. 40, pp. 203¶ÇÇÉ213, 1991.
[3] R. E. Bryant, "Graph¶ÇÇÉBased Algorithm for Boolean Function Manipulation," IEEE Trans. Computers, Vol. 35, pp. 677-691, 1986.
[4] S. Malik, A. Wang, R. Brayton, A. Sangiovanni,, "Logic Verification using Binary Decision Diagrams in Logic Synthesis Environment". International Conference on Computer Aided Design, 1988.
[5] K.M. Butler, D.E. Ross, R. Kapur. and M. R. Mercer, "Heuristics to Compute Variable Ordering for Efficient Manipulations of Ordered Binary Decision Diagrams", DAC-90, pp. 52-57, 1990.
[6] P.W.C. Prasad and A. K. Singh, "Representation of Boolean Function using Partial Binary Decision Diagram," contribution talk, 5th International Congress on Industrial and Applied Mathematics, Australia, 2003.
[7] P.W.C. Prasad, A. Assi, and M. Raseen, "BDD Minimization Using Graph Parameter Permutation", The 2004 International Conference on VLSI, 2004, pp. 491-494.
[8] P.W.C. Prasad, and A. K. Singh, "An Efficient Method for Minimization of Binary Decision Diagrams," 3rd International Conference on Advances in Strategic Technologies (ICAST), pp. 683-688, 2003..
[9] C. Yang and, M. Ciesielski, "BDS: A BDD¶ÇÇÉBased Logic Optimization System," IEEE Trans. On CAD of IC and Systems, Vol.21, pp. 866¶ÇÇÉ876, 2002.
[10] S. B. Akers, "Binary Decision Diagram," IEEE Trans. Computers, Vol. 27, pp. 509-516, 1978.
[11] K. Brace, "Efficient implementation of a BDD package," in Proceedings of Design and Automation conference, pp 40-45, 1993.