Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 128-132 |
| Number of pages | 5 |
| Journal | Proceedings of the International Conference on Parallel Processing |
| Volume | 3 |
| State | Published - 1988 |