Implementation of an efficient parallel BDD package

Abstract

Implementation of an Efficient Parallel BDD Package by Anthony L. Stornetta Large BDD applications are generally limited by a processor's resources, especially physical memory. In large BDD applications, virtual memory is not an attractive solution for conventional depth-first BDD algorithms. Irregular memory access patterns in the algorithm cause thrashing, which severely impairs performance. One solution to overcoming this resource limitation is to utilize the memory of multiple networked workstations. A number of different forms of parallelism can be exploited in depth-first algorithms performed on a distributed BDD. The BDD structure is stored in a distributed hash table and can be accessed simultaneously by multiple processors. An unlimited number of multiple BDD operations may be concurrently issued. In essence, the package can simultaneously execute multiple threads of computation on a distributed BDD. This thesis presents an efficient parallel BDD package for a distributed en...