Accession Number:

ADA324567

Title:

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

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Report Date:

1997-03-01

Pagination or Media Count:

18.0

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 approachs advantage of memory access locality, while keeping the depth-first approachs 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.

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE