| 講演名 | 2007-05-31 マルチコア環境に向け並列SATソルバの開発(「自動化:推論,発見,学習,データマイニング」及び一般) 高見 明秀, 岩沼 宏治, 鍋島 英知, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文では,実用的な高速並列SATソルバの開発を目的として,最新のSATソルバ技術に基づくマルチコア環境向けのSATソルバを提案する.具体的には,SATソルバの探索戦略のパラメータを調整することで,各CPUが異なる領域を探索するようにバイアスをかけ,さらに学習節を共有することで探索領域の効率的な枝狩りを図る.提案手法に基づくソルバを実装し,ベンチマーク問題集で評価実験を行った結果,2つのCPU利用時に約2倍の速度向上が得られることを確認した.また,4つのCPU利用時には,1つのCPUでは制限時間内に解くことのできなかった問題を2問解くことができた. |
| 抄録(英) | In this paper, we propose a new parallel SAT solver based on the fastest sequential SAT solver "MINI-SAT" for a multi-core processor environment. Our solver consists of multi-processes. Each process executes a SAT solver which solves the same SAT problem using different search strategy parameters. Each process executes a SAT solver which solves the same SAT problem using different search strategy parameters and shares learned clauses each other for pruning redundant search space. The experimental result showed that our solver using 2-CPUs is approximately two times faster than -1-CPU, and 4-CPUs can solve two SAT problems which can not be solved by 1-CPU within a certain time limit. |
| キーワード(和) | SAT / 並列実行 / マルチコア環境 / 学習節共有 |
| キーワード(英) | SAT / parallel processing / multi-core environment / sharing learnt clauses |
| 資料番号 | AI2007-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 2007/5/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マルチコア環境に向け並列SATソルバの開発(「自動化:推論,発見,学習,データマイニング」及び一般) |
| サブタイトル（和） | |
| タイトル（英） | A Parallel SAT Solver for Multi-Core Processor Environment |
| サブタイトル（和） | |
| キーワード(1)（和/英） | SAT / SAT |
| キーワード(2)（和/英） | 並列実行 / parallel processing |
| キーワード(3)（和/英） | マルチコア環境 / multi-core environment |
| キーワード(4)（和/英） | 学習節共有 / sharing learnt clauses |
| 第 1 著者 氏名（和/英） | 高見 明秀 / Akihide TAKAMI |
| 第 1 著者 所属（和/英） | 山梨大学大学院医学工学総合教育部修士課程コンピュータ・メディア工学専攻 Computer Science and Media Engineering, Master's Course, Graduate School of Medical and Engineering Science Department of Education, University of Yamanashi |
| 第 2 著者 氏名（和/英） | 岩沼 宏治 / Koji IWANUMA |
| 第 2 著者 所属（和/英） | 山梨大学大学院医学工学総合研究部 Graduate School of Medical and Engineering Science Department of Research, University of Yamanashi |
| 第 3 著者 氏名（和/英） | 鍋島 英知 / Hidetomo NABESHIMA |
| 第 3 著者 所属（和/英） | 山梨大学大学院医学工学総合研究部 Graduate School of Medical and Engineering Science Department of Research, University of Yamanashi |
| 発表年月日 | 2007-05-31 |
| 資料番号 | AI2007-2 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 78 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |