Abstract
Reduced ordered binary decision diagrams (ROBDDs) have become widely used for CAD applications such as logic synthesis, formal verification, and etc. The size of RDBDDs for a Boolean function is very sensitive to the ordering choices of input variables and the problem of finding a minimum-size variable ordering is known to be NP-complete. In this paper, we propose a new ROBDD minimization algorithm based on the microcanonical optimization (MO). MO iteratively applies an initialization phase and a sampling phase to combinatorial optimization problems. In the proposed MO-based algorithm, the initialization phase is replaced with the existing Sifting algorithm known to be a very fast local search algorithm to find a minimum-size ROBDD. We derived equations for the proposed MO-based algorithm parameters empirically. The algorithm has been experimented on well known benchmark circuits and the experiments show that, even with slightly better solutions, the run time of the algorithm is 24% and 48% of the Genetic and SA algorithms’, respectively, on average. The proposed MO-based algorithm is a good candidate for the large size problems that cannot be attacked by exact algorithms when a near-optimal solution is required.
This work was supported by Hankuk University of Foreign Studies Research Fund 0f 2006.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Scholl, Christoph, Drechsler, Rolf, Becker, Bernd.: Functional Simulation using Binary Decision Diagrams. In: ACM/IEEE International Conference on Computer Aided Design (ICCAD’97), pp. 8–12 (1997)
Yang, C., Ciesielski, M.: BDS: A BDD-based logic optimization system. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 21(7), 866–876 (2002)
Bryant, R.E.: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transaction on Computers C-35, 667–691 (1986)
Bollig, B., Wegener, I.: Improving the variable ordering of OBDDs in NP-complete. IEEE Trans. Comput. 45(9), 993–1002 (1996)
Fujii, H., Otomo, G., Hori, G.: Interleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams. In: ICCAD 1993, pp. 622–627 (1993)
Rudell, R.: Dynamic Variable Ordering of Ordered Binary Decision Diagrams. In: ICCAD 1993, pp. 42–47 (1993)
Moller, D., Molitor, P., Orechsler, R.: Symmetry based variable ordering for OBDDs. In: IFIP Workshop on Logic and Architecture Synthesis (1994)
Panda, S., Somenzi, F.: Who are the variables in your neighborhood. In: ICCAD 1995, pp. 74–77 (1995)
Fredman, S.J., Supowit, K.J.: Finding the Optimal Variable Ordering for Binary Decision Diagrams. IEEE Transaction on Computers C-39(5), 710–713 (1990)
Ebendt, R., Gunther, W., Drechsler, R.: An improved branch and bound algorithm for exact BDD minimization. IEEE Trans. on CAD Integr. Circuit Syst. 22(12), 1657–1663 (2003)
Ebendt, R., Gunther, W., Drechsler, R.: Combining Ordered Best-First Search With Branch and Bound for exact BDD minimization. IEEE Trans. on CAD Integr. Circuit Syst. 24(10), 1515–1529 (2005)
Bollig, B.M., Lobbing, M., Wegener, I.: Simulated Annealing to improve variable orderings for OBDDs. In: International Workshop on Logic Synthesis vol. 5B, pp. 5.1–5.10 (1995)
Drechsler, Rolf, Beckern, Bernd, Gockel, Nicole.: A Genetic Algorithm for Variable Ordering of OBDDs. In: International Workshop on Logic Synthesis, vol. 5C, pp. 5.55–5.64 (1995)
Linhares, A., Yanasse, H.H., Torreao, J.R.A.: Linear Gate Assignment: A Fast Statistical Mechanics Approach. IEEE Transaction on Computer-Aided Design of Integrated circuits and system 18(12) (1999)
Linhares, A., Torreao, J.A.: Microcanonical optimization applied to the traveling salesman problem. Int. J. Modern Phys. C 9, 133–146 (1998)
Creutz, M.: Microcanonical Monte Carlo simulation. Phys. Rev. Lett. 50, 1411–1413 (1983)
Somenzi, F.C.: Decision Diagram Package Release 2.3.1. University of Colorado (2002)
Yang, S.: Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. Distributed as part of the IWLS91 benchmark distribution (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Cho, SY., Lee, M., Chung, Y. (2007). A Microcanonical Optimization Algorithm for BDD Minimization Problem. In: Okuno, H.G., Ali, M. (eds) New Trends in Applied Artificial Intelligence. IEA/AIE 2007. Lecture Notes in Computer Science(), vol 4570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73325-6_99
Download citation
DOI: https://doi.org/10.1007/978-3-540-73325-6_99
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73322-5
Online ISBN: 978-3-540-73325-6
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
