.
When a processor has finished its work,
it tries to get an unsearched subtree from another processor.
When a goal node is found, all of them quit.
DFS can be implemented on a MIMD system
by partitioning the search space into subtrees that are searched in parallel.
Each processor searches a disjoint subtree in a depth-first fashion,
which can be done asynchronously without any communication.
When a processor has finished its work,
it tries to get an unsearched subtree from another processor.
When a goal node is found, all of them quit.
Effective work-load balancing is important to keep all processors busy. In the following, we describe two variants that are based on simple task attraction: a dynamical stack-splitting method and a scheme using fine-grained fixed work packets.