Document Open Access Logo

Computing Treewidth on the GPU

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.29.pdf
  • Filesize: 492 kB
  • 13 pages

Document Identifiers

Author Details

Tom C. van der Zanden
Hans L. Bodlaender

Cite AsGet BibTex

Tom C. van der Zanden and Hans L. Bodlaender. Computing Treewidth on the GPU. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.IPEC.2017.29

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.
Keywords
  • treewidth
  • GPU
  • GPGPU
  • exact algorithms
  • graph algorithms
  • algorithm engineering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Austin Appleby. SMHasher. Accessed 2017-04-12. URL: https://github.com/aappleby/smhasher.
  2. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-426, 1970. Google Scholar
  3. Hans L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25:1305-1317, 1996. Google Scholar
  4. Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. On exact algorithms for treewidth. ACM Trans. Algorithms, 9(1):12:1-12:23, 2012. Google Scholar
  5. Hans L. Bodlaender and Arie M.C.A. Koster. Safe separators for treewidth. Discrete Mathematics, 306(3):337-350, 2006. Google Scholar
  6. Hans L. Bodlaender and Arie M.C.A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255-269, 2008. Google Scholar
  7. Hans L. Bodlaender and Arie M.C.A. Koster. Treewidth computations II. Lower bounds. Information and Computation, 209(7):1103-1119, 2011. Google Scholar
  8. Hans L. Bodlaender and T. C. van der Zanden. BZTreewidth. Accessed 2017-04-11. URL: https://github.com/TomvdZanden/BZTreewidth.
  9. Hans L. Bodlaender and T. C. van der Zanden. GPGPU treewidth. Accessed 2017-04-21. URL: https://github.com/TomvdZanden/GPGPU-Treewidth.
  10. François Clautiaux, Jacques Carlier, Aziz Moukrim, and Stéphane Nègre. New lower and upper bounds for graph treewidth. In Klaus Jansen, Marian Margraf, Monaldo Mastrolilli, and José D. P. Rolim, editors, Experimental and Efficient Algorithms: Second International Workshop, WEA 2003, pages 70-80. Springer, 2003. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 1st edition, 2015. Google Scholar
  12. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The parameterized algorithms and computational experiments challenge (PACE). Accessed 2017-04-05. URL: https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/.
  13. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The first parameterized algorithms and computational experiments challenge. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 30:1-30:9. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2016.30.
  14. P. Alex Dow. Search Algorithms for Exact Treewidth. PhD thesis, 2010. Google Scholar
  15. P. Alex Dow and Richard E. Korf. Best-first search for treewidth. In Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 2, AAAI'07, pages 1146-1151. AAAI Press, 2007. Google Scholar
  16. Vibhav Gogate and Rina Dechter. A complete anytime algorithm for treewidth. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, pages 201-208. AUAI Press, 2004. Google Scholar
  17. Alexander Hein and Arie M. C. A. Koster. An experimental evaluation of treewidth at most four reductions. In Panos M. Pardalos and Steffen Rebennack, editors, Proceedings of the 10th International Symposium on Experimental and Efficient Algorithms, SEA 2011, volume 6630 of LNCS, pages 218-229. Springer, 2011. Google Scholar
  18. M. Held and R. Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10:196-210, 1962. Google Scholar
  19. Adam Kirsch and Michael Mitzenmacher. Less hashing, same performance: Building a better bloom filter. In Yossi Azar and Thomas Erlebach, editors, Algorithms - ESA 2006: 14th Annual European Symposium, pages 456-467. Springer, 2006. Google Scholar
  20. NVIDIA. NVIDIA GeForce GTX 1080 Whitepaper. Accessed 2017-04-10. URL: http://international.download.nvidia.com/geforce-com/international/pdfs/GeForce_GTX_1080_Whitepaper_FINAL.pdf.
  21. NVIDIA. NVIDIA’s Next Generation CUDA Compute Architecture: FERMI. Accessed 2017-04-12. URL: http://www.nvidia.com/content/pdf/fermi_white_papers/nvidia_fermi_compute_architecture_whitepaper.pdf.
  22. Hisao Tamaki. Positive-instance driven dynamic programming for treewidth. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 68:1-68:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.68.
  23. Tom C. van der Zanden and Hans L. Bodlaender. Computing Treewidth on the GPU. Preprint, 2017. URL: http://arxiv.org/abs/arXiv:1709.09990.
  24. Thomas C. van Dijk, Jan-Pieter van den Heuvel, and Wouter Slob. Computing treewidth with libtw, 2006. Accessed 2017-06-16. URL: http://www.treewidth.com/treewidth.
  25. Y. Yuan. A fast parallel branch and bound algorithm for treewidth. In 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, pages 472-479, 2011. Google Scholar
  26. Rong Zhou and Eric A. Hansen. Combining breadth-first and depth-first strategies in searching for treewidth. In Proceedings of the 21st International Joint Conference on Artifical Intelligence, IJCAI'09, pages 640-645. Morgan Kaufmann Publishers Inc., 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact