Computing Treewidth on the GPU

T.C. van der Zanden; H.L. Bodlaender

doi:10.4230/LIPIcs.IPEC.2017.29

Computing Treewidth on the GPU

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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^*(2^n)-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 language	English
Title of host publication	Proceedings of the 12th International Symposium on Parameterisiert and Exact Computation (IPEC 2017)
Publisher	Dagstuhl Publishing
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2017.29
Publication status	Published - 2017

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Keywords

Distributed
Parallel
Cluster Computing

Access to Document

10.4230/LIPIcs.IPEC.2017.29Licence: CC BY

LIPIcs.IPEC.2017.29Final published version, 492 KBLicence: CC BY

Cite this

@inproceedings{9090cb65402045499f2ef98c1389f139,

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^*(2^n)-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 = "Distributed, Parallel, Cluster Computing",

author = "{van der Zanden}, T.C. and H.L. Bodlaender",

year = "2017",

doi = "10.4230/LIPIcs.IPEC.2017.29",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Dagstuhl Publishing",

booktitle = "Proceedings of the 12th International Symposium on Parameterisiert and Exact Computation (IPEC 2017)",

}

Computing Treewidth on the GPU. / van der Zanden, T.C.; Bodlaender, H.L.
Proceedings of the 12th International Symposium on Parameterisiert and Exact Computation (IPEC 2017). Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Computing Treewidth on the GPU

AU - van der Zanden, T.C.

AU - Bodlaender, H.L.

PY - 2017

Y1 - 2017

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^*(2^n)-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^*(2^n)-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 - Distributed

KW - Parallel

KW - Cluster Computing

U2 - 10.4230/LIPIcs.IPEC.2017.29

DO - 10.4230/LIPIcs.IPEC.2017.29

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - Proceedings of the 12th International Symposium on Parameterisiert and Exact Computation (IPEC 2017)

PB - Dagstuhl Publishing

ER -

Computing Treewidth on the GPU

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this