
GPU-accelerated tree-based exact optimization methods 163
FIGURE 8.6. The overall architecture of the GPU-accelerated branch-and-
bound algorithm based on the parallel evaluation of bounds.
lower bound’s implementation raises mainly two challenges. The first one is
related to the SIMD model of the GPU and to the implementation of the
LB. Indeed, although typically every GPU thread will run the identical lower
bound function, the body of the lower bound can contain conditions on thread
identifiers and data. This implies that different instructions are executed in
some threads. In SIMD architectures such as GPUs this behavior leads to
the thread or branc ...