Binary Decision Diagrams (BDD) are data structures that have been used to solve various problems in different aspects of computer aided design and formal verification. The large memory and time requirements of BDD applications are the major constraints that usually prevent the use of BDDs.
One way of overcoming this resource limitation problem is to utilize the memory available on a network of workstations (NOW). This requires the distribution of the computation and memory requirements involved in the manipulation of BDDs over a NOW.
We present an algorithm for manipulating BDDs on a NOW. The algorithm makes use of the Breadth-first technique to manipulate BDDs so that various BDD operations can be started concurrently on the different workstations on the NOW. We describe the design and implementation of our distributed BDD package and the various approaches considered in order to optimize the performance of the algorithm. Experimental results demonstrating the performance and capabilities of the distributed package and the benefits of the different optimization approaches considered are given.
Mary Fasan is a MSc student at Computer Science, Stellenbosch University.