We will show how Julia allows us to implement spatial branch-and-bound-type methods using interval arithmetic in parallel on GPUs, in a relatively painless way.

These methods use repeated bisection in a divide-and-conquer style to perform exhaustive search over a box in d dimensions (for small d), in order to find all roots of a function f, find all global optima of f, or to bound feasible sets of constraints such as {x: f(x) ≤ 0}.

Using a vectorised implementation, we will show firstly how to define a vector of interval objects (or similar user-defined types) on the GPU, which most other systems cannot do. Then we need a way to run interval arithmetic methods, as defined in the IntervalArithmetic.jl package, on the GPU. CUDA.jl's broadcasting abstraction

We will illustrate with the Griewank function, a standard test case for nonlinear optimization. We have developed a generic implementation of a vectorised branch-and-prune algorithm, which can run on both the CPU and GPU with no code changes whatsoever. A key difficulty that we faced, but were able to solve, was how to eliminate the uninteresting boxes in parallel.

We obtain a 2-orders-of-magnitude speed-up over a single CPU core, and we expect that performance will be improved even more by reducing array allocations.