Boolean Function Manipulation on a Parallel System using BDDs

This paper describes a distributed algorithm for Boolean function manipulation. The algorithm is based on Binary Decision Diagrams (BDDs), which are one of the most commonly used data structures for representing and manipulating Boolean functions. A new distributed version of a BDD data structure and a distributed implementation of the basic operator for its manipulation are presented. The algorithm is suitable to work on a MIMD architecture and is based on a message passing master-slave paradigm. A package has been written, which uses the PVM library and is portable on different architectures. Two applications have been developed using the parallel BDD package. In both cases the results show that the new distributed version of the algorithm is able to manage BDDs much larger than the ones managed by mono-processor tools.