C++ library for GPU accelerated linear algebra

Bandicoot employs a delayed evaluation approach to optimise linear algebra expressions at compile time. Where applicable, the order of operations is optimised, redundant or unnecessary operations are removed entirely, and inefficiently-expressed operations are rewritten efficiently. Delayed evaluation and optimisation are achieved through recursive templates and template meta-programming.

While chained operations such as addition, subtraction and multiplication (matrix and element-wise) are the primary targets for speed-up opportunities, other operations, such as manipulation of submatrices, can also be optimised.

See also the Questions page for more information about speed enhancements.

To show the speedups that can be obtained with Bandicoot, below are two sets of timing comparisons.
- The first shows the potential of the use of a GPU, comparing simple linear algebra workloads against Armadillo. This comparison can be used to get an idea of how Bandicoot could accelerate a CPU-only Armadillo program.
- The second shows comparisons of GPU-enabled machine learning algorithms with Bandicoot against popular machine learning libraries such as PyTorch and TensorFlow. This comparison can give an idea of how the optimized, low-overhead implementations in Bandicoot can provide acceleration.

The first set of timing comparisons shows the speedups that Bandicoot can provide via the use of the GPU over the CPU-only Armadillo. The comparisons were done using a machine with the following specifications:
- Intel Core i9-10920X (3.5 GHz, 12 cores, 19.25MB cache)
- NVIDIA RTX2080ti (1350 MHz, 4352 CUDA cores, 11GB RAM)
- 128GB system RAM
- NVIDIA driver version 525.105.17
- Linux kernel 6.1.0
- GCC 12.2.0

Comparisons were done both with 32-bit floating-point precision (i.e. fmat/fvec) and 64-bit floating-point precision (i.e. mat/vec)

Note: GPUs (especially consumer GPUs) are far more efficient when using 32-bit floating-point precision; not all GPUs have support for 64-bit floating-point precision

Task 1: accu() (accumulate elements of vector)

Code extract:

// N is specified externally
// when using Armadillo, 'using namespace arma' is used
// when using Bandicoot, 'using namespace coot' is used
fvec f(N);
f.randu();
coot_synchronise(); // applicable only to Bandicoot

wall_clock c;

c.tic();
float result = accu(c);
coot_synchronise(); // applicable only to Bandicoot
const double time = c.toc();

Bandicoot provides 2+ orders of magnitude speedup for sufficiently large vectors
In this example, float and double performance are the same for Bandicoot, but that is not always true (see later benchmarks)

Task 2: scalar vector multiply-add (axpy)

Code extract:

// N is specified externally
// when using Armadillo, 'using namespace arma' is used
// when using Bandicoot, 'using namespace coot' is used
fvec A(N, fill::randu);
fvec B(N, fill::randu);
coot_synchronise(); // applicable only to Bandicoot

wall_clock c;

c.tic();
B += 3 * A;
coot_synchronise(); // applicable only to Bandicoot
const double time = c.toc();

Vectorisable operations such as axpy show significant speedups once the vector is reasonably sized
Similar speedup patterns should be observed for any elementwise operation

Task 3: matrix multiplication

Code extract:

// N is specified externally
// when using Armadillo, 'using namespace arma' is used
// when using Bandicoot, 'using namespace coot' is used
fmat A(N, N, fill::randu);
fmat B(N, N, fill::randu);
coot_synchronise(); // applicable only to Bandicoot

wall_clock c;

c.tic();
fmat C = A * B;
coot_synchronise(); // applicable only to Bandicoot
const double time = c.toc();

Small matrix sizes are not able to exploit the full parallelism of the GPU and do not show speedups
GPUs can show up to order-of-magnitude performance gains for 32-bit precision (float)
For matrix multiplication, GPUs may not show speedup for 64-bit precision (double)

Task 4: LU decomposition

Code extract:

// N is specified externally
// when using Armadillo, 'using namespace arma' is used
// when using Bandicoot, 'using namespace coot' is used
fmat A(N, N, fill::randu);
coot_synchronise(); // applicable only to Bandicoot

wall_clock c;

c.tic();
fmat L, U;
lu(L, U, A);
coot_synchronise(); // applicable only to Bandicoot
const double time = c.toc();

Decompositions may be more limited in the speedup they show due to the more complex nature of the operation
Speedups of up to 10x for float matrices and 5x for double matrices can still be seen for sufficiently large matrix sizes

The second set of timing comparisons shows benchmarks for GPU-enabled machine learning (logistic regression) with Bandicoot and popular machine learning libraries such as PyTorch and TensorFlow.

We train a logistic regression model on a random dataset using simple batch stochastic gradient descent (SGD) for 50 epochs with a constant learning rate. For Bandicoot and Armadillo, we use the SGD implementation in ensmallen.

To match standard practices in the machine learning literature, we use 64-bit floating-point precision matrices (i.e. double), instead of float. Using float would likely result in additional speedup.

System specifications are the same as for the previous benchmarks

Bandicoot provides 2x speedup over Armadillo and over 10x speedup over PyTorch and TensorFlow for large batch sizes (here 1024)
Smaller batch sizes do not provide the same speedup

PyTorch and TensorFlow run out of GPU memory for the larger 10k-dimensional dataset
Bandicoot can provide additional speedup (up to 10x) over Armadillo in more dimensions