License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.29
URN: urn:nbn:de:0030-drops-85671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8567/
Go to the corresponding LIPIcs Volume Portal

van der Zanden, Tom C. ; Bodlaender, Hans L.

Computing Treewidth on the GPU

pdf-format:
LIPIcs-IPEC-2017-29.pdf (0.5 MB)

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 77x) compared to running the same algorithm on the CPU.

BibTeX - Entry

@InProceedings{vanderzanden_et_al:LIPIcs:2018:8567,
  author =	{Tom C. van der Zanden and Hans L. Bodlaender},
  title =	{{Computing Treewidth on the GPU}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Daniel Lokshtanov and Naomi Nishimura},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8567},
  URN =		{urn:nbn:de:0030-drops-85671},
  doi =		{10.4230/LIPIcs.IPEC.2017.29},
  annote =	{Keywords: treewidth, GPU, GPGPU, exact algorithms, graph algorithms, algorithm engineering}
}

Keywords: treewidth, GPU, GPGPU, exact algorithms, graph algorithms, algorithm engineering
Collection: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 02.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI