Other Institutes / Centres / Divisions / Services

Permanent URI for this community

Now showing 1 - 1 of 1

Distributed binary decision diagrams
(Stellenbosch : University of Stellenbosch, 2010-12) Fasan, Mary Oluwasola; Geldenhuys, Jaco; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Computer Sciience.
ENGLISH ABSTRACT: Binary Decision Diagrams (BDDs) 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 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 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. In this thesis, an algorithm for manipulating BDDs on a NOW is presented. 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. The design and implementation details of the distributed BDD package are described. The various approaches considered in order to optimize the performance of the algorithm are also discussed. Experimental results demonstrating the performance and capabilities of the distributed package and the benefits of the different optimization approaches are given.