SATソルバの並列実行に関する一考察(<特集>「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(自動推論)  [in Japanese] Consideration on parallel execution of SAT solvers  [in Japanese]

Search this Article

Author(s)

Abstract

近年多くのSATソルバが提案されているが,個々のSATソルバには得意な問題も不得意な問題も存在する.そこで本論文では,様々な問題を速く解くために, SATソルバにおける並列実行を提案する.並列で実行することにより,個々のSATソルバにおけるパラメータを変更する実行方法よりも,高いパフォーマンスを得ることを目標にする.プラットフォームはPrologからJavaのトランスレ一夕であるProlog Cafeを用いる.Prolog Cafeのマル千スレッド化によってJavaで書かれたSATソルバをProlog Cafeから容易に呼び出し,複数のSATソルバを並列動作させることができる.この並列環境において,部分割当てによる局所集中法や,複数ソルバによる協調的な解決について考察を行う.

Recently, many SAT solvers has been proposed. There are many SAT problems which can be solved by some SAT solver quickly but by another SAT solver slowly. Thus we propose parallel execution of SAT solvers to solve many different SAT problems efficiently. We get higher perfomance by executing problems in parallel than by changing parameters of each SAT solvers. We use Prolog Cafe, which is a Prolog-to-Java source-to-source translator system as a platform. We can easily call a SAT solver written in Java on Prolog Cafe, and can execute many SAT solvers in parallel by multi-thread. We also consider a partially centerized method by partial assignment and a cooperative method by multiple SAT solvers.

Journal

  • IEICE technical report. Artificial intelligence and knowledge-based processing

    IEICE technical report. Artificial intelligence and knowledge-based processing 103(103), 41-46, 2003-05-22

    The Institute of Electronics, Information and Communication Engineers

References:  12

Cited by:  1

Codes

  • NII Article ID (NAID)
    110003176892
  • NII NACSIS-CAT ID (NCID)
    AN10013061
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    09135685
  • NDL Article ID
    6619790
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top