Algorithmic Optimization of BDDs and Performance Evaluation for Multi-level Logic Circuits with Area and Power Trade-offs
- 1
- 2
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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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.
- 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).
- R. Drechsler and N. G?ckel, “Minimization of BDDs by Evolutionary Algorithms,” International Workshop on Logic Synthesis (IWLS), Lake Tahoe, 1997.
- 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
- 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