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.

Boolean function manipulation on a parallel system using BDDs / F., Bianchi; Corno, Fulvio; Rebaudengo, Maurizio; SONZA REORDA, Matteo; R., Ansaloni. - 1225:(1997), pp. 916-928. (Intervento presentato al convegno High-Performance Computing and Networking International Conference and Exhibition tenutosi a Vienna (AUT) nel April 28–30, 1997) [10.1007/BFb0031663].

Boolean function manipulation on a parallel system using BDDs

CORNO, Fulvio;REBAUDENGO, Maurizio;SONZA REORDA, Matteo;
1997

Abstract

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.
1997
3540628983
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2374682
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo