Selective Minterms Based Tabular Method for BDD Manipulations
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:50654", author = "P. W. C. Prasad and A. Assi and M. Raseen and A. Harb", title = "Selective Minterms Based Tabular Method for BDD Manipulations", 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.", volume = "1", number = "3", pages = "494-4", }
