Computing Treewidth on the GPU
Computing Treewidth on the GPU
复制标题
在 GPU 上计算树宽
DOI：
10.4230/lipics.ipec.2017.29
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
H. Bodlaender
中科院分区：
文献类型：
--
作者：
Tom C. van der Zanden;H. Bodlaender
提出了一种在GPU上计算图树宽度的并行算法。我们在OpenCL中实现了该算法，并对其性能进行了实验评估。我们的算法基于O*(2^n)时间算法，该算法使用类似于Held-Karp的动态规划方法来探索图的消去顺序。我们使用Bloom过滤器来检测重复的溶液。
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.
影响因子：
1
作者：
Tamaki, Hisao
通讯作者：
Tamaki, Hisao