Parallel depth first search on the ring architecture

Vipin Kumar, V. Nageshwara Rao, K. Ramesh

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


The implementation and analysis of a parallel depth-first search on the ring architecture is presented. At the heart of the parallel formulation of depth-first search is a dynamic work-distribution scheme that divides the work among different processors. The effectiveness of the parallel formulation is strongly influenced by the choice of the work-distribution scheme. In particular, a commonly used scheme is found to give very poor performance on large rings (>32 processors). A scheme that performs well on rings of up to 128 processors is presented. The concept of isoefficiency function is introduced to characterize the effectiveness of different work-distribution schemes.

Original languageEnglish (US)
Pages (from-to)128-132
Number of pages5
JournalProceedings of the International Conference on Parallel Processing
StatePublished - Dec 1 1988

Cite this