文献

J-GLOBAL ID：202002221927021604   整理番号：20A2258775

回路レベルのアメーバにヒントを得たSATソルバ【JST・京大機械翻訳】

A Circuit-Level Amoeba-Inspired SAT Solver

著者 (4件)： Takeuchi Naoki (Institute of Advanced Sciences, Yokohama National University, Yokohama, Japan) ,  Aono Masashi (Faculty of Environment and Information Studies, Keio University, Fujisawa, Japan) ,  Hara-Azumi Yuko (School of Engineering, Tokyo Institute of Technology, Tokyo, Japan) ,  Ayala Christopher L. (Institute of Advanced Sciences, Yokohama National University, Yokohama, Japan)
資料名： IEEE Transactions on Circuits and Systems 2: Express Briefs  (IEEE Transactions on Circuits and Systems 2: Express Briefs)
巻： 67  号： 10  ページ： 2139-2143  発行年： 2020年 
JST資料番号： W0347A  ISSN： 1549-7747  CODEN： ITCSFK  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： AmbSAT(またはAmoebaSAT)は,Boole satisfibility問題(SAT)に対する解を探索するための生物学的に触発された確率的局所探索(SLS)ソルバである。AmbSATは,各反復段階で並列に複数の変数を更新し,従って,AmbSATはSATインスタンスの特定の集合に対して,いくつかの他の従来のSLSソルバよりも少ない数の反復ステップで解を見つけることができる。しかしながら,AmbSATの並列性は,多くのクロックサイクルが各反復を実行するのに必要である,汎用マイクロプロセッサと互換性がない。したがって,AmbSATは,解を迅速に見つけるためにAmbSATの並列性を利用することができる特別なハードウェアを必要とする。この短報では,著者らは,回路レベルAmbSAT(CL-AmbSAT)と呼ぶAmbSATと同様の方法でSATに対する解を探索する回路モデルを提案した。提案アプローチのスケーラビリティを推定するために設計したランダムに生成されたSATインスタンスの集合に対するCL-AmbSATの探索性能を評価するために数値シミュレーションを行った。シミュレーション結果は,CL-AmbSATが強力なSLSソルバ,ProbSATよりも少ない反復数を持つ解を見出し,AmbSATさえ凌駕することを示した。CL-AmbSATは変数を更新するために単純な組合せ論理を使用するので,CL-AmbSATは様々なハードウェアに容易に実装できる。Copyright 2020 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： シミュレーション ,  互換性 ,  クロック ,  *アメーバ ,  組合せ論 ,  ハードウェア ,  マイクロプロセッサ ,  回路モデル ,  近傍探索法
準シソーラス用語： 数値シミュレーション ,  *ソルバ ,  探索性能 , 【Automatic Indexing@JST】

分類 (1件)： パターン認識  (JE07000S)

タイトルに関連する用語 (4件)： アメーバ ,  ヒント ,  SAT ,  ソルバ