Calculating a million stationary points in a second on the GPU

07/29/2021, 1:10 PM1:20 PM UTC
Blue

Abstract:

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.

Description:

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.

Platinum sponsors

Julia Computing

Gold sponsors

Relational AI

Silver sponsors

Invenia LabsConningPumas AIQuEra Computing Inc.King Abdullah University of Science and TechnologyDataChef.coJeffrey Sarnoff

Media partners

Packt Publication

Fiscal Sponsor

NumFOCUS