HermesBDD: A Multi-Core and Multi-Platform Binary Decision Diagram Package
Authors:
- 3 May 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 87-90
Abstract
BDDs are representations of a Boolean expression in the form of a directed acyclic graph. BDDs are widely used in several fields, particularly in model checking and hardware verification. There are several implementations for BDD manipulation, where each package differs depending on the application. This paper presents HermesBDD: a novel multi-core and multi-platform binary decision diagram package focused on high performance and usability. HermesBDD supports a static and dynamic memory management mechanism, the possibility to exploit lock-free hash tables, and a simple parallel implementation of the IF-THEN-ELSE procedure based on a higher-level wrapper for threads and futures. HermesBDD is completely written in C++ with no need to rely on external libraries and is developed according to software engineering principles for reliability and easy maintenance over time. We provide experimental results on the n-Queens problem, the de-facto SAT solver benchmark for BDDs, demonstrating a significant speedup of 18.73× over our non-parallel baselines, and a remarkable performance boost w.r.t. other state-of-the-art BDDs packages.Keywords
All Related Versions
Funding Information
- Ministry of Education
This publication has 11 references indexed in Scilit:
- Adiar Binary Decision Diagrams in External Memory2022
- Effective Problem Solving Using SAT SolversCommunications in Computer and Information Science, 2020
- Sylvan: Multi-Core Decision Diagrams2015
- A Thread-Safe Library for Binary Decision Diagrams2014
- Multi-Core BDD Operations for Symbolic ReachabilityElectronic Notes in Theoretical Computer Science, 2013
- CacBDD: A BDD Package with Dynamic Cache Management2013
- Biddy — a Multi-platform Academic BDD PackageJournal of Software, 2012
- A consumer report on BDD packages2004
- The I/O-complexity of Ordered Binary-Decision Diagram manipulation1995
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986