Parallelism

GPU offload

A par for, par [...] or par reduction can run on an NVIDIA GPU (through CUDA) or an Apple GPU (through Metal) with no annotation and no change in meaning. The compiler decides which constructs can run there, the runtime decides for each launch whether that is faster, and either way the results are the same bits as on the CPU. A check that fails on the device panics exactly as it would on the CPU.

What you need

NVIDIA on Windows or Linux: the normal display driver. The runtime loads nvcuda.dll or libcuda.so.1 when it first needs it. No CUDA toolkit.
Apple silicon (M1 and later) on macOS: nothing. Metal is reached through the Objective-C runtime.
Nothing at build time. The program carries its kernels (PTX for CUDA, Metal Shading Language on macOS), and the driver compiles them for the device it finds. Without a driver or a device, every construct runs on the CPU, as before.

AMD and Intel GPUs aren’t supported yet; see the roadmap.

A first look

The Collatz example runs one par max over ten million numbers. Repeat it four times and ask the runtime what it did:

fn collatz_len(n: int) -> int:
    var x = n
    var steps = 0
    while x != 1:
        x = x / 2 if x % 2 == 0 else 3 * x + 1
        steps += 1
    return steps

fn main():
    let n = 10_000_000
    for round in 0..4:
        let t0 = clock()
        let longest = par max(collatz_len(i) for i in 1..=n)
        let ms = (clock() - t0) * 1000.0
        print(f"round {round}: longest chain {longest} steps, {ms:.1f} ms")

brine build gpu_demo.br --release -o gpu_demo
BRINE_GPU_LOG=1 ./gpu_demo

On a Ryzen 9 9950X3D with an RTX 4090 (stderr first, then stdout):

brine gpu: gpu_demo.br:13:23 par reduction n=10000000 -> cpu 68.040 ms (starting the GPU)
brine gpu: NVIDIA GeForce RTX 4090 ready in 105 ms
brine gpu: gpu_demo.br:13:23 par reduction n=10000000 -> cpu 71.043 ms (starting the GPU)
brine gpu: gpu_demo.br:13:23 par reduction n=10000000 -> gpu 5.323 ms (kernels 4.106 ms, copies 1.217 ms, 0.0 MB; cpu estimate 69.542 ms)
brine gpu: gpu_demo.br:13:23 par reduction n=10000000 -> gpu 3.996 ms (kernels 3.968 ms, copies 0.028 ms, 0.0 MB; cpu estimate 69.542 ms)
round 0: longest chain 685 steps, 68.7 ms
round 1: longest chain 685 steps, 71.4 ms
round 2: longest chain 685 steps, 5.9 ms
round 3: longest chain 685 steps, 4.6 ms

The first round would be faster on the GPU, but not by enough to wait for the device to start, so the runtime starts it in the background and runs the round on all 32 threads. The second round starts before the device is quite ready. From the third round on, the reduction runs on the GPU, about 15 times faster. Every round prints the same answer, and BRINE_GPU=off prints it too, in about 63 ms per round.

Which constructs can run on a GPU

The compiler decides this, when it builds the program:

par for, par [...] and par reductions (sum, product, min, max, any, all, with or without a filter) can.
par(a, b) forks don’t, nor do constructs nested inside another par, nor a construct whose body contains another par construct.

A construct can run on a GPU when its body, and every function it calls, uses only:

int, float and the other integer and float types up to 64 bits, and bool: arithmetic, comparisons, conversions, shifts;
branches, loops, match on numbers and enums without payloads, local variables, structs and tuples;
reads of captured scalars and of arrays, including arrays of arrays and arrays of structs;
writes to out[i] (in par for);
sqrt, abs, floor, ceil, round, min and max;
calls to functions that follow the same rules (recursion is fine on CUDA);
checks that can fail: overflow, bounds, division by zero, assert, panic, contracts.

Any of these keeps it on the CPU:

anything that allocates: strings, f-strings, maps, enums with payloads, new arrays (a body that returns an array or a string, for example);
print, eprint, file and process I/O, world;
calling a function value;
sin, cos, tan, exp, log, pow and the like, and float %: their last bit depends on the C library, and the GPU’s versions round differently;
128-bit integers;
on Apple GPUs, float (f64), because they have none, recursion, because Metal has none, and subnormal f32 constants. Use f32 for Metal.

BRINE_GPU_LOG=1 says why each construct that can’t run on a GPU stayed on the CPU. These are real lines from a test program:

