Fast functional evaluation of candidate OBDD variable orderings
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Symbolic simulation via ordered binary decision diagrams (OBDDs) is becoming more feasible each year. These representations are often very efficient under an appropriate ordering of the variables of the functions represented. Recently, heuristics for ordering variables have been developed, but due to the nature of heuristics, no single heuristic always produces an appropriate ordering. The authors develop and analyze a technique for selecting the best of several candidate orderings. The ordering selection method is fast. Its ranking of an ordering is compared to the actual performance of an ordering during functionals (OBDD) calculations in circuits from the ISCAS85 combinational benchmarks. Compared to any previously published single ordering heuristic, the method allows OBDD calculations using less cumulative memory over all six circuits investigated, and also produces over an order of magnitude improvement for one or more of these circuits, over every single heuristic examined.<>Keywords
This publication has 12 references indexed in Scilit:
- Ordered binary decision diagrams and circuit structurePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Proving circuit correctness using formal comparison between expected and extracted behaviourPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Logic verification using binary decision diagrams in a logic synthesis environmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Evaluation and improvement of Boolean comparison method based on binary decision diagramsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New ideas on symbolic manipulations of finite state machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Finding the optimal variable ordering for binary decision diagramsIEEE Transactions on Computers, 1990
- A Basis for a Mathematical Theory of Computation)Published by Elsevier ,1963
- Representation of Switching Circuits by Binary-Decision ProgramsBell System Technical Journal, 1959
- A symbolic analysis of relay and switching circuitsTransactions of the American Institute of Electrical Engineers, 1938