Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions
This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters: The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.
[1] R. E. Bryant, "On the complexity of VLSI implementations and graph
representations of Boolean functions with application to integer
multiplication," IEEE Trans. On Computers, vol. 40, pp. 203−213,
1991.
[2] R. E. Bryant, "Graph−Based Algorithm for Boolean Function
Manipulation," IEEE Trans. Computers, vol. 35, pp. 677-691, 1986.
[3] K. Priyank, "VLSI Logic Test, Validation and Verification, Properties
& Applications of Binary Decision Diagrams," Lecture Notes,
Department of Electrical and Computer Engineering University of Utah,
Salt Lake City, UT 84112, 1997.
[4] F. Aloul, I. Markov, K. Sakallah, "MINCE: A Static Global Variable-
Ordering Heuristic for SAT Search and BDD Manipulation," to appear
in Journal of Universal Computer Science (JUCS), 2005.
[5] Justin E. Harlow and Franc Brglez, "Design of Experiments and
evaluation of BDD ordering Heuristics," Inter. Journal on Software
tools for Technology Transfer, vol. 3, pp.193-206, 2001.
[6] S. B. Akers, "Binary Decision Diagram," IEEE Trans. Computers, vol.
27 pp. 509-516, 1978.
[7] M. Fujita, H. Fujisawa, and N. Kawato, "Evaluation and Improvements
of Boolean Comparison Method Based on Binary Decision Diagrams,"
in Proceedings of the International Conference on Computer Aided
Design (ICCAD), 1988, pp. 2-5.
[8] Malik, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Logic
Verification Using Binary Decision Diagrams in a Logic Synthesis
Environment," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1988, pp. 6-9.
[9] S. Panda and F. Somenzi, "Who Are the Variables in Your
Neighborhood," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1995, pp. 74-77.
[10] R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision
Diagrams," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1993, pp. 42-47.
[11] F. Somenzi, "Efficient Manipulation of Decision Diagrams," in
International Journal on Software Tools for Technology Transfer
(STTT), vol. 3, pp.171-181, 2001.
[12] S. J. Friedman and K.J. Supowit, "Finding the Optimal Variable
Ordering for Binary Decision Diagrams," IEEE Trans. On Computers,
vol. 39, pp. 710−713, 1990.
[13] F. Görschwin, R. Drechsler, "Minimizing the Number of paths in BDDs,"
in Proceedings of 15th symposium on Integrated Circuits and Systems
Design, 2002, pp. 359-364.
[14] R. Ebendt, "Reducing the number of variable movements in exact BDD
minimization," in Proceedings of 2003 Int. Symp. on Circuits and
Systems, 2003, pp. 605-608.
[15] R. Ebendt, W. Gűnther and R. Drechsler, "Combination of lower
bounds in exact BDD minimization," in Proceedings of Design
Automation and Test in Europe Conf. and Exhibition, 2003, pp. 758-
763.
[16] R. Drechsler, N. Drechsler and.W.G├╝nther, "Fast Exact Minimization of
BDD-s," IEEE Trans. on CAD of IC and Systems, vol.19, pp. 384−389,
2000.
[17] P. W. C. Prasad and A. K. Singh, "An Efficient Method for
Minimization of Binary Decision Diagrams," in Proceedings of 3rd Int.
Conf. on Advances in Strategic Technologies, 2003, pp. 683-688.
[18] K.S. Brace, R.L. Rudell and R.E. Bryant, "Efficient implementation of a
BDD package," in Proceedings of Design and Automation conf., 1990,
pp. 40-45.
[19] Tani, K. Hamaguchi, and S. Yajima, "The Complexity of the Optimal
Variable Ordering Problems of A Shared Binary Decision Diagram," in
Proceedings of 4th International Symposium on Algorithms and
Computation (ISAAC-93), LNCS 762, 1993.
[20] R. Rudell, "Dynamic Variable ordering for ordered binary decision
diagrams," in Proceedings of IEEE Inter. Conf. on CAD, 1993, pp. 42-
47.
[21] P. Chung, I. N. Haji and J. H. Patel, "Efficient Variable Ordering
Heuristics for Shared ROBDDs," in Proceedings of Int. Sym. on
Circuits and Systems, 1993, pp. 40-45.
[22] Y. Lu, J. Jain, E. Clarke and M. Fujita, "Efficient Variable Ordering
using a BDD Based Sampling," in Proceedings of 37th Design
Automation Conf., 2000, pp. 687-692.
[23] M. G. Karpovsky, R. S. Stankovic, and J. T. Astola, "Reduction of
Sizes of Decision Diagrams by Autocorrelation Functions," IEEE
Transaction on computer, vol. 52, pp. 592-606, 2003.
[24] R. Drechsler and D. Sieling, "Binary Decision Diagrams in Theory and
Practice," Springer-Verlag Trans., pp.112-136, 2001.
[25] P. W. C. Prasad, M. Raseen and A. Assi, "Improved Variables Ordering
for Binary Decision diagram," in Proceedings of Int. Research Conf. on
Innovation in Information Technology, 2004, pp. 329-333.
[26] A. Kuehlmann, F. Krohm, "Equivalence checking using cuts and
heaps," in Proceedings of 34th Design Automation conference
(DAC-97), 1997, pp.263-268.
[27] F. Somenzi, "CUDD: CU Decision Diagram Package,"
ftp://vlsi.colorado.edu/ pub/., 2003.
[28] S. Yang, "Logic synthesis and optimization benchmarks user guide
version 3.0," Technical report, Microelectronic Centre of North
Caroline, Research Triangle Park, NC, January 1991.
[29] M. Hansen, H. Yalcin, and J. P. Hayes, "Unveiling the ISCAS-85
Benchmarks: A Case Study in Reverse Engineering," IEEE Trans. On
Design and Test, vol. 16, pp. 72-80, 1999.
[30] F. Brglez and H. Fujiwara, "A neutral netlist of 10 combinational
circuits and a target translator in Fortran," in Proceedings of Int.
Symposium on Circuit and Systems, Special Sess. On ATPG and Fault
Simulation, 1985, pp. 663-6985.
[1] R. E. Bryant, "On the complexity of VLSI implementations and graph
representations of Boolean functions with application to integer
multiplication," IEEE Trans. On Computers, vol. 40, pp. 203−213,
1991.
[2] R. E. Bryant, "Graph−Based Algorithm for Boolean Function
Manipulation," IEEE Trans. Computers, vol. 35, pp. 677-691, 1986.
[3] K. Priyank, "VLSI Logic Test, Validation and Verification, Properties
& Applications of Binary Decision Diagrams," Lecture Notes,
Department of Electrical and Computer Engineering University of Utah,
Salt Lake City, UT 84112, 1997.
[4] F. Aloul, I. Markov, K. Sakallah, "MINCE: A Static Global Variable-
Ordering Heuristic for SAT Search and BDD Manipulation," to appear
in Journal of Universal Computer Science (JUCS), 2005.
[5] Justin E. Harlow and Franc Brglez, "Design of Experiments and
evaluation of BDD ordering Heuristics," Inter. Journal on Software
tools for Technology Transfer, vol. 3, pp.193-206, 2001.
[6] S. B. Akers, "Binary Decision Diagram," IEEE Trans. Computers, vol.
27 pp. 509-516, 1978.
[7] M. Fujita, H. Fujisawa, and N. Kawato, "Evaluation and Improvements
of Boolean Comparison Method Based on Binary Decision Diagrams,"
in Proceedings of the International Conference on Computer Aided
Design (ICCAD), 1988, pp. 2-5.
[8] Malik, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Logic
Verification Using Binary Decision Diagrams in a Logic Synthesis
Environment," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1988, pp. 6-9.
[9] S. Panda and F. Somenzi, "Who Are the Variables in Your
Neighborhood," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1995, pp. 74-77.
[10] R. Rudell, "Dynamic Variable Ordering for Ordered Binary Decision
Diagrams," in Proceedings of the International Conference on
Computer Aided Design (ICCAD), 1993, pp. 42-47.
[11] F. Somenzi, "Efficient Manipulation of Decision Diagrams," in
International Journal on Software Tools for Technology Transfer
(STTT), vol. 3, pp.171-181, 2001.
[12] S. J. Friedman and K.J. Supowit, "Finding the Optimal Variable
Ordering for Binary Decision Diagrams," IEEE Trans. On Computers,
vol. 39, pp. 710−713, 1990.
[13] F. Görschwin, R. Drechsler, "Minimizing the Number of paths in BDDs,"
in Proceedings of 15th symposium on Integrated Circuits and Systems
Design, 2002, pp. 359-364.
[14] R. Ebendt, "Reducing the number of variable movements in exact BDD
minimization," in Proceedings of 2003 Int. Symp. on Circuits and
Systems, 2003, pp. 605-608.
[15] R. Ebendt, W. Gűnther and R. Drechsler, "Combination of lower
bounds in exact BDD minimization," in Proceedings of Design
Automation and Test in Europe Conf. and Exhibition, 2003, pp. 758-
763.
[16] R. Drechsler, N. Drechsler and.W.G├╝nther, "Fast Exact Minimization of
BDD-s," IEEE Trans. on CAD of IC and Systems, vol.19, pp. 384−389,
2000.
[17] P. W. C. Prasad and A. K. Singh, "An Efficient Method for
Minimization of Binary Decision Diagrams," in Proceedings of 3rd Int.
Conf. on Advances in Strategic Technologies, 2003, pp. 683-688.
[18] K.S. Brace, R.L. Rudell and R.E. Bryant, "Efficient implementation of a
BDD package," in Proceedings of Design and Automation conf., 1990,
pp. 40-45.
[19] Tani, K. Hamaguchi, and S. Yajima, "The Complexity of the Optimal
Variable Ordering Problems of A Shared Binary Decision Diagram," in
Proceedings of 4th International Symposium on Algorithms and
Computation (ISAAC-93), LNCS 762, 1993.
[20] R. Rudell, "Dynamic Variable ordering for ordered binary decision
diagrams," in Proceedings of IEEE Inter. Conf. on CAD, 1993, pp. 42-
47.
[21] P. Chung, I. N. Haji and J. H. Patel, "Efficient Variable Ordering
Heuristics for Shared ROBDDs," in Proceedings of Int. Sym. on
Circuits and Systems, 1993, pp. 40-45.
[22] Y. Lu, J. Jain, E. Clarke and M. Fujita, "Efficient Variable Ordering
using a BDD Based Sampling," in Proceedings of 37th Design
Automation Conf., 2000, pp. 687-692.
[23] M. G. Karpovsky, R. S. Stankovic, and J. T. Astola, "Reduction of
Sizes of Decision Diagrams by Autocorrelation Functions," IEEE
Transaction on computer, vol. 52, pp. 592-606, 2003.
[24] R. Drechsler and D. Sieling, "Binary Decision Diagrams in Theory and
Practice," Springer-Verlag Trans., pp.112-136, 2001.
[25] P. W. C. Prasad, M. Raseen and A. Assi, "Improved Variables Ordering
for Binary Decision diagram," in Proceedings of Int. Research Conf. on
Innovation in Information Technology, 2004, pp. 329-333.
[26] A. Kuehlmann, F. Krohm, "Equivalence checking using cuts and
heaps," in Proceedings of 34th Design Automation conference
(DAC-97), 1997, pp.263-268.
[27] F. Somenzi, "CUDD: CU Decision Diagram Package,"
ftp://vlsi.colorado.edu/ pub/., 2003.
[28] S. Yang, "Logic synthesis and optimization benchmarks user guide
version 3.0," Technical report, Microelectronic Centre of North
Caroline, Research Triangle Park, NC, January 1991.
[29] M. Hansen, H. Yalcin, and J. P. Hayes, "Unveiling the ISCAS-85
Benchmarks: A Case Study in Reverse Engineering," IEEE Trans. On
Design and Test, vol. 16, pp. 72-80, 1999.
[30] F. Brglez and H. Fujiwara, "A neutral netlist of 10 combinational
circuits and a target translator in Fortran," in Proceedings of Int.
Symposium on Circuit and Systems, Special Sess. On ATPG and Fault
Simulation, 1985, pp. 663-6985.
@article{"International Journal of Information, Control and Computer Sciences:55182", author = "P.W. C. Prasad and A. Assi and A. Harb and V.C. Prasad", title = "Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions", abstract = "This paper presents an improved variable ordering method to obtain the minimum number of nodes in Reduced Ordered Binary Decision Diagrams (ROBDD). The proposed method uses the graph topology to find the best variable ordering. Therefore the input Boolean function is converted to a unidirectional graph. Three levels of graph parameters are used to increase the probability of having a good variable ordering. The initial level uses the total number of nodes (NN) in all the paths, the total number of paths (NP) and the maximum number of nodes among all paths (MNNAP). The second and third levels use two extra parameters: The shortest path among two variables (SP) and the sum of shortest path from one variable to all the other variables (SSP). A permutation of the graph parameters is performed at each level for each variable order and the number of nodes is recorded. Experimental results are promising; the proposed method is found to be more effective in finding the variable ordering for the majority of benchmark circuits.
", keywords = "Binary decision diagrams, graph representation, Boolean functions representation, variable ordering.", volume = "2", number = "2", pages = "414-7", }