brine gpu: elig.br:13:13 par reduction n=1000000 -> cpu 0.329 ms (not GPU-eligible: uses sin)
brine gpu: elig.br:14:13 par map n=1000000 -> cpu 11.836 ms (not GPU-eligible: its context holds strings, maps or enums with payloads)
brine gpu: elig.br:26:14 par reduction n=1000000 -> cpu 0.509 ms (not GPU-eligible: uses pow)
brine gpu: pr.br:8:9 par for n=100000 -> cpu 0.371 ms (not GPU-eligible: calls brine_sb_init)
brine gpu: elig.br:21:13 par map n=10000 -> cpu 6.136 ms (not GPU-eligible: calls brine_par_reduce)

The last two name runtime functions: brine_sb_init builds a string (here, for print), and brine_par_reduce is a nested par reduction. Reading a map in the body gives the “strings, maps or enums” reason too.

When the runtime uses it

For each launch of an eligible construct, the runtime compares the two sides:

Too small or nested: constructs with fewer than 4096 elements, and constructs inside another par, run on the CPU.
The CPU’s time is estimated by running the first elements on one thread for about 100 µs, then measured on every later launch.
The device’s time is guessed from that (f64 code counts as much slower on most cards), then measured after its first run. To it the runtime adds the copies, at the bandwidth it has measured, and the cost of each launch.
It uses the device when that is at least 25% faster (the device’s time, copies included, is under 75% of the CPU’s).
Warm-up. Getting a device ready takes 0.1 to 0.7 s (about 0.1 s on Windows, 0.4 s on Linux). If the device isn’t ready, its start-up time counts against it. A construct that would gain, but not enough to cover the wait, starts the device in the background and runs on the CPU until it is ready. That’s what happened to rounds 0 and 1 above.

The thread count matters too. Run the Collatz program once with one thread and the CPU estimate becomes 1.2 s, so waiting 91 ms for the device pays at once:

brine gpu: NVIDIA GeForce RTX 4090 ready in 91 ms
brine gpu: collatz.br:12:19 par reduction n=10000000 -> gpu 9.359 ms (kernels 8.440 ms, copies 0.919 ms, 0.0 MB; cpu estimate 1221.429 ms)
longest chain below 10000000: 685 steps (101 ms)

A short program that runs a construct only once may end before the device is ready, and then everything runs on the CPU. That is the right choice for it.

Same results

The kernels use the CPU’s semantics, not the device’s defaults:

every float operation rounds to nearest even, and none is fused into a multiply-add (FMA);
/ and sqrt are exactly rounded;
subnormal numbers are kept (on NVIDIA);
integer division, %, conversions and shifts follow Brine’s rules, not the device’s.

A reduction runs the same leaves and tree as on the CPU: each launch reduces an aligned subtree of up to 2²⁴ leaves, and the CPU combines the subtrees’ results in the same tree. So par sum of floats gives the same bits on the GPU as on one CPU thread.

Checks. Overflow, bounds, division by zero, assert and contract checks set a flag on the device instead of panicking. When the flag is set, the device’s results are dropped, and the construct runs again on the CPU, which panics with the usual message:

fn main():
    let n = 1_000_000
    var xs = [1] * n
    xs[777_777] = 9_223_372_036_854_775_807
    var out = [0] * n
    par for i in 0..n:
        out[i] = xs[i] * 2
    print(out[0])

brine gpu: NVIDIA GeForce RTX 4090 ready in 96 ms
brine gpu: chk.br:6:9 par for n=1000000: a check failed on the GPU, running it on the CPU

panic: integer overflow in multiplication
  --> chk.br:7:18

Rerunning is safe: results are copied back only after a launch succeeded, and a body can only write out[i], so the CPU starts from the same state.

Subnormals on Apple GPUs. Apple GPUs flush subnormal f32 values to zero. On Metal, a subnormal operand or result sets the flag too, and the construct reruns on the CPU, so you still get the CPU’s bits.

Copies

Every launch copies the arrays the body reads to the device, and the arrays it writes back. Arrays are values, so nothing else can see them in between. Keeping arrays on the device from one construct to the next is future work, so a construct that does little work per byte (a plain sum of a big array, a light map) stays on the CPU, where memory is faster than the PCIe bus. The MB in the log is what a launch copied.

BRINE_GPU and BRINE_GPU_LOG

Variable	Value	Effect
`BRINE_GPU`	`auto` (default)	the runtime picks, as above
	`on` (or `1`)	use the GPU for every construct that can run there, at any size, waiting for the device if needed
	`off` (or `0`)	never use a GPU
`BRINE_GPU_LOG`	`1`	print to stderr where each construct ran, how long it took, and why

The program reads them itself, so they work with brine run and with a built binary. Each log line names the construct by file, line and column, its kind and element count, then the side it ran on:

brine gpu: <file>:<line>:<col> <par for | par map | par reduction> n=<elements> -> gpu <total> ms (kernel(s) <ms>, copies <ms>, <MB> MB; cpu estimate <ms>)
brine gpu: <file>:<line>:<col> <kind> n=<elements> -> cpu <ms> ms (<reason>)

Reasons for the CPU are faster on the CPU, starting the GPU, small, BRINE_GPU=off, a check failed on the GPU, too big for the GPU's memory, the GPU is busy (another thread is using it), or not GPU-eligible: .... cpu estimate is 0.000 with BRINE_GPU=on, which doesn’t measure the CPU.

See environment variables for the others, including BRINE_DUMP_PTX=file, which writes the kernel module when building.

Benchmarks

From bench/gpu in the Brine repository: Windows 11, Ryzen 9 9950X3D (16 cores, 32 threads), RTX 4090, Brine 0.3.0 plus the GPU work, --release. Times in ms for the construct alone; cold is the first run in the process (for the GPU, including getting the device ready), warm the best later run. The GPU was shared with a running game, so GPU times varied by up to 1.5x.

Benchmark	CPU warm	GPU cold	GPU warm	auto warm	auto picks
`vecmap` f64: 16M elements, 16 multiply-adds and divisions each	6.7	122-146	29-36	6.8	CPU
`nbody` f64: 16384 bodies, all pairs	41-44	139-147	37-50	42-45	CPU
`nbody` f32	35-40	8-10	4.5	4.5-7.5	GPU
`mandelbrot` f64: 4096 x 4096, up to 512 iterations	107-117	149-170	46-70	48-72	CPU, then GPU
sum of 64M `float`s	7.5-8.4	154-171	43-47	8	CPU
sum of 64M `f32`s	3.9	23-28	21-26	4.1	CPU
sum of a computed series, 256M terms	14-16	6.4-12	5.8-10	15	CPU (ends before the device is ready)

Re-run for this page with Brine 0.4.0 on the same machine, the n-body step (bench/gpu/nbody.br) printed the same checksum in all three modes:

`BRINE_GPU`	f64 cold	f64 warm	f32 cold	f32 warm
`off`	40.2	39.9	33.9	33.3
`on`	149.0	30.8	4.6	3.7
`auto`	42.6	40.4	34.5	3.7

And examples/find_signal.br (32 matched-filter searches over a million f32 samples) took 933 ms with BRINE_GPU=off, 233 ms on auto and 173 ms with on.

On an M1 Mac mini (8-core GPU), the f32 n-body step took 58 ms on the CPU and 63 ms warm on the GPU, so auto kept it on the CPU. Larger Apple GPUs (M1 Pro and up) should move it over.

What the numbers say:

Work per byte decides. The f32 n-body step copies 0.5 MB and does 268 million interactions: 8x faster on the GPU. A sum or a light map of a big array is bound by the copy over PCIe (8-10 GB/s) while the CPU reads memory at 60+ GB/s, so it stays on the CPU.
f64 is slow on GeForce cards (1/64 of the f32 rate). Mandelbrot in f64 still gains 1.6-2.3x; the n-body step in f64 runs at about the CPU’s speed.
Exact rounding costs a little. Correctly rounded / and sqrt and no FMA are slower than the device’s defaults. That is the price of the same bits.

Writing GPU-friendly code

Do a lot per element. Loops inside the body (an inner for over a row, an iteration count) are where a GPU wins. A body that reads one number and adds one is copy-bound.
Prefer f32 when its precision is enough. It is many times faster on GeForce cards, and it is the only float type Apple GPUs have.
Keep the body allocation-free. Return numbers, tuples or structs, not arrays or strings. Pass in the arrays you read; don’t build them in the body.
Keep the transcendental math out of the hot body. sin, exp, log and pow keep a construct on the CPU. Compute a table before the construct, or rewrite with sqrt and arithmetic where you can.
Don’t print in the body. Collect results and print after.
Reuse a construct. A construct that runs many times (in a time step loop, or once per input) gets measured, and from then on runs on the faster side. The device’s start-up is paid once per process.
Prove the indexes. Checks the prover removes cost nothing on either side. examples/find_signal.br states its ranges with requires, and no runtime check is left in its search loop. See runtime checks.
Look. BRINE_GPU_LOG=1 tells you where each construct ran and why; BRINE_GPU=on shows what the GPU would do.

Roadmap

Arrays kept on the device between constructs, so a sequence of par constructs over the same data copies it once.
par(...) forks and nested constructs on the GPU.
AMD and Intel GPUs through Vulkan compute with SPIR-V kernels (the driver loaded at run time, as CUDA is), with exactly rounded / and sqrt, a capability check for subnormals and f64, and a self-test at start-up that turns the GPU off if its results differ from the CPU’s. This waits for real devices to test on. It includes the AMD and Intel GPUs in Intel Macs; Metal is used only on Apple GPUs for now.