Breadth-First with Depth-First BDD Construction: A Hybrid Approach,
Yirng-An Chen, Bwolen Yang, Randal E. Bryant · 1997
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. Yirng-An Chen and Randal E. Bryant are sponsored by the Wright Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330. Bwolen Yang is supported in part by the Advanced Research Projects Agency and Rome Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-96-1-0287, in part by the ...