We describe the motivations, technical problems and solutions behind the implementation of BeeDeeDee, a new thread-safe Java library for Binary Decision Diagrams (BDDs) manipulation. BeeDeeDee allows clients to share a single factory of BDDs, in real parallelism, and reduce the memory footprint of their overall execution, at a very low synchronization cost. We prove through experiments on multi-core computers that BeeDeeDee is an effective thread-safe library for BDD manipulation. As test cases, we consider multiple instances of the n-queens problem, the construction of circuits and the parallel execution of information flow static analyses of Java programs, for distinct properties of variables. For sequential-only executions, BeeDeeDee is faster than other non-thread-safe Java libraries and as fast as non-thread-safe C libraries.

A Thread-Safe Library for Binary Decision Diagrams

LOVATO, Alberto;MACEDONIO, Damiano;SPOTO, Nicola Fausto
2014-01-01

Abstract

We describe the motivations, technical problems and solutions behind the implementation of BeeDeeDee, a new thread-safe Java library for Binary Decision Diagrams (BDDs) manipulation. BeeDeeDee allows clients to share a single factory of BDDs, in real parallelism, and reduce the memory footprint of their overall execution, at a very low synchronization cost. We prove through experiments on multi-core computers that BeeDeeDee is an effective thread-safe library for BDD manipulation. As test cases, we consider multiple instances of the n-queens problem, the construction of circuits and the parallel execution of information flow static analyses of Java programs, for distinct properties of variables. For sequential-only executions, BeeDeeDee is faster than other non-thread-safe Java libraries and as fast as non-thread-safe C libraries.
2014
978-3-319-10430-0
Boolean functions, binary decision diagrams, Java multithreading, threads
File in questo prodotto:
File Dimensione Formato  
Thread-SafeLibraryForBDD.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Licenza: Accesso ristretto
Dimensione 295.01 kB
Formato Adobe PDF
295.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11562/937437
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? ND
social impact