License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.24
URN: urn:nbn:de:0030-drops-153150
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15315/
Fichte, Johannes K. ;
Hecher, Markus ;
Roland, Valentin
Parallel Model Counting with CUDA: Algorithm Engineering for Efficient Hardware Utilization
Abstract
Propositional model counting (MC) and its extensions as well as applications in the area of probabilistic reasoning have received renewed attention in recent years. As a result, also the need for quickly solving counting-based problems with automated solvers is critical for certain areas. In this paper, we present experiments evaluating various techniques in order to improve the performance of parallel model counting on general purpose graphics processing units (GPGPUs). Thereby, we mainly consider engineering efficient algorithms for model counting on GPGPUs that utilize the treewidth of a propositional formula by means of dynamic programming. The combination of our techniques results in the solver GPUSAT3, which is based on the programming framework Cuda that -compared to other frameworks- shows superior extensibility and driver support. When combining all findings of this work, we show that GPUSAT3 not only solves more instances of the recent Model Counting Competition 2020 (MCC 2020) than existing GPGPU-based systems, but also solves those significantly faster. A portfolio with one of the best solvers of MCC 2020 and GPUSAT3 solves 19% more instances than the former alone in less than half of the runtime.
BibTeX - Entry
@InProceedings{fichte_et_al:LIPIcs.CP.2021.24,
author = {Fichte, Johannes K. and Hecher, Markus and Roland, Valentin},
title = {{Parallel Model Counting with CUDA: Algorithm Engineering for Efficient Hardware Utilization}},
booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
pages = {24:1--24:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-211-2},
ISSN = {1868-8969},
year = {2021},
volume = {210},
editor = {Michel, Laurent D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15315},
URN = {urn:nbn:de:0030-drops-153150},
doi = {10.4230/LIPIcs.CP.2021.24},
annote = {Keywords: Propositional Satisfiability, GPGPU, Model Counting, Treewidth, Tree Decomposition}
}
