Computing treewidth on the GPU

Tom C. van der Zanden, Hans L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
10 Downloads (Pure)

Abstract

We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O∗(2n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77×) compared to running the same algorithm on the CPU.

Original languageEnglish
Title of host publication12th International Symposium on Parameterized and Exact Computation, IPEC 2017
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-13
ISBN (Print)978-3-95977-051-4
DOIs
Publication statusPublished - 1 Feb 2018
Event12th International Symposium on Parameterized and Exact Computation (IPEC 2017) - Vienna, Austria
Duration: 6 Sep 20178 Sep 2017
Conference number: 12
https://algo2017.ac.tuwien.ac.at/ipec

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume89

Conference

Conference12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Abbreviated titleIPEC 2017
CountryAustria
CityVienna
Period6/09/178/09/17
Internet address

Fingerprint

Dynamic programming
Parallel algorithms
Program processors
Data storage equipment
Graphics processing unit
Experiments

Keywords

  • Algorithm engineering
  • Exact algorithms
  • GPGPU
  • GPU
  • Graph algorithms
  • Treewidth

Cite this

van der Zanden, T. C., & Bodlaender, H. L. (2018). Computing treewidth on the GPU. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 (pp. 1-13). [29] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 89). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2017.29
van der Zanden, Tom C. ; Bodlaender, Hans L. / Computing treewidth on the GPU. 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. pp. 1-13 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{0911c497ae344ee3b66fe5e6b50f0a60,
title = "Computing treewidth on the GPU",
abstract = "We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O∗(2n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77×) compared to running the same algorithm on the CPU.",
keywords = "Algorithm engineering, Exact algorithms, GPGPU, GPU, Graph algorithms, Treewidth",
author = "{van der Zanden}, {Tom C.} and Bodlaender, {Hans L.}",
year = "2018",
month = "2",
day = "1",
doi = "10.4230/LIPIcs.IPEC.2017.29",
language = "English",
isbn = "978-3-95977-051-4",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "1--13",
booktitle = "12th International Symposium on Parameterized and Exact Computation, IPEC 2017",

}

van der Zanden, TC & Bodlaender, HL 2018, Computing treewidth on the GPU. in 12th International Symposium on Parameterized and Exact Computation, IPEC 2017., 29, Leibniz International Proceedings in Informatics (LIPIcs), vol. 89, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 1-13, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 6/09/17. https://doi.org/10.4230/LIPIcs.IPEC.2017.29

Computing treewidth on the GPU. / van der Zanden, Tom C.; Bodlaender, Hans L.

12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. p. 1-13 29 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 89).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Computing treewidth on the GPU

AU - van der Zanden, Tom C.

AU - Bodlaender, Hans L.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O∗(2n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77×) compared to running the same algorithm on the CPU.

AB - We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O∗(2n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77×) compared to running the same algorithm on the CPU.

KW - Algorithm engineering

KW - Exact algorithms

KW - GPGPU

KW - GPU

KW - Graph algorithms

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85044749982&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2017.29

DO - 10.4230/LIPIcs.IPEC.2017.29

M3 - Conference contribution

AN - SCOPUS:85044749982

SN - 978-3-95977-051-4

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 13

BT - 12th International Symposium on Parameterized and Exact Computation, IPEC 2017

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -

van der Zanden TC, Bodlaender HL. Computing treewidth on the GPU. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. p. 1-13. 29. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.IPEC.2017.29