Multi-valued decision diagrams (MDDs) are a generalization ofbinary decision diagrams (BDDs). They are suitable for severalapplications in synthesis and verification of integrated circuits sinceoften, functions with multi-valued input variables can be representedefficiently by MDDs. Their sizes counted in number of nodes vary fromlinear to exponential dependent on the variable ordering used. Thereforesifting, i.e. dynamic variable re-ordering, has to be applied frequentlywhile an MDD is built in order to keep the number of nodes needed duringthe process small. Often most of the runtime for MDD construction isspent for sifting. We present a new method that speeds up MDDconstruction and also reduces memory consumption. It is based on theselection of re-ordering heuristics dependent on the history of theconstruction process. Success of previous re-ordering steps as well asthe frequency of sifting calls in the past are used to determine avariation of sifting that is applied next. Experimental results aregiven to demonstrate that runtimes and memory consumption can be reducedby 30% on average when the proposed selection methods are used duringMDD construction
展开▼
