Depth-first search (DFS) is an important technique for finding a solution in a state space tree (or graph) containing one or more solutions. Many applications of Operations Research, Artificial Intelligence and other areas in Computing Science use DFS as a basic solution method. Because these problems are computationally intensive, the design of efficient parallel algorithms is of great importance.
In this paper, we compare two work-load balancing methods for massively parallel DFS: a stack-splitting scheme [13][7][1] and a fixed-packet DFS [16]. Both employ a simple task attraction mechanism. They mainly differ by the work distribution: While the first one splits its stack on demand, the second uses fixed size work packets.
We briefly discuss basic sequential search techniques, introduce the two parallel DFS variants, and present empirical performance results obtained on a large scale 1024-node MIMD system. Our theoretical analysis gives evidence that the fixed-packet DFS scales better on large systems than the commonly used stack-splitting, thereby confirming our empirical results.