| 講演名 | 1998/12/10 再構成可能なハードウェアを用いた充足可能性問題の解法 須山 敬之, 横尾 真, 名古屋 彰, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では再構成可能なハードウェアを用いた充足可能性問題(Satisfiability Problems:SAT)の解法について報告する.近年のEPGAに代表される再構成可能な論理素子の技術の進歩により, 利用者が手元でかつ簡単に専用の論理回路を実現することが可能となってきている.そこでSATの個々の問題専用の論理回路をFPGA上に構成することにより, その問題を高速に解く手法を提案する.SATつは和積形論理式を真にするような変数への値の割り当てが存在するかどうかを調べる問題であり, 代表的なNP完全問題の一つである.ここではハードウェア上で解くために適した, 探索木を削減する新たなアルゴリズムを提案し, その評価, 及び実装状況について述べる. |
| 抄録(英) | This paper presents a report on an approach for solving satisfiability problems (SAT) using Reconfigurable Hardware. Recently, due to advances in Reconfigurable Hardware such as FPGAs, users can now create their own reconfigurable logic circuits. This technology has enabled users to rapidly create logic circuits specialized for solving individual problem instances. Satisfiabitily problems were chosen because they make up an important subclass of NP-hard problems. We have developed a neew algorithm which is suitable for hardware and can reduce the search tree size. We report evaluation results and implementation status. |
| キーワード(和) | 充足可能性問題 / 再構成可能なハードウェア / 論理合成 / アルゴリズム |
| キーワード(英) | satisfiability problems / Reconfigurable Hardware / logic synthesis / algorithm |
| 資料番号 | VLD98-103,CPSY98-123 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1998/12/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 再構成可能なハードウェアを用いた充足可能性問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Satisfiability Problems using Reconfigurable Hardware |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 充足可能性問題 / satisfiability problems |
| キーワード(2)（和/英） | 再構成可能なハードウェア / Reconfigurable Hardware |
| キーワード(3)（和/英） | 論理合成 / logic synthesis |
| キーワード(4)（和/英） | アルゴリズム / algorithm |
| 第 1 著者 氏名（和/英） | 須山 敬之 / Takayuki Suyama |
| 第 1 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 第 2 著者 氏名（和/英） | 横尾 真 / Makoto Yokoo |
| 第 2 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 第 3 著者 氏名（和/英） | 名古屋 彰 / Akira Nagoya |
| 第 3 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 発表年月日 | 1998/12/10 |
| 資料番号 | VLD98-103,CPSY98-123 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 446 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |