Technical Report No. 144 - Abstract

Wolfgang Guenther
Speeding up Dynamic Minimization of Linearly Transformed BDDs

Binary Decision Diagrams (BDDs) are frequently used in many applications in VLSI CAD. However, they are very sensitive to the variable ordering and their size often becomes infeasible. To reduce the BDD sizes, Linear Transformations (LTs), a special type of spectral techniques, have been successfully applied in many cases. The most commonly used heuristic to find a good LT, i.e. an LT which leads to a small BDD representation, is called linear sifting. It can be seen as an extension of the widely used dynamic BDD minimization algorithm called sifting by a linear operator. In this paper, we prove lower bounds for Linearly Transformed BDDs (LTBDDs) under certain conditions and show that it is possible to speed up linear sifting significantly using these bounds. Experimental results are given to show the efficiency of our approach.