Accession Number : ADA324567

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

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Chen, Yirng-An ; Yang, Bwolen ; Bryant, Randal E.

PDF Url : ADA324567

Report Date : MAR 1997

Pagination or Media Count : 18

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.

Descriptors :   *ALGORITHMS, *MEMORY DEVICES, *HYBRID SYSTEMS, *SYSTEMS APPROACH, ACCESS, OPERATORS(MATHEMATICS), BOOLEAN ALGEBRA.

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE