マルチプロセッサシステムによる並行探索 : 仮説検証法の場合

概要

論文の詳細を見る
This paper describes the implementation of a concurrent search algorithm on the distributed system which consists of 15 processors connected by VME-bus. In such a system, it is necessary to exchange messages between asynchronous processors. The efficiency of the system goes down when message exchanges are quite often. An effort is required to make the message exchanges as less as possible. The requirment would be reflected in the problem decomposition methods, namely, to decompose a problem into mutually independent subproblems. We proposed two distinct methods answering the requirment. In this paper, we apply one of them, called Hypothesis Verification Method, and describe the realization of a distributed system appropriate for it. We report on the design and evaluation. Especially, the following two points are investigated : (1) How fast can the system solve 2×2×2 Rubik's Cube ; (2) There exist several problems for which the speed-up ratio superlinearly increases with the number of processors. This phenomenon is called extraordinary acceleration. We investigate the reason why this phenomenon occurs.
社団法人人工知能学会の論文
1990-11-01