2024-03-28T22:53:38Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000294982023-04-27T10:00:04Z01164:02240:02283:02288
PVMによるSAT並列局所探索プログラムA parallel local search program for SAT using PVMjpnhttp://id.nii.ac.jp/1001/00029498/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=29498&item_no=1&attribute_id=1&file_no=1Copyright (c) 2000 by the Information Processing Society of Japan京都大学大学院情報学研究科京都大学大学院情報学研究科京都大学大学院情報学研究科京都大学大学院情報学研究科梅本, 潤宮崎, 修一岡部, 寿男岩間, 一雄充足可能性問題(SAT)は基本的な組み合わせ問題である.高速なSATの解法アルゴリズムとして局所探索法があるが,大規模な問題にも対応するため更なる高速化の重要性が高まっている.そこで,本稿では局所探索法をネットワーク並列計算用ソフトウェアシステムであるPVM(Parallel Virtual Machine)で並列化して実行する高速化手法を提案する.局所探索法のTRYという実行単位を各計算機で並列に実行するTRY同時実行により,効率的に高速化できることを示した.さらに,2nd DIMACS Implementation Challengeのsatisfiabilityのベンチマークに対して計算機実験を行い,これまで解かれていなかった例題をワークステーション70台を用いて8 500秒程で解くことができた.The Satisfiability Problem(SAT) is one of the most fundamental combinatorial problems. The local search algorithm, which was developed recently, is probably the most popular SAT algorithm because of its surprising efficiency. The purpose of this paper is to speed up local search using PVM(Parallel Virtual Machine), which is the software system designed for networked parallel computing. We show that the local search algorithm can be efficiantly speeded up by the method 'TRY simultaneous execution'. The method executes TRYs, the unit process of the local search, on several computers in parallel, Furthermore, we show experimental results using benchmarks of 2nd DIMACS Implemaentation Challenge. In this experiment, we were able to solve an instance, which has not been solved by other programs, in about 8,500 seconds using 70 workstations.AN10463942情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC)200023(1999-HPC-080)951002000-03-022009-06-30