Consistent Linear Speedups for a First Solution in Parallel State-Space Search
Association for the Advancement of Artificial Intelligence (AAAI) 1990
Publication Type: Paper
Consider the problem of exploring a large state-space for a goal state where although many such states may exist in the state-space, finding any one state satisfying the requirements is sufficient. All the methods known until now for conduction such search in parallel using multiprocessors fail to provide consistent linear speedups over sequential execution. The speedups vary between sublinear to superlinear and from one execution to another. Further, adding more processors may sometimes lead to a slow-down rather than speedup, giving rise to speedup anomalies reported in literature. We present a prioritizing strategy which yields consistent speedups that are close to P with P processors, and that monotonically increase with the addition of processors. This is achieved by keeping the total number of nodes expanded during parallel search very close to that of a sequential search. In addition, the strategy requires substantially smaller memory relative to other methods. The performance of this strategy is demonstrated on a multiprocessor with several state-space search problems.
V. Saletore and L.V. Kale, "Consistent Linear Speedups for a First Solution in Parallel State-Space Search", Proceedings of the AAAI, August 1990.