Parallel depth first search. Part II. Analysis

Vipin Kumar, V. Nageshwara Rao

Research output: Contribution to journalArticle

111 Scopus citations

Abstract

This paper presents the analysis of a parallel formulation of depth-first search. At the heart of this 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 the target architecture. We introduce the concept of isoefficiency function to characterize the effectiveness of different architectures and work-distribution schemes. Many researchers considered the ring architecture to be quite suitable for parallel depth-first search. Our analytical and experimental results show that hypercube and shared-memory architectures are significantly better. The analysis of previously known work-distribution schemes motivated the design of substantially improved schemes for ring and shared-memory architectures. In particular, we present a work-distribution algorithm that guarantees close to optimal performance on a shared-memory/ω-network-with-message-combining architecture (e.g. RP3). Much of the analysis presented in this paper is applicable to other parallel algorithms in which work is dynamically shared between different processors (e.g., parallel divide-and-conquer algorithms). The concept of isoefficiency is useful in characterizing the scalability of a variety of parallel algorithms.

Original languageEnglish (US)
Pages (from-to)501-519
Number of pages19
JournalInternational Journal of Parallel Programming
Volume16
Issue number6
DOIs
StatePublished - Dec 1 1987

Keywords

  • Parallel algorithm
  • depth-first search
  • isoefficiency function
  • work distribution schemes

Fingerprint Dive into the research topics of 'Parallel depth first search. Part II. Analysis'. Together they form a unique fingerprint.

Cite this