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

L. V. Kalé, Vikram A. Saletore

Research output: Contribution to journalArticlepeer-review


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
Issue number4
StatePublished - Aug 1990


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

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'Parallel state-space search for a first solution with consistent linear speedups'. Together they form a unique fingerprint.

Cite this