SATアルゴリズムにおけるBCP処理のGPUを用いた並列化

スポンサーリンク

概要

論文の詳細を見る
充足可能性判定問題 (SAT) は,応用範囲の広い最も基本的な NP 完全問題の一つである.SAT を解くためには最悪指数時間かかってしまうが,重要な問題なのでできるだけ高速に解きたいという要求がある.そこで我々は,GPU を用いて並列計算を行うことで,その計算時間を節約しようと考えた.本論文では,SAT アルゴリズムの主要な高速化手法のひとつである BCP ( Boolean Constraint Propagation) 処理を GPU を用いて並列化する手法を提案する.分割統治法に BCP 処理を組み合わせた SAT アルゴリズムに提案手法を適用し,CPU に 2.93GHz Intel Core i3,GPU に NVIDIA GeForce GTX480 を用いた環境で評価実験を行ったところ,SAT ソルバとしての速度向上率は 6.7 倍であった.
2011-11-21

著者

関連論文

もっと見る

スポンサーリンク