Parallel state-space search for a first solution with consistent linear speedups

L. V. Kalé, Vikram A. Saletore

Research output: Contribution to journalArticle

Abstract

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 conducting 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 additon 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.

Original languageEnglish (US)
Pages (from-to)251-293
Number of pages43
JournalInternational Journal of Parallel Programming
Volume19
Issue number4
DOIs
StatePublished - Aug 1 1990

    Fingerprint

Keywords

  • Parallel algorithms
  • first solution
  • linear speedup
  • parallel depth-first search
  • state-space trees

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Cite this