GPU Acceleration of BCP Procedure for SAT Algorithms

スポンサーリンク

概要

• 論文の詳細を見る

• The satisfiability problem (SAT) is widely applicable and one of the most basic NP-complete problems. This problem has been required to be solved as fast as possible because of its significance, but it takes exponential time in the worst case to solve. Therefore, we aim to save the computation time by parallel computing on a GPU. We propose parallelization of BCP (Boolean Constraint Propagation) procedure, one of the most effective techniques for SAT, on a GPU. For a 2.93GHz Intel Core i3 CPU and an NVIDIA GeForce GTX480, our experiment shows that the GPU accelerates our SAT solver based on our BCP-embedded divide and conquer algorithm 6.7 times faster than the CPU counterpart.

• 2012-07-09

著者

• Hironori Fujii

  Osaka Prefecture University

• Noriyuki Fujimoto

  Osaka Prefecture University

関連論文

• GPU Acceleration of BCP Procedure for SAT Algorithms

スポンサーリンク