Parallel depth first search. Part I. Implementation

V. Nageshwara Rao, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

92 Scopus citations

Abstract

This paper presents a parallel formulation of depth-first search which retains the storage efficiency of sequential depth-first search and can be mapped on to any MIMD architecture. To study its effectiveness it has been implemented to solve the 15-puzzle problem on three commercially available multiprocessors-Sequent Balance 21000, the Intel Hypercube and BBN Butterfly. We have been able to achieve fairly linear speedup on Sequent up to 30 processors (the maximum configuration available) and on the Intel Hypercube and BBN Butterfly up to 128 processors (the maximum configurations available). Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our experimental results show that hypercube and sharedmemory architectures are significantly better. At the heart of our parallel formulation is a dynamic work distribution scheme that divides the work between different processors. The effectiveness of the parallel formulation is strongly influenced by the work distribution scheme and architectural features such as presence/absence of shared memory, the diameter of the network, relative speed of the communication network, etc. In a companion paper,(1) we analyze the effectiveness of different load-balancing schemes and architectures, and also present new improved work distribution schemes.

Original languageEnglish (US)
Pages (from-to)479-499
Number of pages21
JournalInternational Journal of Parallel Programming
Volume16
Issue number6
DOIs
StatePublished - Dec 1 1987

Keywords

  • Parallel formulation
  • depth-first search
  • state-space trees
  • work distribution schemes

Fingerprint

Dive into the research topics of 'Parallel depth first search. Part I. Implementation'. Together they form a unique fingerprint.

Cite this