再構成可能なハードウェアを用いた充足可能性問題の解法

須山 敬之  横尾 真  澤田 宏  名古屋 彰  

誌名
電子情報通信学会論文誌 D   Vol.J84-D1   No.4   pp.410-420
発行日: 2001/04/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 人工知能,認知科学
キーワード: 
充足可能性問題,  リコンフィギャラブルコンピューティング,  FPGA,  論理合成,  制約充足問題,  

本文: PDF(864.4KB)
>>論文を購入


あらまし: 
本論文ではFPGA(Field Programmable Gate Arrays)と論理合成システムを用いた充足可能性問題(Satisfiability Problems: SAT)の新しい解法を提案する.この解法の特徴は,個々の問題のインスタンスに特化した論理回路をFPGAに構成する点である.このアプローチは近年のリコンフィギャラブルコンピューティング技術の進歩により可能となったものであり,アルゴリズムの設計方針に新しい可能性を開くものである.SATは制約充足問題の一種であり,多くの応用問題を表現できる一般的な枠組みである.本論文ではハードウェア上の実行に適した種々のアルゴリズムの提案を行う.これらのアルゴリズム中で最も高性能なものは,動的な変数の順序付けヒューリスティックを導入したDavis-Putnamアルゴリズムと同等な性能をもつ.シミュレーションを用いた評価結果により,本論文で提案する手法により,非常に難しいランダムに生成された400変数の3-SAT問題のインスタンスが,回路をマシンサイクル10 MHzで動作させた場合に,1.6分で解が得られることが示された.更に,128変数,節の個数256の非常に難しい問題のインスタンスを,FPGA上に実装し動作することを確認した.