UWEE Tech Report Series

Exact and Heuristic Minimization of Determinant Decision Diagrams


UWEETR-2002-0001

Author(s):
Alicia Manthe, C.-J. Richard Shi

Keywords:
Decision diagrams, data structures, VLSI-CAD, symbolic circuit analysis, logic minimizaiton, computer algebra

Abstract

Determinant Decision Diagram (DDD) is a variant of binary decision diagrams (BDDs) for representing symbolic matrix determinants and cofactors in symbolic circuit analysis. DDD-based symbolic analysis algorithms have time and space complexities proportional to the number of DDD vertices. Inspired by the ideas of Rudell, Drechsler, et. al. on BDD minimization, we present lower-bound based exact and heuristic algorithms for reordering the DDD vertices to minimize the DDD size. Our new contributions are two-folds. First, we show how vertex signs, which are specific to DDDs, can be handled during neighboring vertex reordering. Second, we develop lower bounds tailored to the DDD structures, which are much tighter than the known lower bounds for BDDs. On a set of DDD examples from symbolic circuit analysis, experimental results have demonstrated that the proposed lower-bound based reordering algorithms can effectively reduce DDD sizes. It has also been demonstrated that sifting with lower bounds uses about 55% less computation compared to sifting without using lower bounds, and sifting with the new lower bounds reduces the computation further by up to 10% compared to sifting with known lower bounds for BDDs.

Download the PDF version

Download the Gzipped Postscript version