Binary Decision Diagrams (BDDs) provide very efficient representations of Boolean functions and have been widely used in various computer-aided design of VLSI systems. As the construction time of BDDs varies with applications and is often large in some complex circuits, it would be useful to design parallel algorithms to construct BDDs. In this paper, we propose two parallel algorithms for constructing the BDDs of logic circuits. We first present a shared memory parallel algorithm using locks. To achieve more parallelism, we present another algorithm using replication of fanin cones that is suitable for execution on distributed memory multicomputers. We have implemented our parallel algorithms on two shared memory multiprocessors and one distributed memory multicomputer. Experimental results showing speedups for some ISCAS benchmark circuits are reported on an 8 processor IBM J-40 shared memory multiprocessor, an 8 processor SGI Origin shared memory multiprocessor, and a 16 processor IBM SP-2 distributed memory multicomputer.

Gzipped Postscript version of the paper