Calculating a million stationary points in a second on the GPU
2021-07-29, 13:10–13:20 (UTC), Blue

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. As a test case, we calculate and verify existence and uniqueness of over one million stationary points of the transcendental Griewank function of two variables in one second on a recent GPU. We are not aware of any other system that is able to do this.


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.

Professor of Computational Science at the Universidad Nacional Autónoma de México and visiting professor at MIT.

Interested in computational science, interval arithmetic, and numeric-symbolic computing.

Author of the JuliaIntervals suite of packages for interval arithmetic, and various tutorials on Julia.

This speaker also appears in: