FPGAと論理合成システムを用いた充足可能性問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
本稿ではFPGA (Field Programmable Gate Arrays)と論理合成システムを用いた充足可能性問題(Satisfability Problems: SAT)の解法について報告する.近年のFPGAに代表される再構成可能な論理素子の技術の進歩により,利用者が手元でかつ簡単に専用の論理回路を実現することが可能となってきている. またハードウェア記述言語からの論理合成システムを用いることにより,ハードウェアの設計をより短期間に行うことができる.そこでこれらの技術を用いて, SATの個々の問題専用の論理回路をFPGA上に構成することにより,その問題を高速に解く手法を提案する.SATとは和積形論理式を真にするような変数への値の割り当てが存在するかどうかを調べる問題であり,代表的なNP完全問題の一つである. ここではハードウェア上で解くために適した新たなアルゴリズムを提案し,その実装状況について述べる.
- 1996-12-13
著者
-
横尾 真
Nttコミュニケーション科学研究所
-
須山 敬之
Ntt西日本研究開発センタ
-
名古屋 彰
NTT未来ねっと研究所
-
名古屋 彰
NTTコミュニケーション科学研究所
-
須山 敬之
NTTコミュニケーション科学研究所
-
津田 宏
NTTコミュニケーション科学研究所
-
須山 敬之
Nttコミュニケーション科学基礎研究所
関連論文
- 開放型プロダクションシステムにおけるデータ依存関係の管理
- 動的再構成可能ハードウェア上へのスケーラブルスイッチの実装に関する検討
- 組合せオークションの高速な準最適勝者決定アルゴリズム
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- Addition-Shift-Sequence問題の計算複雑度について
- FPGAと論理合成システムを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- しきい論理に基づく再構成可能デバイスの可変論理部
- しきい論理に基づく再構成可能デバイスの可変論理部
- しきい論理に基づく再構成可能デバイスの可変論理部
- ニューロンMOSによる対称関数回路の設計
- ニューロンMOSによる対称関数回路の設計手法
- ニューロンMOSを可変論理部に用いた再構成可能デバイスに関する検討
- ニューロンMOSによる対称関数回路の設計手法
- ニューロンMOSを可変論理部に用いた再構成可能デバイスに関する検討
- SPFD : 論理関数の自由度の新しい表現方法
- D-6-10 再構成メッシュの線形時間遅延モデルについて
- 再構成可能なハードウェアを用いた線形ブロック符号の性能評価の高速化
- 再構成可能なハードウェアを用いた線形ブロック符号の性能評価の高速化
- 論理関数の種々の分解手法を統合したLUT回路合成法
- 論理関数の種々の分解手法を統合したLUT回路合成法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 論理関数の種々の分解手法を統合したLUT回路合成法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 変数の重なりのない単純な関数分解を用いた組合せ回路の改善方法
- ED2000-111 / SDM2000-93 / ICD2000-47 動的再構成可能論理LSI : PCA-1
- ED2000-111 / SDM2000-93 / ICD2000-47 動的再構成可能論理LSI : PCA-1
- ED2000-111 / SDM2000-93 / ICD2000-47 動的再構成可能論理LSI : PCA-1
- 布線論理による汎用計算機構 : プラスティックセルアーキテクチャ
- 意味的等価性検証に基づく記述式解答文の採点法(テキストの類似性・文処理モデル)
- 意味的等価性検証に基づく記述式解答文の採点法(テキストの類似性・文処理モデル)
- 自己再構成機能をもつ非同期式LSIの回路高速化の検討
- 自己再構成機能をもつ非同期式LSIの回路高速化の検討
- SA-1-1 PCAで実現される自己参照・書換・増殖可能なハードウェア
- 非同期式動的再構成可能LSIによる自己複製回路
- 非同期式動的再構成可能LSIによる自己複製回路
- 非同期式動的再構成可能LSIによる自己複製回路
- PCA可変部への組合わせ回路のマッピング手法の検討(システム設計及び一般)
- PCA可変部への組合わせ回路のマッピング手法の検討(システム設計及び一般)
- 全米人工知能会議AAAI-94報告
- 会議報告 IJCAI-01
- 多状態コミットメント探索とその評価
- 多状態コミットメント実時間A^*アルゴリズムの性能解析
- 多状態コミットメント探索の性能評価
- ヒューリスティック探索へのn-状態コミットメントの導入
- ヒューリスティック探索への n-状態コミットメントの導入
- 淘汰を用いたマルチエージェント実時間探索の高速化 : 協調探索への競争の導入 ( マルチエージェント)
- マルチエージェント合意形成のための回覧板プロトコル
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散制約充足におけるnogood学習の効果
- 複雑な局所問題に対応する分散制約充足アルゴリズム
- 分散不完全制約充足問題
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散breakout : 反復改善型分散制約充足アルゴリズム(並列処理)
- CSPの新しい展開 : 分散/動的/不完全CSP ( 制約充足問題の基礎と応用)
- ICMAS'95報告
- 自律的再構成可能なハードウェアにおける試験方式の検討
- 自律的再構成可能なハードウェアにおける試験方式の検討
- 自律的再構成可能なハードウェアにおける試験方式の検討
- フラクタル画像圧縮の再構成可能アーキテクチャによる実現法
- フラクタル画像圧縮の再構成可能アーキテクチャによる実現法
- エージェントの組織による実時間連続問題解決
- ATMSを用いた分散制約充足問題の解法
- AAAI-99参加報告
- PARTHENONにおける最新の論理合成機能
- (1)マルチエージェントシステム(会議報告)
- 座談会 : AIと電子商取引の展望(AIの観点から見た電子商取引の将来像)
- マルチエージェントシステム
- Forbus, K. D. and de Kleer, J. : Building Problem Solvers, MIT Press (1993).
- 分散制約充足の高速化と通信網回線設定への適用
- 分散制約充足の通信網回線設定への適用
- 分散制約充足による分散協調問題解決の定式化とその解法
- 割り当て確率に基づくデータフローグラフのスケジューリング手法
- 割り当て確率に基づくデータフローグラフのスケジューリング手法
- 変数の重なりのない単純な関数分解を用いた組合せ回路の改善方法
- 論理関数の自由度の新しい表現方法とそのFPGA向け論理設計への応用
- 論理関数の自由度の新しい表現方法とそのFPGA向け論理設計への応用
- 対称変数の検出による関数分解の高速化と多段論理合成への応用
- 対称変数の検出による関数分解の高速化と多段論理合成への応用
- 架空名義表明のメカニズムデザインに対する影響 : インターネットでの集団意思決定に向けて(特集●社会・経済におけるマルチエージェント)
- 不正行為を防ぐ電子商取引メカニズム
- 電子商取引における一般化Vickreyオークションの問題点 : 架空名義入札に対する頑健性
- 新規参入を容易とする頑健な情報財取引メカニズムの提案
- 新規参入を容易とする頑健な情報財取引メカニズムの提案
- 電子商取引における一般化Vickreyオークションの問題点 : 架空名義入札に対する頑健性
- 繰り返しゲームにおいて協調行動を生成する先読み型行動選択方法
- ハードウェア/ソフトウェア協調設計システム
- ハードウェア/ソフトウェア協調設計システム
- インターネットオークションの理論と応用(AIの観点から見た電子商取引の将来像)
- 制約充足問題の地形の解析
- 柔軟で動的なエージェントの組織構造を用いた分散制約充足アルゴリズム
- 分散制約充足問題における制約緩和
- 分散探索とその周辺 ( マルチエージェントと協調計算)
- 弱コミットメント戦略を用いた制約充足問題の解法
- 実時間制約充足問題とその解法
- 弱コミットメント戦略を用いた制約充足問題の解法
- 相手エージェントを考慮した行動戦略の調整
- 組合せオークションの高速な準最適勝者決定アルゴリズム
- ACM EC-00参加報告
- 新しい並列処理ア-キテクチャとその設計技術