FPGAを用いた大規模な充足可能性問題の高速計算(アルゴリズム理論)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,Field Programmable Gate Array (FPGA)を用いた,WSATアルゴリズムに基づく大規模な充足可能性問題(SAT)に対する高速計算システム(SAT Solver)の提案を行う.WSATアルゴリズムは,SATを解くための確率的局所探索アルゴリズム(Stochastic Local Search Algorithm)のうち,最も高性能なアルゴリズムの一つであり,かつ複雑な制御を必要としないことからハードウェア化に適している.小規模な問題はソフトウェアによって十分高速に解くことができるため,ハードウェアシステムにおいては,大規模な問題を高速に解くことが重要である.これまでのハードウェアシステムでは,高速化のため,SAT問題におけるクローズをすべて並列に評価していた.これに対して,本システムでは,(1)クローズの値を評価する際,変数のフリップにより値が変化する可能性のあるクローズのみを並列に評価することによる回路規模の小型化,(2)複数のFIFO tree及びBufferを用いた非充足クローズの管理に基づくマルチスレッド処理による解探索の高速化を行っている.本研究では,従来のハードウェアシステムでは解くことができなかった大規模な問題である,2000変数/8500クローズまでの問題を解くことができる回路を,XILINX社製FPGAであるXC2V6000に実装し,従来のハードウェアシステムを上回る性能を示した.
- 社団法人電子情報通信学会の論文
- 2007-10-01
著者
関連論文
- 幾つかの画像処理問題を用いたGPUとFPGAの性能比較(リコンフィギャラブル応用)
- FPGAグリッドを用いたHMMERの高速化 (リコンフィギャラブルシステム)
- FPGAを用いたHMMERの高速化(リコンフィギャラブル応用)
- 1H-5 モラル付き囚人のディレンマの高速計算
- FPGAを用いた繰り返し囚人のジレンマの高速計算
- 1H-4 FPGAを用いた将棋の高速計算の実現
- 1H-3 Field Programmable Gate Array による複雑適応系の計算の高速化
- 1H-2 Field Programmable Gate Array を用いた探索問題の高速化
- 1H-1 FPGAによるCPUアクセラレータ
- FPGAによるGAの計算の高速化
- FPGAを用いた全探索法による可変ブロックサイズ動き予測の実現 (リコンフィギャラブルシステム)
- FPGAを用いたCLAHEの実時間処理の実現(リコンフィギャラブル応用1)
- FPGAを用いた様々な大きさ,回転角を持つパターンの検出手法の検討(リコンフィギャラブル応用2)
- FPGAを用いた全探索法による可変ブロックサイズ動き予測の実現(リコンフィギャラブル応用1)
- FPGAを用いた回転パターンの実時間検出(応用1)
- FPGAを用いた局所的コントラスト強調の実時間処理の実現(リコンフィギャラブル応用)
- FPGAを用いた大規模な充足可能性問題の高速計算(アルゴリズム理論)
- FPGAを用いたWSATアルゴリズムの高速計算(応用技術,リコンフィギャラブルシステム論文)
- FPGAによる実時間線分抽出の実現(リコンフィギャラブル応用1)
- FPGAグリッドを用いたHMMERの高速化(数値計算)
- FPGAを用いたMean-Shiftフィルタの高速計算 (リコンフィギャラブルシステム)
- FPGAによるSAT問題のプリプロセッサの実現 (リコンフィギャラブルシステム)
- FPGAを用いたMean-Shiftフィルタの高速計算(画像処理)
- FPGAによるDP-Treeアルゴリズムを用いたステレオビジョンシステムの構築(画像処理)
- FPGAによるSAT問題のプリプロセッサの実現(アプリケーション)
- FPGAを用いたグラフカットセグメンテーションの高速化(画像処理(1))
- FPGAを用いたショートリードマッピングの高速化(FPGA応用(1),リコンフィギャラブルシステム,一般)
- FPGAを用いたグラフカットセグメンテーションの高速化