Distributed binary decision diagrams

[摘要] ENGLISH ABSTRACT: Binary Decision Diagrams (BDDs) are data structures that have been used to solve variousproblems in different aspects of computer aided design and formal verification. The largememory and time requirements of BDD applications are the major constraints that usuallyprevent the use of BDDs since there is a limited amount of memory available on a machine.One way of overcoming this resource limitation problem is to utilize the memory availableon a network of workstations (NOW). This requires the distribution of the computation andmemory requirements involved in the manipulation of BDDs over a NOW.In this thesis, an algorithm for manipulating BDDs on a NOW is presented. The algorithmmakes use of the breadth-first technique to manipulate BDDs so that various BDD operationscan be started concurrently on the different workstations on the NOW. The design and implementationdetails of the distributed BDD package are described. The various approachesconsidered in order to optimize the performance of the algorithm are also discussed. Experimentalresults demonstrating the performance and capabilities of the distributed package andthe benefits of the different optimization approaches are given.

[发布机构] Stellenbosch University