
158 Designing Scientific Applications on GPUs
FIGURE 8.1. Illustration of the parallel tree exploration model.
8.3.1 The parallel tree exploration model
Tree-based strategies consist of building and/or exploring the solution tree
in parallel by performing operations on several subproblems simultaneously.
This coarse-grained type of parallelism affects the general structure of the
B&B algorithm and makes it highly irregular.
The parallel tree exploration model, illustrated in Figure 8.1, consists of
visiting in parallel different paths of the same tree. The search tree is explored
in parallel by performing the branching, selection, bounding, and elimination ...