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

Let W be serial work and WP be parallel work. Search overhead factor s is defined as WP/W.

Upper bound on speedup is p×(W/WP).

Parallel Depth-First Search

• How is the search space partitioned across processors?

• Different subtrees can be searched concurrently.

• However, subtrees can be very different in size.

• It is difficult to estimate the size of a subtree rooted at a node.

• Dynamic load balancing is required.

Parallel Depth-First Search

• The unstructured nature of tree search and the imbalance resulting from static partitioning.

Parallel Depth-First Search: Dynamic Load Balancing

• When a processor runs out of work, it gets more work from another processor.

•