Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

This is done using work requests and responses in message passing machines and locking and extracting work in shared address space machines.

On reaching final state at a processor, all processors terminate.

Unexplored states can be conveniently stored as local stacks at processors.

The entire space is assigned to one processor to begin with.

Parallel Depth-First Search: Dynamic Load Balancing

• A generic scheme for dynamic load balancing.

Parameters in Parallel DFS: Work Splitting

• Work is split by splitting the stack into two.

• Ideally, we do not want either of the split pieces to be small.

• Select nodes near the bottom of the stack (node splitting), or

• Select some nodes from each level (stack splitting).

• The second strategy generally yields a more even split of the space.