A New Empirical Evaluation of Existing Methods for Estimating BDD Sizes

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    Binary Decision Diagrams (BDDs) are very useful structures to represent Boolean function in VLSI synthesis. Time taken to build a BDD and obtaining its size plays a major role in the time of complexity of VLSI synthesis. This time complexity increases drastically as the number of input variables increases. Various models to estimate the size of the BDD, without actually building it already exists. These models claim to support both simplified and un-simplified Boolean functions. The models were developed under the justification that time to estimate will be far less compared to the time taken to actually build the BDD. There are two drawbacks with the existing model. First drawback is that, the current model just follows a random curve fit without any substantial mathematical support. Second drawback is the existing model is based on experimental results which used only less than ten variables.  Since current practical functions may use hundreds of variables, there is no guarantee that the model is accurate enough. Given the two drawbacks, it becomes necessary to test the existing model for more complex circuits with hundreds of variables. In this paper the existing models were tested with standard benchmark circuits. Results were compared with actual BDD sizes of the benchmarks and the estimated sizes from the parameters of the benchmarks. Comparison of the results proved that existing models give poor results for the circuits with more than ten variables and existing models become inapplicable to most of the current practical functions that uses more than hundreds of variables.



  • Keywords

    Binary Decision Diagrams, Modeling, Invalidation.

  • References

      [1] S. B. Akers, "Binary Decision Diagram," IEEE Trans. Computers, Vol. 27,pp. 509-516, 1978.

      [2] R. E. Bryant, "Graph-Based Algorithm for Boolean
      Function Manipulation," IEEE Trans. Computers, Vol.
      35, pp.677-691, 1986.

      [3] S. Minato, “Binary Decision diagrams and Applications for VLSICAD,” Kluwer Academic Publishers, 1996.

      [4] 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, UT84112.

      [5] M. Raseen, P.W.C. Prasad, and A. Assi, “Mathematical Model to Predict the Number of Nodes in an ROBDD,” The 47th IEEE International Midwest Symposium on Circuit and Systems (MWSCAS’ 2004), Vol. 3, pp. 431-434, Hiroshima, Japan, July 2004.

      [6] M. Raseen, Ali Assi, P.W.C. Prasad and A. Harb, “An Efficient Mathematical Estimation of the BDDs Complexity”, The 16th IASTED International Conference on Modelling and Simulation, pp 381-386, Mexico, May 2005.

      [7] M. Raseen, P.W.C. Prasad and A. Assi, "An Efficient Estimation of the ROBDD’s Complexity", Integration - The VLSI journal, Vol. 39, Issue 3, pp.211-228, Elsevier Publications, 2006.

      [8] M. Raseen and K. Thanushkodi, “ROBDD’s Parameter Estimation for Simplified Boolean Functions”, International Journal of Soft Computing, Vol. 3, Issue 6, pp.451-460, Medwell Journals, Nov-Dec 2008.

      [9] M. Raseen and E. Venitha, "Exact Modeling of Binary Decision Diagram Complexity", International Conference on Internet of Things and Challenges, pp. 244-248, Chennai, India, December 2017.

      [10] T.Padmapriya, S.V.Manikanthan, “An enhanced distributed evolved node-b architecture in 5G tele-communications network”, International Journal of Engineering & Technology, DOI: 10.14419/ijet.v7i2.8.10419, ISSN NO:2227-524X, Vol-7, No.2.9(2018)

      [11] S.V.Manikanthan and V.Rama “Optimal Performance Of Key Predistribution Protocol In Wireless Sensor Networks” International Innovative Research Journal of Engineering and Technology, ISSN NO: 2456-1983,Vol-2,Issue –Special –March 2017.

      [12] T. Padmapriya, V.Saminadan, “Performance Improvement in long term Evolution-advanced network using multiple input multiple output technique”, Journal of Advanced Research in Dynamical and Control Systems, Vol. 9, Sp-6, pp: 990-1010, 2017.




Article ID: 12069
DOI: 10.14419/ijet.v7i2.24.12069

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.