Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions

Authors: P.W. C. Prasad, A. Assi, A. Harb, V.C. Prasad

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.

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

References:

[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.