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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2374682
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo