講演抄録/キーワード |
講演名 |
2021-06-09 15:00
M-KUBOSボード上での充足可能性問題ソルバー・AmoebaSATの実装 ○閻 英傑・青野真士・天野英晴(慶大)・大古田香織・福田真悟・斉藤健太(Amoeba Energy)・葛西誠也(北大) RECONF2021-13 |
抄録 |
(和) |
充足可能性問題(Boolean Satisfiability Problem; SAT) はNP 完全であることが知られており、その迅速な解
探索手法は、移動体や通信の制御やスケジューリングなどの様々な実社会課題における制約充足解の導出に応用可能
である。これらの応用分野はタイミング制約があるため、高速動作が要求され、FPGA 上での実装が有効である。本
論文では、SAT の確率的局所探索アルゴリズムの一つである「AmoebaSAT」を、Zynq M-KUBOS ボードにHLS によ
り実装した結果について報告する。従来のAmoebaSAT のFPGA 実装は、高速であったが、対象とする問題サイズが
300 変数程度に制限されていた。また、問題インスタンスを変更するたびに構成情報を再生成する必要があった。そこ
で本研究では、AmoebaSAT の制約規則のうち最も多くのメモリ量を要する部分を省略したモデル「AmoebaSATslim」
を開発した。AmoebaSATslim はAmoebaSAT と同等の解探索能力を実現できると共に、FPGA のハードウェア資源を
大幅に節約できる。これにより、3750 変数で16350 節の問題インスタンスの解を、構成情報を固定したまま入力パラ
メータの変更のみで探索可能となった。性能面では既報告のFPGA 実装SAT ソルバーには劣るものの、x86 サーバで
ソフトウェアとして実装されたAmoebaSATslim の6.5 倍程度の性能向上を実現した。 |
(英) |
(Not available yet) |
キーワード |
(和) |
制約充足問題 / AmoebaSAT / FPGA / / / / / |
(英) |
SAT / AmoebaSAT / FPGA / / / / / |
文献情報 |
信学技報, vol. 121, no. 59, RECONF2021-13, pp. 68-73, 2021年6月. |
資料番号 |
RECONF2021-13 |
発行日 |
2021-06-01 (RECONF) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
査読に ついて |
本技術報告は査読を経ていない技術報告であり,推敲を加えられていずれかの場に発表されることがあります. |
PDFダウンロード |
RECONF2021-13 |