Research Group Prof. Vornberger

Abstract: Work Load Balancing in Highly Parallel Depth-First Search

A. Reinefeld, V. Schnecke

Among the various approaches for parallel depth-first search (DFS), the stack-splitting schemes are most popular. However, as shown in this paper, dynamical stack-splitting is not suitable for massively parallel systems with several hundred processors. Initial work-load imbalances and work packets of dissimilar sizes cause a high communication overhead.

We compare work-load balancing strategies of two depth-first searches and propose a scheme that uses fine-grained fixed-sized work packets. In its iterative-deepening variant (named AIDA*) the global workload distribution improves from one iteration to the next. As a consequence, the communication overhead decreases with increasing search time.

Procs. Scalable High Performance Computing Conference SHPCC'94, Knoxville, TE, IEEE Comp. Sc. Press (1994), 773-780

Postscript (99 kB)