Breadth-First with Depth-First BDD Construction: A Hybrid Approach

	      Yirng-An Chen, Bwolen Yang, and Randal E. Bryant


Abstract:

This paper presents the technique of operator sifting as a new way of
understanding both breadth-first and depth-first approaches to BDD
construction.  A new algorithm is also proposed to capture the
breadth-first approach's advantage of memory access locality, while
keeping the depth-first approach's advantage of low memory overhead.
Our preliminary experimental results show that our approach is generally
faster than other implementations that rely exclusively on either
breadth-first or depth-first approaches while keeping memory overhead
comparable to that of depth-first approaches.





@techreport{chen-hybrid97,
    key="Chen",
    author="Yirng-An Chen and Bwolen Yang and Randal E. Bryant",
    Title="Breadth-First with Depth-First {BDD} Construction: A Hybrid Approach",
    institution	= "{School of Computer Science, Carnegie Mellon University}",
    number	= "CMU-CS-97-120",
    month       = March,
    year	= "1997"
}