Algorithmic Optimization of BDDs and Performance Evaluation for Multi-level Logic Circuits with Area and Power Trade-offs

Saurabh Chaudhury, Anirban Dutta

.

DOI: 10.4236/cs.2011.23031                

Abstract

Binary Decision Diagrams (BDDs) can be graphically manipulated to reduce the number of nodes and hence the area. In this context, ordering of BDDs play a major role. Most of the algorithms for input variable ordering of OBDD focus primarily on area minimization. However, suitable input variable ordering helps in minimizing the power consumption also. In this particular work, we have proposed two algorithms namely, a genetic algorithm based technique and a branch and bound algorithm to find an optimal input variable order. Of course, the node reordering is taken care of by the standard BDD package buddy-2.4. Moreover, we have evaluated the performances of the proposed algorithms by running an exhaustive search program. Experi-mental results show a substantial saving in area and power. We have also compared our techniques with other state-of-art techniques of variable ordering for OBDDs and found to give superior results.

Keywords

Algorithmic Optimization, BDDs, Genetic Algorithm, Branch & Bound, Variable Ordering, Area-Power Trade-offs

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Malik, A. R. Wang, R. K. Brayton and A. Sangiovarmi-Vincentelli, “Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment,” Proceedings of International Conference on Computer-Aided Design, Santa Clara, 7-10 November 1988, pp. 6-9. doi:10.1109/ICCAD.1988.122451
[2]	M. Fujita, H. Fujisawa and Y. Matsnnaga, “Variable Ordering Algorithms for Ordered Binary Decision Diagrams and Their Evaluation,” IEEE Transactions on Computer-Aided Design, Vol. 12, No. 1, 1993, pp. 6-12. doi:10.1109/43.184839
[3]	M. Fujita, Y. Matsmraga and T. Kakuda, “On Variable Ordering of Binary Decision Diagrams for the Application of Multi-level Logic Synthesis,” Proceedings of European Design Automation Conference, Amsterdam, 25-28 February 1991, pp. 50-54. doi:10.1109/EDAC.1991.206358
[4]	N. Ishiura, H. Sawada and S. Yajima, “Minimization of Binary Decision Diagrams Based on Exchange of Variables,” 1991 IEEE International Conference on Computer-Aided Design, Santa Clara, 11-14 November 1991, pp. 472-475. doi:10.1109/ICCAD.1991.185307
[5]	R. Rudell, “Dynamic Variable Ordering for Ordered Binary Decision Diagrams,” Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, 7-11 November 1993, pp. 42-47. doi:10.1109/ICCAD.1993.580029
[6]	H. Fujii, G. Ootomo and C. Hori, “Interleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams,” Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, 7-11 November 1993, pp. 38-41. doi:10.1109/ICCAD.1993.580028
[7]	C. Meinel and F. Somenzi, “Linear Sifting of Decision Diagrams,” Proceedings of the 34th Annual Automation Conference, Anaheim, 9-13 June 1997, pp. 202-207.
[8]	B. Beate, L. Martin and W. Ingo, “Simulated Annealing to Improve Variable Orderings for OBDDs,” Proceedings of the International Workshop on Logic Synthesis, May 1995, pp. (5-1)-(5-10).
[9]	R. Drechsler and N. G?ckel, “Minimization of BDDs by Evolutionary Algorithms,” International Workshop on Logic Synthesis (IWLS), Lake Tahoe, 1997.
[10]	M. A. Thornton, J. P. Williams, R. Drechsler, N. Drechsler and D. M. Wessels, “SBDD Variable Reordering Based on Probabilistic and Evolutionary Algorithms,” 1999 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, 22-24 August 1999, pp. 381-387. doi:10.1109/PACRIM.1999.799556
[11]	R. Drechsler, B. Becker, N. G?ckel, “Learning Heuristics for OBDD Minimization by Evolutionary Algorithms,” Lecture Notes in Computer Science, Vol. 1141, 1996, pp. 730-739. doi:10.1007/3-540-61723-X_1036
[12]	W. Günther and R. Drechsler, “Improving EAs for Sequencing Problems,” Proceedings of the Genetic and Evolutionary Computation Conference, 2000.
[13]	R. Drechsler, M. Kerttu, P. Lindgren and M. Thornton, “Low Power Optimization Techniques for BDD Mapped Circuits Using Temporal Correlation,” Canadian Journal of ECE, Vol. 27, No. 4, 2002, pp. 159-164.
[14]	S. Chaudhury and S. Chattopadhyay, “Output Phase Assignment for Multilevel Multi-output Logic Synthesis with Area and Power Trade-offs,” 2006 Annual IEEE India Conference, New Delhi, 15-17 September 2006, pp, 1-4.
[15]	W. N. N. Hung, X. Song, E. M. Aboulhamid and M. A. Driscoll, “BDD Minimization by Scatter Search,” IEEE transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, No. 8, 2006, pp. 974-979.
[16]	P. W. C. Prasad, M. Raseen, A. Assi and S. M. N. A. Senanayake, “BDD Path Length Minimization Based on Initial Variable Ordering”, Journal of Computer Science, Vol. 1, No. 4, 2005, pp. 520-528.
[17]	M. Rice and S. Kulhari, “A Survey of Static Variable Ordering Heuristics for Efficient BDD/MDD Construction,” Technical Report, 2008. http://www.cs.ucr.edu/~skulhari/StaticHeuristics.pdf
[18]	P. W. C. Prasad, A. Assi, A. Harb and V. C. Prasad, “Binary Decision Diagrams: An Improved Variable Ordering using Graph Representation of Boolean Functions,” International Journal of Computer Science, Vol. 1, No. 1, 2006, pp. 1-7.
[19]	O. Brudaru, R. Ebendt and I. Furdu, “Optimizing Variable Ordering of BDDs with Double Hybridized Embryonic Genetic Algorithm,” Proceedings of 12th IEEE International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, 23-26 September 2010, pp. 167-173.
[20]	R. Ebendt, F. Gorschwin and R. Drechsler, “Advanced BDD Minimization”, Springer, New York, 2005.