Multi-core Decision Diagrams

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

45 Downloads (Pure)

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 languageEnglish
Title of host publicationHandbook of Parallel Constraint Reasoning
EditorsYoussef Hamadi, Lakhdar Sais
Place of PublicationCham
PublisherSpringer
Chapter13
Pages509-545
Number of pages37
ISBN (Electronic)978-3-319-63516-3
ISBN (Print)978-3-319-63515-6
DOIs
Publication statusPublished - 2018

Fingerprint

Decision Diagrams
Data structures
Model checking
Algorithms and Data Structures
Automated Reasoning
Sequential Algorithm
Processing
Parallel Processing
Parallelization
Model Checking
Data Structures

Keywords

  • Parallel algorithms
  • Decision diagram
  • MDD
  • BDD
  • MT-BDD
  • Work-stealing
  • deque
  • garbage collection

Cite this

van Dijk, T., & van de Pol, J. (2018). Multi-core Decision Diagrams. In Y. Hamadi, & L. Sais (Eds.), Handbook of Parallel Constraint Reasoning (pp. 509-545). Cham: Springer. https://doi.org/10.1007/978-3-319-63516-3_13
van Dijk, Tom ; van de Pol, Jaco. / Multi-core Decision Diagrams. Handbook of Parallel Constraint Reasoning. editor / Youssef Hamadi ; Lakhdar Sais. Cham : Springer, 2018. pp. 509-545
@inbook{6a38b45ea0da4c988305818b52737c45,
title = "Multi-core Decision Diagrams",
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.",
keywords = "Parallel algorithms, Decision diagram, MDD, BDD, MT-BDD, Work-stealing, deque, garbage collection",
author = "{van Dijk}, Tom and {van de Pol}, Jaco",
year = "2018",
doi = "10.1007/978-3-319-63516-3_13",
language = "English",
isbn = "978-3-319-63515-6",
pages = "509--545",
editor = "Youssef Hamadi and Lakhdar Sais",
booktitle = "Handbook of Parallel Constraint Reasoning",
publisher = "Springer",

}

van Dijk, T & van de Pol, J 2018, Multi-core Decision Diagrams. in Y Hamadi & L Sais (eds), Handbook of Parallel Constraint Reasoning. Springer, Cham, pp. 509-545. https://doi.org/10.1007/978-3-319-63516-3_13

Multi-core Decision Diagrams. / van Dijk, Tom; van de Pol, Jaco.

Handbook of Parallel Constraint Reasoning. ed. / Youssef Hamadi; Lakhdar Sais. Cham : Springer, 2018. p. 509-545.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - Multi-core Decision Diagrams

AU - van Dijk, Tom

AU - van de Pol, Jaco

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Parallel algorithms

KW - Decision diagram

KW - MDD

KW - BDD

KW - MT-BDD

KW - Work-stealing

KW - deque

KW - garbage collection

U2 - 10.1007/978-3-319-63516-3_13

DO - 10.1007/978-3-319-63516-3_13

M3 - Chapter

SN - 978-3-319-63515-6

SP - 509

EP - 545

BT - Handbook of Parallel Constraint Reasoning

A2 - Hamadi, Youssef

A2 - Sais, Lakhdar

PB - Springer

CY - Cham

ER -

van Dijk T, van de Pol J. Multi-core Decision Diagrams. In Hamadi Y, Sais L, editors, Handbook of Parallel Constraint Reasoning. Cham: Springer. 2018. p. 509-545 https://doi.org/10.1007/978-3-319-63516-3_13