Abstract
Decision diagrams are fundamental data structures that revolutionized fields such as model checking, automated reasoning and decision processes. As performance gains in the current era mostly come from parallel processing, an ongoing challenge is to develop data structures and algorithms for modern multicore architectures. This chapter describes the parallelization of decision diagram operations as implemented in the parallel decision diagram package Sylvan, which allows sequential algorithms that use decision diagrams to exploit the power of multi-core machines.
| Original language | English |
|---|---|
| Title of host publication | Handbook of Parallel Constraint Reasoning |
| Editors | Youssef Hamadi, Lakhdar Sais |
| Place of Publication | Cham |
| Publisher | Springer |
| Chapter | 13 |
| Pages | 509-545 |
| Number of pages | 37 |
| ISBN (Electronic) | 978-3-319-63516-3 |
| ISBN (Print) | 978-3-319-63515-6 |
| DOIs | |
| Publication status | Published - 2018 |
Keywords
- Parallel algorithms
- Decision diagram
- MDD
- BDD
- MT-BDD
- Work-stealing
- Deque
- Garbage collection
- n/a OA procedure