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)|
|Number of pages||5|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - Dec 1 1988|