Parallelism: par constructs, GPUs and the world module # Deadlock freedom > How Brine proves at compile time that every rank of a world program makes the same communication calls in the same order, the uniform and varying values behind it, errors E0510, E0511 and E0512, and what the check allows. A `world` program can’t deadlock. Every `world` call is collective, so a program could only hang if some ranks skipped a call that others made. The compiler rules that out: a communication call may not depend on anything that can differ between ranks, such as `world.rank()`, and the arguments that steer communication must be the same on every rank. ## Why collectives are enough [Section titled “Why collectives are enough”](#why-collectives-are-enough) In MPI-style code, deadlocks come from unmatched messages: rank 0 waits in `recv` for a message rank 1 never sends, or both ranks wait for each other. Brine has no `send` and `recv` ([E0512](/reference/errors/#e0512)). Every call in the [`world` API](/parallelism/world/#the-api) involves every rank, and point-to-point messages are written with `shift` and `exchange`, which are collectives too. So if every rank makes the same sequence of `world` calls, every receive has a matching send: all ranks run the same program, and the static types make the messages agree. The compiler’s job is to make sure the sequence can’t differ. ## Uniform and varying values [Section titled “Uniform and varying values”](#uniform-and-varying-values) The check, in `compiler/uniform.br`, classifies every value: * **Uniform:** the same on every rank. Constants, `world.size()`, `args()`, `os.name()`, `os.arch()`, and the results of `world.sum`, `min`, `max`, `broadcast` and `gather_all` (every rank gets the same result). * **Varying:** may differ between ranks. The sources are: * `world.rank()`; * the results of `world.shift` and `world.exchange` (each rank receives something different); * `clock()`; * files and processes: `read_file`, `file_exists`, `getenv`, `run`; * the `os` functions, except `os.name()` and `os.arch()`; * C functions declared with `extern fn`. Anything computed from a varying value is varying, and so is a variable assigned under a varying condition (`if world.rank() == 1: root = 1` makes `root` varying). Then two rules: 1. **A communication call can’t be controlled by a varying value** ([E0510](/reference/errors/#e0510)): not by an `if`, `while`, `for` or `match`, not by `and`/`or` or a conditional expression, and not by an early `return`, `break` or `continue` before it. 2. **Arguments that steer communication must be uniform** ([E0511](/reference/errors/#e0511)): the root of `world.broadcast`, the distance of `world.shift`, and any parameter that decides whether a function communicates. The *values* sent can vary freely: `world.sum(local)` with a different `local` on each rank is the point of the call. ## Communication under a rank-dependent branch [Section titled “Communication under a rank-dependent branch”](#communication-under-a-rank-dependent-branch) branch.br ```brine fn main(): if world.rank() == 0: let total = world.sum(1) print(total) ``` ```text error[E0510]: some ranks might not reach this communication --> branch.br:3:21 | 3 | let total = world.sum(1) | ^^^^^^^^^^^^ calls `world.sum` 2 | if world.rank() == 0: | ----------------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` Rank 0 would wait in `world.sum` for ranks that never call it. Compute the rank-specific part first, then communicate on every rank, and branch on the rank only for what doesn’t communicate: ```brine fn main(): let mine = 1 if world.rank() == 0 else 0 let total = world.sum(mine) if world.rank() == 0: print(total) ``` brine run --ranks 3 ```text 1 ``` ## Loops whose length varies [Section titled “Loops whose length varies”](#loops-whose-length-varies) A loop whose condition or range depends on the rank runs a different number of times on each rank: loop.br ```brine fn main(): let rank = world.rank() var steps = 0 while steps < rank: world.barrier() steps += 1 ``` ```text error[E0510]: some ranks might not reach this communication --> loop.br:5:9 | 5 | world.barrier() | ^^^^^^^^^^^^^^^ calls `world.barrier` 4 | while steps < rank: | ------------ this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` The same goes for `for i in 0..n` with a varying `n`, and for a `continue` or `break` under a varying condition before the call. ## Short-circuits and other sources [Section titled “Short-circuits and other sources”](#short-circuits-and-other-sources) `and`, `or` and conditional expressions decide whether their right side runs, so they count as branches. `clock()` differs between processes: timer.br ```brine fn main(): let t = clock() if t > 1.0 and world.sum(1) > 0: print("ok") ``` ```text error[E0510]: some ranks might not reach this communication --> timer.br:3:20 | 3 | if t > 1.0 and world.sum(1) > 0: | ^^^^^^^^^^^^ calls `world.sum` | ------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` ## Branching on received values [Section titled “Branching on received values”](#branching-on-received-values) `shift` and `exchange` give each rank a different value, so their results are varying too: received.br ```brine fn main(): let got = world.shift(world.rank(), 1) if got == 0: world.barrier() ``` ```text error[E0510]: some ranks might not reach this communication --> received.br:4:9 | 4 | world.barrier() | ^^^^^^^^^^^^^^^ calls `world.barrier` 3 | if got == 0: | -------- this may differ between ranks | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` To decide together, turn the local fact into a uniform one with a reduction. Every rank then gets the same answer and takes the same branch: ```brine fn main(): let got = world.shift(world.rank(), 1) # ask every rank, and get the same answer everywhere let someone_got_zero = world.max(1 if got == 0 else 0) == 1 if someone_got_zero: world.barrier() if world.rank() == 0: print(f"rank 0 got {got}, someone got 0: {someone_got_zero}") ``` brine run --ranks 3 ```text rank 0 got 2, someone got 0: true ``` ## What’s allowed [Section titled “What’s allowed”](#whats-allowed) Results of `world.sum`, `min`, `max`, `broadcast` and `gather_all` are uniform, so conditions built from them are fine. That covers the usual iterative patterns: loop until the largest error on any rank is small, let rank 0 choose a value and broadcast it, take turns as the root: allowed.br ```brine fn main(): let rank = world.rank() let size = world.size() # every rank keeps going until the largest error is small var x = float(rank + 1) * 100.0 var rounds = 0 while world.max(abs(x - 1.0)) > 0.001: x = (x + 1.0) / 2.0 rounds += 1 # a value chosen on rank 0, then the same everywhere let seed = world.broadcast(0, rank * 7 + 3) if seed > 0: world.barrier() # each rank takes a turn as the root: `r` is uniform var total = 0 for r in 0..size: total += world.broadcast(r, rank * 10) if rank == 0: print(f"{size} ranks: {rounds} rounds, seed {seed}, total {total}") ``` brine run allowed.br --ranks 4 ```text 4 ranks: 19 rounds, seed 3, total 60 ``` Branching on the rank is fine when no communication depends on it: printing on rank 0, doing rank-specific work before a collective, or returning early *after* the last call. ## Functions that communicate [Section titled “Functions that communicate”](#functions-that-communicate) The check is modular. For every function it records a summary: whether the function communicates, and which of its parameters must be uniform because the function branches on them around a communication. Call sites are checked against the summary, so the rules hold across calls, modules and recursion. Calling a communicating function under a varying condition, here an early `return` before it, is E0510, and the error shows where the function communicates: early.br ```brine fn report(x: int): let total = world.sum(x) print(total) fn main(): if world.rank() == 0: return report(1) ``` ```text error[E0510]: some ranks might not reach this communication --> early.br:8:5 | 8 | report(1) | ^^^^^^^^^ calls `report`, which communicates with other ranks 6 | if world.rank() == 0: | ----------------- this may differ between ranks 2 | let total = world.sum(x) | ------------ communicates here | = note: every rank must make the same `world` calls in the same order, otherwise the program could hang = help: move the call out of the rank-dependent branch or loop; compute rank-specific values first, then communicate on every rank = run `brine explain E0510` for more about this error error: could not compile due to 1 error ``` A parameter that controls communication inside the function must get a uniform argument: rounds.br ```brine fn rounds(n: int) -> int: var total = 0 for i in 0..n: total += world.sum(i) return total fn main(): print(rounds(world.rank())) ``` ```text error[E0511]: argument `n` of `rounds` must be the same on every rank --> rounds.br:8:18 | 8 | print(rounds(world.rank())) | ^^^^^^^^^^^^ might differ between ranks | = help: compute it from values that are the same everywhere, e.g. `world.size()`, constants, or the result of `world.broadcast` = run `brine explain E0511` for more about this error error: could not compile due to 1 error ``` Make the argument uniform first, for example with `world.broadcast`: ```brine fn rounds(n: int) -> int: var total = 0 for i in 0..n: total += world.sum(i) return total fn main(): let n = world.broadcast(0, world.rank() + 3) let r = rounds(n) if world.rank() == 0: print(f"{world.size()} ranks, {n} rounds: {r}") ``` brine run --ranks 3 ```text 3 ranks, 3 rounds: 9 ``` A parameter that is only *sent* may vary. Here `v` differs on every rank and `levels` is uniform, and the recursion is fine: ```brine fn tree_sum(v: int, levels: int) -> int: if levels == 0: return v return tree_sum(world.sum(v), levels - 1) fn main(): let r = tree_sum(world.rank(), 3) if world.rank() == 0: print(r) ``` brine run --ranks 4 ```text 96 ``` ## Roots and distances [Section titled “Roots and distances”](#roots-and-distances) `world.broadcast(root, v)` needs every rank to agree on the root, and `world.shift(v, by)` on the distance: root.br ```brine fn main(): let root = world.rank() let v = world.broadcast(root, 42) print(v) ``` ```text error[E0511]: the root rank of `world.broadcast` must be the same on every rank --> root.br:3:29 | 3 | let v = world.broadcast(root, 42) | ^^^^ might differ between ranks 2 | let root = world.rank() | ------------ because this depends on which rank is running | = help: compute it from values that are the same everywhere, e.g. `world.size()`, constants, or the result of `world.broadcast` = run `brine explain E0511` for more about this error error: could not compile due to 1 error ``` ## No send or recv [Section titled “No send or recv”](#no-send-or-recv) recv.br ```brine fn main(): let x = world.recv(0) ``` ```text error[E0512]: `world.recv` doesn't exist: unmatched sends and receives can deadlock --> recv.br:2:19 | 2 | let x = world.recv(0) | ^^^^ not available | = note: run `brine explain E0512` for how to express point-to-point patterns = help: every rank takes part in each communication: `world.shift(v, 1)` sends `v` to the next rank and returns the value from the previous one; `world.exchange(xs)` sends `xs[j]` to rank `j` = run `brine explain E0512` for more about this error error: could not compile due to 1 error ``` “Rank 0 sends a message to rank 1” is an `exchange` in which every other slot is empty. Filling the outbox under a rank-dependent `if` is fine, since the `if` doesn’t communicate: ```brine fn main(): var outbox = [""] * world.size() if world.rank() == 0 and world.size() > 1: outbox[1] = "hello" let inbox = world.exchange(outbox) if world.rank() == 1: print(f"rank 1 got {inbox[0]}") ``` brine run --ranks 4 ```text rank 1 got hello ``` A ring (each rank to its neighbour) is `world.shift(v, 1)`; a halo exchange in both directions is `shift(v, 1)` and `shift(v, -1)`. ## Communication inside par [Section titled “Communication inside par”](#communication-inside-par) `world` calls can’t appear in a `par` body ([E0503](/reference/errors/#e0503)): iterations run in no fixed order, so the ranks’ calls couldn’t line up. inpar.br ```brine fn main(): let total = par sum(world.sum(i) for i in 0..10) print(total) ``` ```text error[E0503]: `world` operations can't be used inside a `par` body --> inpar.br:2:25 | 2 | let total = par sum(world.sum(i) for i in 0..10) | ^^^^^^^^^^^^ not allowed here | = help: communicate before or after the parallel section = run `brine explain E0503` for more about this error error: could not compile due to 1 error ``` Reduce locally with `par`, then communicate once: `world.sum(par sum(f(i) for i in lo..hi))`. See [combining world with par](/parallelism/world/#combining-world-with-par). ## What the check doesn’t cover [Section titled “What the check doesn’t cover”](#what-the-check-doesnt-cover) The compiler proves that ranks can’t disagree about which calls to make. It can’t make a rank reach the next call: * **A rank that crashes** never sends its next message. The others stop with an error naming it instead of waiting forever (`panic (rank 0): rank 1 exited before sending the expected message`); see [when a rank fails](/parallelism/world/#when-a-rank-fails). * **A rank that loops forever** before a collective keeps the others waiting, as a slow rank would. * **Message sizes** can differ: `gather_all` of a string or an array works with a different length on each rank. `exchange` needs exactly `world.size()` elements on every rank, and panics otherwise. ## Rules [Section titled “Rules”](#rules) * Every `world` call except `rank()` and `size()` is collective. * No communication under a condition, loop, short-circuit or early exit that depends on a varying value ([E0510](/reference/errors/#e0510)). * `broadcast` roots, `shift` distances and parameters that steer communication must be uniform ([E0511](/reference/errors/#e0511)). * No `send` or `recv` ([E0512](/reference/errors/#e0512)); use `shift` and `exchange`. * No communication in `par` ([E0503](/reference/errors/#e0503)). * Make a local fact uniform with `world.sum`, `min`, `max`, `broadcast` or `gather_all`, then branch on it. # Deterministic reductions > The exact order in which par sum, product, min, max, any and all combine their elements, why it gives the same bits on any thread count or GPU, how integer overflow follows it, and how it differs from a sequential sum. A `par` reduction combines its elements in one fixed order that depends only on how many elements there are, never on the number of threads or the device. So a float `par sum` prints the same bits on 1 thread, 32 threads or a GPU. The order is a tree, not left to right, so it can differ from a sequential `sum` in the last bits, usually by being closer to the exact result. ## The order [Section titled “The order”](#the-order) For `par sum`, `par product`, `par min`, `par max`, `par any` and `par all`: 1. **Leaves.** The elements are split into leaves of 16 consecutive elements: elements 0-15 are leaf 0, 16-31 are leaf 1, and so on. The last leaf may be shorter. 2. **Inside a leaf, left to right.** Each leaf is folded from its first element to its last, starting from the reducer’s start value (`0` for `sum`, `1` for `product`): `((((0 + x0) + x1) + x2) + ... + x15)`. 3. **Between leaves, a balanced tree.** The leaf results are combined level by level: leaves 0 and 1, 2 and 3, 4 and 5, …; then those results in pairs; and so on until one value is left. A node without a partner at the end of a level moves up a level unchanged. 4. **Filters.** With `if`, elements that don’t pass are skipped inside their leaf. A leaf whose elements were all filtered out keeps its place in the tree but has no value, so its partner moves up unchanged. Every step depends only on positions, so the result depends only on the elements and their count. ## A picture [Section titled “A picture”](#a-picture) `par sum(x for x in xs)` with 80 elements makes 5 leaves: ```text elements 0..15 16..31 32..47 48..63 64..79 | | | | | leaves L0 L1 L2 L3 L4 each folded left to right \ / \ / | level 1 (L0 + L1) (L2 + L3) L4 L4 has no partner: moves up \ / | level 2 ((L0 + L1) + (L2 + L3)) L4 \ / level 3 (((L0 + L1) + (L2 + L3)) + L4) the result ``` A sequential `sum(x for x in xs)` is one long left fold instead: `(((0 + x0) + x1) + ...) + x79`. ## Why a fixed order [Section titled “Why a fixed order”](#why-a-fixed-order) Floating-point addition isn’t associative: `(a + b) + c` and `a + (b + c)` can round differently. A reduction that let each thread add up its own share and then combined the shares as they finished would print different bits depending on the thread count, the machine, and timing. Tests that compare output would fail for no reason, and a bug would be hard to tell from noise. Brine fixes the tree instead. Threads (and GPU blocks) only decide *who* computes each subtree, never *which* elements go in it, so: * the result is the same on 1 thread, 32 threads, a 128-core server or a GPU; * the result is the same from run to run; * dev, `--release` and native and C backends agree. The tree also loses less precision. In a left-to-right sum of `n` terms the rounding errors can grow with `n`; in a balanced tree they grow with the height, about `log2(n)`. Adding small terms to a large running total, the usual source of lost bits, mostly turns into adding numbers of similar size. ## Same bits everywhere: a demonstration [Section titled “Same bits everywhere: a demonstration”](#same-bits-everywhere-a-demonstration) This program adds up the first ten million terms of the harmonic series (1 + 1/2 + 1/3 + …), once with `par sum` and once with a sequential `sum`: harmonic.br ```brine fn main(): let n = 10_000_000 let tree = par sum(1.0 / float(i) for i in 1..=n) let left = sum(1.0 / float(i) for i in 1..=n) print(f"par sum: {tree}") print(f"sum: {left}") ``` Built with `--release` and run on a Ryzen 9 9950X3D and an RTX 4090 with different thread counts, with the GPU off and on: ```sh brine build harmonic.br --release -o harmonic BRINE_THREADS=1 BRINE_GPU=off ./harmonic BRINE_THREADS=2 BRINE_GPU=off ./harmonic BRINE_THREADS=8 BRINE_GPU=off ./harmonic BRINE_THREADS=32 BRINE_GPU=off ./harmonic BRINE_GPU=on BRINE_GPU_LOG=1 ./harmonic ``` Every run prints the same two lines: Output (all five runs) ```text par sum: 16.69531136585985 sum: 16.695311365857272 ``` The GPU run also logs where the reduction ran: stderr, BRINE_GPU=on BRINE_GPU_LOG=1 ```text brine gpu: NVIDIA GeForce RTX 4090 ready in 88 ms brine gpu: harmonic.br:3:16 par reduction n=10000000 -> gpu 1.252 ms (kernels 0.321 ms, copies 0.930 ms, 0.0 MB; cpu estimate 0.000 ms) ``` The exact sum is 16.6953113658598518153991… The `par sum` result is the closest `float` to it (it is off by 7.2 × 10⁻¹⁶, a fifth of a unit in the last place). The sequential sum is off by 2.6 × 10⁻¹², about 730 units in the last place, because by the end it adds terms near 10⁻⁷ to a total near 16. The two lines differ, and they always will: they’re different orders. What never changes is each line. ## Integers and overflow [Section titled “Integers and overflow”](#integers-and-overflow) Integer `par sum` and `par product` check every addition and multiplication, like all integer arithmetic in Brine, and the checks happen in the tree order. Whether a reduction overflows is decided by the partial results of *that* order, so it is the same on every machine, but it can differ from a sequential `sum`. The tree can overflow where the left fold doesn’t. Here leaf 1 holds two copies of the largest `int`, and folding that leaf overflows, while the left fold’s running total never leaves the range: ov.br ```brine fn main(): let big = 9_223_372_036_854_775_807 var xs = [0] * 32 xs[0] = -big xs[16] = big xs[17] = big print(sum(x for x in xs)) print(par sum(x for x in xs)) ``` Output ```text 9223372036854775807 panic: integer overflow in addition --> ov.br:8:11 ``` And the other way round: here the left fold passes through `big + 5`, while the tree combines `big - 5` with `10 - 10` and never leaves the range: ov2.br ```brine fn main(): let big = 9_223_372_036_854_775_807 var xs = [0] * 64 xs[0] = big xs[16] = -5 xs[32] = 10 xs[48] = -10 print(par sum(x for x in xs)) print(sum(x for x in xs)) ``` Output ```text 9223372036854775802 panic: integer overflow in addition --> ov2.br:9:11 ``` When the exact total fits, both orders give the same integer, since integer addition is associative as long as nothing overflows. If partial results may come near the limits, use a wider type (`i128`) or `float`. `min`, `max`, `any` and `all` never overflow. `min` and `max` compare the way the sequential versions do: a later value replaces the current one only if it is strictly smaller (or larger). ## par sum and sum [Section titled “par sum and sum”](#par-sum-and-sum) | | `sum(...)` | `par sum(...)` | | ---------------------------- | ----------------------- | ---------------------------------------- | | order | left to right, from `0` | leaves of 16, then a balanced tree | | threads | one | the pool, and the GPU when it pays | | float result | the left fold’s bits | the tree’s bits, the same on any machine | | integer overflow | of the running total | of any partial result in the tree | | accuracy for long float sums | error can grow with `n` | error grows with `log2(n)` | Both are deterministic. They’re just different orders, so pick one and keep it. If you need a result that matches another language’s plain loop bit for bit, use the sequential `sum` (or a `for` loop). ## The 0.4.0 change [Section titled “The 0.4.0 change”](#the-040-change) Up to Brine 0.3.0, a `par` reduction split its elements into at most 256 chunks, summed each chunk left to right and added the chunk results in order. That was also independent of the thread count, but a GPU needs thousands of independent partial results, so 0.4.0 changed to the leaves and tree on this page. It is a breaking change (see the [changelog](/reference/changelog/)): * `par sum` and `par product` of floats can differ from 0.3.0 in the last bits, usually closer to the exact result; * whether an integer `par sum` or `par product` overflows is decided by the new order. Programs that need the old bits should sum sequentially. ## Related pages [Section titled “Related pages”](#related-pages) * [Parallelism overview](/parallelism/overview/#par-reductions): the reducers and filters * [GPU offload](/parallelism/gpu/#same-results): how the GPU runs the same tree * [Multiple processes: world](/parallelism/world/#combining-world-with-par): `world.sum` combines ranks in rank order # GPU offload > Which par constructs and bodies run on an NVIDIA (CUDA) or Apple (Metal) GPU, how the runtime decides when, why the results are the same bits as on the CPU, BRINE_GPU and BRINE_GPU_LOG, benchmarks, and tips for GPU-friendly code. 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 [Section titled “What you need”](#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](#roadmap). ## A first look [Section titled “A first look”](#a-first-look) The [Collatz example](/parallelism/overview/#threads) runs one `par max` over ten million numbers. Repeat it four times and ask the runtime what it did: gpu_demo.br ```brine 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") ``` ```sh 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): Output ```text 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 [Section titled “Which constructs can run on a GPU”](#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: ```text 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 [Section titled “When the runtime uses it”](#when-the-runtime-uses-it) For each launch of an eligible construct, the runtime compares the two sides: 1. **Too small or nested:** constructs with fewer than 4096 elements, and constructs inside another `par`, run on the CPU. 2. **The CPU’s time** is estimated by running the first elements on one thread for about 100 µs, then measured on every later launch. 3. **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. 4. **It uses the device when that is at least 25% faster** (the device’s time, copies included, is under 75% of the CPU’s). 5. **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_THREADS=1 BRINE_GPU_LOG=1 ./collatz ```text 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 [Section titled “Same results”](#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](/parallelism/deterministic-reductions/) 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: chk.br ```brine 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=on BRINE_GPU_LOG=1 ```text 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 [Section titled “Copies”](#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](#roadmap), 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 [Section titled “BRINE_GPU and BRINE_GPU_LOG”](#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: ```text brine gpu: :: n= -> gpu ms (kernel(s) , copies , MB; cpu estimate ) brine gpu: :: n= -> cpu ms () ``` 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](/tooling/environment-variables/) for the others, including `BRINE_DUMP_PTX=file`, which writes the kernel module when building. ## Benchmarks [Section titled “Benchmarks”](#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 [Section titled “Writing GPU-friendly code”](#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`](https://github.com/brinelang/brine/blob/main/examples/find_signal.br) states its ranges with `requires`, and no runtime check is left in its search loop. See [runtime checks](/proofs/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 [Section titled “Roadmap”](#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. ## Related pages [Section titled “Related pages”](#related-pages) * [Parallelism overview](/parallelism/overview/) * [Deterministic reductions](/parallelism/deterministic-reductions/) * [Environment variables](/tooling/environment-variables/) # Parallelism overview > The four par constructs (par for, par [...], par reductions, par(a, b)), how many threads they use, what a par body may contain, nesting, and which construct to pick. Parallelism in Brine is syntax: put `par` in front of a loop, a comprehension, a reduction or a pair of expressions, and it runs on every core (and on the GPU, when that’s faster). The compiler rejects any `par` body that could race, and reductions give the same bits on any number of threads, so adding `par` never changes what a correct program prints. ## The four constructs [Section titled “The four constructs”](#the-four-constructs) | Construct | What it does | Result | | ----------------------------- | ---------------------------------------------------------------- | ------------------------------ | | `par for i in lo..hi:` | runs the body once per `i`, in parallel | nothing; writes go to `out[i]` | | `par [e for x in xs]` | parallel map: one result per element | an array, in order | | `par sum(e for x in xs if c)` | parallel reduction: `sum`, `product`, `min`, `max`, `any`, `all` | one value | | `par(f(a), g(b))` | fork-join: evaluates the expressions at the same time | a tuple | ## A complete example [Section titled “A complete example”](#a-complete-example) overview\.br ```brine 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 = 1_000_000 # par [...]: one result per element, in order let lens = par [collatz_len(i) for i in 1..=n] # par reductions, with and without a filter let longest = par max(l for l in lens) let total = par sum(l for l in lens) let long_ones = par sum(1 for l in lens if l > 300) # par for: each iteration writes only its own element of `hist` var hist = [0] * 8 par for b in 0..8: hist[b] = sum(1 for l in lens if l / 100 == b) # par(a, b): independent expressions, run at the same time let (a, b) = par(collatz_len(27), collatz_len(97)) print(f"longest: {longest}, average: {float(total) / float(n):.2f}, over 300: {long_ones}") print(f"by hundreds: {hist}") print(f"27 takes {a} steps, 97 takes {b}") ``` ```sh brine run overview.br ``` Output ```text longest: 524, average: 131.43, over 300: 5617 by hundreds: [344030, 530366, 119920, 5574, 106, 4, 0, 0] 27 takes 111 steps, 97 takes 118 ``` The output is the same on every run and every machine, whatever the number of threads. ## par for [Section titled “par for”](#par-for) `par for` runs its body once for every value of the loop variable, spread over the thread pool. The iterations run in no particular order, so the body can’t change variables from outside the loop, with one exception: an outer array may be written at the loop index. ```brine fn main(): let n = 8 var out = [0.0] * n par for i in 0..n: out[i] = sqrt(float(i)) print(out) ``` Output ```text [0.0, 1.0, 1.4142135623730951, 1.7320508075688772, 2.0, 2.23606797749979, 2.449489742783178, 2.6457513110645907] ``` * The loop can be over a range (`lo..hi`, `lo..=hi`, `range(a, b, step)`), an array, a map, or `enumerate(xs)`. Only a loop over a range can write `out[i]`; the others can read outer values but not write them. * `out[i]` must be exactly the loop variable. `out[2 * i]` and `out[i + 1]` are errors, and once the body writes `out[i]` it may not read `out` any other way (`out[i - 1]`, `len(out)`). See [race freedom](/parallelism/race-freedom/). * `continue` ends the current iteration. `break` and `return` are errors ([E0505](/reference/errors/#e0505)): other iterations are already running. * A `par for` can’t have an `invariant` ([E0507](/reference/errors/#e0507)): there is no state between iterations. ## par \[…] [Section titled “par \[…\]”](#par-) A parallel map evaluates the expression for every element and returns the results as an array, in the order of the input. It is the usual way to compute one value per element. ```brine fn main(): let words = ["fig", "pear", "plum", "banana"] let lengths = par [len(w) for w in words] let squares = par [i * i for i in 0..6] print(lengths, squares) ``` Output ```text [3, 4, 4, 6] [0, 1, 4, 9, 16, 25] ``` `par [...]` can’t have an `if` filter ([E0508](/reference/errors/#e0508)), because each element’s place in the result has to be known before the elements are computed. Filter with a sequential comprehension afterwards, or count and combine with a filtered reduction. ## par reductions [Section titled “par reductions”](#par-reductions) `par sum`, `par product`, `par min`, `par max`, `par any` and `par all` combine one value per element into a single result. A reduction may filter with `if`. ```brine fn main(): let total = par sum(i for i in 0..10 if i % 2 == 0) let p = par product(i for i in 1..6) let lo = par min(i * 3 - 7 for i in 0..10) let hi = par max(i for i in 0..10 if i < 5) let a = par any(i == 7 for i in 0..10) let b = par all(i < 10 for i in 0..10) print(total, p, lo, hi, a, b) ``` Output ```text 20 120 -7 4 true true ``` * Over no elements, `sum` is `0`, `product` is `1`, `any` is `false` and `all` is `true`. `min` and `max` of nothing panic (`max() of an empty sequence`). * Integer `sum` and `product` stop the program on overflow, as every integer operation does. * The elements are combined in one fixed order that depends only on how many there are, so a float `par sum` gives the same bits on 1 thread, 32 threads or a GPU. That order isn’t left to right, so it can differ from a sequential `sum` in the last bits (usually by being closer to the exact result). See [deterministic reductions](/parallelism/deterministic-reductions/). ## par(a, b) [Section titled “par(a, b)”](#para-b) A fork-join evaluates two or more independent expressions at the same time and returns their values as a tuple. ```brine fn fib(n: int) -> int: if n < 2: return n return fib(n - 1) + fib(n - 2) fn main(): let (a, b, c) = par(fib(30), fib(31), fib(32)) print(a, b, c) ``` Output ```text 832040 1346269 2178309 ``` The expressions follow the same rules as any `par` body: they can read variables but not change them, so `par(xs.pop(), len(xs))` and `par(bump(ref n), 5)` are errors. `par(e)` with one expression is [E0113](/reference/errors/#e0113). ## Threads [Section titled “Threads”](#threads) `par` constructs share one thread pool per process. It has one thread per core by default; change it with `--threads` or `BRINE_THREADS`: ```sh brine run collatz.br --release --threads 8 BRINE_THREADS=8 brine run collatz.br --release # the same; also works for built binaries ``` collatz.br ```brine 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 let t0 = clock() let longest = par max(collatz_len(i) for i in 1..=n) let t1 = clock() print(f"longest chain below {n}: {longest} steps ({(t1 - t0) * 1000.0:.0f} ms)") ``` With the GPU turned off (`BRINE_GPU=off`) on a Ryzen 9 9950X3D (16 cores, 32 threads), `--release`: | `BRINE_THREADS` | 1 | 2 | 4 | 8 | 16 | 32 | | --------------- | ---- | --- | --- | --- | --- | -- | | time (ms) | 1355 | 710 | 360 | 181 | 102 | 63 | Every run prints `longest chain below 10000000: 685 steps`. With the GPU left on `auto`, the same program on an RTX 4090 takes 4-5 ms per run once the device is ready; see [GPU offload](/parallelism/gpu/). With [`--ranks N`](/parallelism/world/), every rank is its own process with its own pool. On one machine, give each rank its share of the cores (`--ranks 4 --threads 8` on 32 threads). See also [environment variables](/tooling/environment-variables/). ## What a par body can contain [Section titled “What a par body can contain”](#what-a-par-body-can-contain) A `par` body is ordinary Brine with one restriction: it can’t change anything that other iterations can see. In practice: | Allowed | Not allowed | | ------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------- | | reading any outer variable, array or map | assigning an outer variable ([E0501](/reference/errors/#e0501)) | | `out[i] = ...` in `par for i in` a range | `out[j]` for any other index, or reading `out` elsewhere in that loop ([E0502](/reference/errors/#e0502)) | | local `let`/`var`, local arrays, `push` on them | `push`, `pop`, `sort` and other changing methods on outer arrays; changing maps ([E0501](/reference/errors/#e0501)) | | calling functions, `ref` arguments to *local* variables | `ref` arguments to outer variables ([E0501](/reference/errors/#e0501)) | | `print`, `eprint`, `clock`, `read_file`, `getenv` | `write_file`, `run`, `exit`, changing `os` calls, `world` ([E0503](/reference/errors/#e0503)) | | `continue`, `assert`, panics | `break`, `return` ([E0505](/reference/errors/#e0505)), `?` ([E0342](/reference/errors/#e0342)) | `print` is allowed, but the lines come out in whatever order the iterations finish (each `print` writes its whole line at once). The rules and the errors are on the [race freedom](/parallelism/race-freedom/) page. ## Nesting [Section titled “Nesting”](#nesting) A `par` construct inside another one is allowed. The inner one runs on the thread that runs the outer iteration, sequentially, so nesting never starts more threads than the pool has: ```brine fn main(): let rows = par [par sum(i * j for j in 0..4) for i in 0..4] print(rows) ``` Output ```text [0, 6, 12, 18] ``` Usually it’s best to put `par` on the outermost loop that has enough iterations to keep every core busy, and leave the inner ones sequential. Nested constructs don’t run on the GPU, and neither does a construct whose body contains one. ## Which one to use [Section titled “Which one to use”](#which-one-to-use) | You want | Use | | ---------------------------------------------------- | ---------------------------------------------------------------------- | | one new value per element | `par [f(x) for x in xs]` | | one number from many (a total, a count, a maximum) | `par sum(...)`, `par max(...)`, … with `if` to filter | | a filtered array | a sequential `[x for x in xs if p(x)]`, or `par [...]` of flags first | | to fill an existing array, or several arrays at once | `par for i in 0..n:` writing `a[i]`, `b[i]` | | two or three unrelated pieces of work | `par(f(), g())` | | work spread over processes or machines | the [`world` module](/parallelism/world/), with `par` inside each rank | `par` pays off when a construct does enough work to cover handing it to the pool. Loops over a few dozen cheap elements are fine to leave sequential. ## Related pages [Section titled “Related pages”](#related-pages) * [Race freedom](/parallelism/race-freedom/): the rule and every error it gives * [Deterministic reductions](/parallelism/deterministic-reductions/): the order of a `par sum` * [GPU offload](/parallelism/gpu/): which constructs run on a GPU, and when * [Multiple processes: world](/parallelism/world/) and [deadlock freedom](/parallelism/deadlock-freedom/) # Race freedom > The compile-time rule that makes every par body free of data races, why it is enough, every error it reports (E0501, E0502, E0503, E0505), and how to restructure code that breaks it. A data race in Brine is a compile error. Inside a `par` body, variables from outside are read-only, with one exception: `par for i in ...` may write an outer array at exactly `[i]`, and then may not touch that array any other way. Because Brine values never alias, that rule is all it takes. ## The rule [Section titled “The rule”](#the-rule) Inside the body of `par for`, `par [...]`, a `par` reduction or `par(a, b)`: 1. **Outer variables are read-only.** You can’t assign them, call a method that changes them (`push`, `pop`, `sort`, `insert`, …), change a map, or pass them as `ref`. 2. **The exception: `out[i]`.** In `par for i in lo..hi`, an array declared outside the loop may be written at `out[i]`, where the index is exactly the loop variable. The element may be a struct or an array itself (`out[i].x = ...`, `grid[i][j] = ...`). 3. **An array written at `out[i]` isn’t accessed any other way in that loop.** No `out[i - 1]`, no `len(out)`, no passing `out` to a function. 4. **No effects that depend on order.** `write_file`, `run`, `exit`, the `os` calls that change things outside the program, and `world` communication aren’t allowed. `print` is. 5. **Every iteration runs to its end.** No `break`, no `return`, no `?`. `continue` is fine. Variables declared inside the body are local to one iteration, and you can do anything with them. ```brine fn fill(ref xs: [int]): for k in 0..len(xs): xs[k] = k fn main(): let base = [10, 20, 30, 40] var out = [0] * 4 par for i in 0..4: var local = [0] * 3 # local to this iteration fill(ref local) # `ref` to a local is fine local.push(base[i]) # reading outer values is fine out[i] = len(local) + local[3] print(out) ``` Output ```text [14, 24, 34, 44] ``` ## Why this is enough [Section titled “Why this is enough”](#why-this-is-enough) A data race needs two threads touching the same memory at the same time, one of them writing. In most languages the compiler can’t rule that out, because two names can point at the same memory. In Brine they can’t: * **Values, not shared objects.** `let b = a` copies, and arguments are passed by value. Arrays and strings share memory only until one copy is changed (copy-on-write), and the reference counts are atomic. Nothing you can write reaches another variable’s memory. * **References are second-class.** A `ref` can’t be stored in a struct or an array, or returned, so the compiler always knows which variable a `ref` names. `let r = ref out` inside a `par` body counts as `out`. * **Functions can only change what they are given as `ref`.** A function called from a `par` body gets copies of outer values, and rule 1 stops it from getting a `ref` to one. So the only memory several iterations can reach is the outer variables. Rule 1 makes them read-only. Rule 2 lets iteration `i` write element `i`, which no other iteration writes, and rule 3 makes sure no other iteration reads it while it changes. With no writes in common and no reads of another iteration’s writes, there is no race, and the result can’t depend on timing. The rules are checked on the body as written, not by analysis of what the indexes might be, so the errors are predictable: the same code is accepted or rejected on every machine. ## Assigning an outer variable [Section titled “Assigning an outer variable”](#assigning-an-outer-variable) race.br ```brine fn main(): let xs = [1, 2, 3, 4] var total = 0 par for i in 0..len(xs): total += xs[i] print(total) ``` ```text error[E0501]: cannot assign to `total` inside a `par` body --> race.br:5:9 | 5 | total += xs[i] | ^^^^^ would be a data race | = note: `total` is shared by all parallel iterations = help: a `par for` may only write `total[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop = run `brine explain E0501` for more about this error error: could not compile due to 1 error ``` Combining values from every iteration is what reductions are for: ```brine fn main(): let xs = [1, 2, 3, 4] let total = par sum(x for x in xs) print(total) ``` Output ```text 10 ``` A reduction is both race-free and [deterministic](/parallelism/deterministic-reductions/), and with a filter it also covers counting (`par sum(1 for x in xs if x > 0)`), finding the largest (`par max`), and testing (`par any`, `par all`). ## Writing another element [Section titled “Writing another element”](#writing-another-element) `out[i]` must use exactly the loop variable. Any other index could be the one another iteration writes: stride.br ```brine fn main(): let n = 5 var out = [0] * (2 * n) par for i in 0..n: out[2 * i] = i * i print(out) ``` ```text error[E0501]: cannot assign to `out` inside a `par` body --> stride.br:5:9 | 5 | out[2 * i] = i * i | ^^^^^^^^^^ would be a data race | = note: `out` is shared by all parallel iterations = help: a `par for` may only write `out[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop = run `brine explain E0501` for more about this error error: could not compile due to 1 error ``` Loop over the elements you write instead, and work out the input from the output index: ```brine fn main(): let n = 5 var out = [0] * (2 * n) par for j in 0..2 * n: if j % 2 == 0: out[j] = (j / 2) * (j / 2) print(out) ``` Output ```text [0, 0, 1, 0, 4, 0, 9, 0, 16, 0] ``` ## Reading the array you write [Section titled “Reading the array you write”](#reading-the-array-you-write) Once a loop writes `xs[i]`, every other use of `xs` in it is an error, reads included, because the neighbouring element may be changing at that moment: smooth.br ```brine fn main(): var xs = [0.0, 3.0, 9.0, 3.0, 0.0, 6.0] par for i in 1..len(xs) - 1: xs[i] = (xs[i - 1] + xs[i] + xs[i + 1]) / 3.0 print(xs) ``` ```text error[E0502]: `xs` is written at `xs[i]` in this `par for`, so it can't be accessed any other way --> smooth.br:4:18 | 4 | xs[i] = (xs[i - 1] + xs[i] + xs[i + 1]) / 3.0 | ^^^^^^^^^ accessed here | = note: other iterations may be writing to the other elements at the same time = help: only use `xs[i]` inside the loop, or copy the data you need before the loop = run `brine explain E0502` for more about this error error: could not compile due to 1 error ``` Read from a copy made before the loop. The copy costs nothing until the loop writes to `xs` (copy-on-write), and the result no longer depends on which neighbour was updated first: ```brine fn main(): var xs = [0.0, 3.0, 9.0, 3.0, 0.0, 6.0] let old = xs par for i in 1..len(old) - 1: xs[i] = (old[i - 1] + old[i] + old[i + 1]) / 3.0 print(xs) ``` Output ```text [0.0, 4.0, 5.0, 4.0, 3.0, 6.0] ``` A computation where each element needs the *new* value of the one before it (a running total, for example) is sequential by nature. Write it as a sequential loop. ## Changing an outer array [Section titled “Changing an outer array”](#changing-an-outer-array) `push`, `pop`, `insert`, `sort` and the other changing methods count as writes: collect.br ```brine fn is_special(i: int) -> bool: return i % 7 == 0 and i % 2 == 1 fn main(): var found: [int] = [] par for i in 0..100: if is_special(i): found.push(i) print(found) ``` ```text error[E0501]: cannot push to `found` inside a `par` body --> collect.br:8:13 | 8 | found.push(i) | ^^^^^ would be a data race | = note: `found` is shared by all parallel iterations = help: a `par for` may only write `found[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop = run `brine explain E0501` for more about this error error: could not compile due to 1 error ``` Compute the expensive part in parallel, one result per element, then collect sequentially. This also keeps the results in order, which pushing from many threads wouldn’t: ```brine fn is_special(i: int) -> bool: return i % 7 == 0 and i % 2 == 1 fn main(): let n = 100 let keep = par [is_special(i) for i in 0..n] let found = [i for i in 0..n if keep[i]] let count = par sum(1 for i in 0..n if keep[i]) print(found, count) ``` Output ```text [7, 21, 35, 49, 63, 77, 91] 7 ``` ## Passing an outer variable as ref [Section titled “Passing an outer variable as ref”](#passing-an-outer-variable-as-ref) A `ref` argument lets the function change the variable, so an outer variable can’t be passed as `ref` from a `par` body: log.br ```brine fn record(ref log: [str], msg: str): log.push(msg) fn main(): var log: [str] = [] par for i in 0..4: record(ref log, f"step {i}") print(log) ``` ```text error[E0501]: cannot pass as `ref` `log` inside a `par` body --> log.br:7:20 | 7 | record(ref log, f"step {i}") | ^^^ would be a data race | = note: `log` is shared by all parallel iterations = help: a `par for` may only write `log[i]` (its own element); to combine values use `par sum(...)`, `par [...]`, or a sequential loop = run `brine explain E0501` for more about this error error: could not compile due to 1 error ``` Return the value instead and let `par [...]` collect it: ```brine fn main(): let log = par [f"step {i}" for i in 0..4] print(log) ``` Output ```text ["step 0", "step 1", "step 2", "step 3"] ``` ## Changing a map [Section titled “Changing a map”](#changing-a-map) Maps can be read in a `par` body but not changed, not even at the loop index: squares.br ```brine fn main(): var squares: {int: int} = {} par for i in 0..5: squares[i] = i * i print(squares) ``` ```text error[E0501]: cannot assign to `squares` inside a `par` body --> squares.br:4:9 | 4 | squares[i] = i * i | ^^^^^^^^^^ would be a data race | = note: `squares` is shared by all parallel iterations = help: maps can't be changed inside `par`; compute the values with `par [...]`, then fill the map in a sequential loop = run `brine explain E0501` for more about this error error: could not compile due to 1 error ``` ```brine fn main(): let vals = par [i * i for i in 0..5] var squares: {int: int} = {} for i in 0..5: squares[i] = vals[i] print(squares) ``` Output ```text {0: 0, 1: 1, 2: 4, 3: 9, 4: 16} ``` ## Effects that depend on order [Section titled “Effects that depend on order”](#effects-that-depend-on-order) Writing files and starting processes change the world outside the program, and the order of those changes would depend on timing. They’re [E0503](/reference/errors/#e0503), as are `exit`, `world` communication, and the `os` functions that change things (`os.spawn`, `os.wait`, `os.poll`, `os.kill`, `os.make_dir`, `os.remove_file`, `os.rename`, `os.sleep`, `os.enable_ansi`): files.br ```brine fn main(): par for i in 0..4: let r = write_file(f"part{i}.txt", f"part {i}\n") ``` ```text error[E0503]: `write_file` can't be called inside a `par` body --> files.br:3:17 | 3 | let r = write_file(f"part{i}.txt", f"part {i}\n") | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not allowed here | = help: its effects would happen in an unpredictable order; do it before or after the `par` = run `brine explain E0503` for more about this error error: could not compile due to 1 error ``` Build the contents in parallel, then write them in order: ```brine fn main(): let texts = par [f"part {i}\n" for i in 0..4] for i in 0..4: match write_file(f"part{i}.txt", texts[i]): case Ok(_): pass case Err(e): eprint(e) print("wrote", len(texts), "files") ``` Output ```text wrote 4 files ``` Reading is allowed: `read_file`, `file_exists`, `getenv` and `clock` can be called in a `par` body. So can `print` and `eprint`. Each call writes its whole line at once, but the lines of different iterations come out in whatever order the iterations run, so don’t rely on that order. ## Leaving the loop early [Section titled “Leaving the loop early”](#leaving-the-loop-early) first.br ```brine fn main(): let xs = [3, 8, 1, 9] par for i in 0..len(xs): if xs[i] > 5: break ``` ```text error[E0505]: `break` is not allowed inside a `par for` --> first.br:5:13 | 5 | break | ^^^^^ parallel iterations can't stop each other | = help: use `continue` to skip an iteration, or a sequential `for` loop = run `brine explain E0505` for more about this error error: could not compile due to 1 error ``` `return` is rejected the same way, and `?` (which may return) is [E0342](/reference/errors/#e0342). To find the first match, ask with a reduction: ```brine fn main(): let xs = [3, 8, 1, 9, 4] if par any(x > 5 for x in xs): let first = par min(i for i in 0..len(xs) if xs[i] > 5) print(first) ``` Output ```text 1 ``` ## Restructuring patterns [Section titled “Restructuring patterns”](#restructuring-patterns) | Sequential habit | Race-free version | | ---------------------------------------------- | ------------------------------------------------------------------------------------------------------- | | `total += f(x)` in a loop | `par sum(f(x) for x in xs)` | | counting matches | `par sum(1 for x in xs if p(x))` | | tracking the best so far | `par max(...)`, `par min(...)`; for the index, `par min(i for i in 0..n if xs[i] == best)` | | `found.push(x)` when `p(x)` | `let keep = par [p(x) for x in xs]`, then `[xs[i] for i in 0..n if keep[i]]` | | updating an array in place from its neighbours | copy first (`let old = xs`), read `old`, write `xs[i]` | | filling a map | `par [...]` for the values, then a sequential loop for the map | | a histogram | `par for b in 0..bins:` with `hist[b] = sum(1 for x in xs if bucket(x) == b)`, or one `par sum` per bin | | writing results to files | `par [...]` for the contents, then write sequentially | | `break` on the first match | `par any(...)`, then `par min(i ... if ...)` | ## Rules [Section titled “Rules”](#rules) * In a `par` body, outer variables are read-only; `par for i in` a range may write `out[i]` with exactly the loop variable ([E0501](/reference/errors/#e0501)). * An array written at `out[i]` can’t be used any other way in that loop ([E0502](/reference/errors/#e0502)). * No `write_file`, `run`, `exit`, changing `os` calls or `world` in `par` ([E0503](/reference/errors/#e0503)); `print` and reads are allowed. * No `break` or `return` ([E0505](/reference/errors/#e0505)); `continue` is fine. * `par for` has no invariants ([E0507](/reference/errors/#e0507)) and `par [...]` has no `if` filter ([E0508](/reference/errors/#e0508)). See also: [parallelism overview](/parallelism/overview/), [deterministic reductions](/parallelism/deterministic-reductions/), [references](/language/functions/). # Multiple processes: world > The built-in world module for MPI-style programs across processes and machines, with every call and its signature, messageable types, brine run --ranks, multi-machine setup, the TCP transport, and combining world with par. The built-in `world` module runs one program as several cooperating processes (*ranks*), on one machine or many, in the style of MPI. Every `world` call is collective: all ranks make it, in the same order, and the compiler checks that they do, so a Brine program can’t deadlock waiting for a message. Every program is also a valid one-rank program, so the same code runs with or without `--ranks`. ## A first program [Section titled “A first program”](#a-first-program) world.br ```brine fn main(): let rank = world.rank() let size = world.size() # each rank sums its own slice of the numbers var local = 0 for i in 0..1_000_000: if i % size == rank: local += i let total = world.sum(local) # every rank contributes one value; everyone gets the whole list let all = world.gather_all(rank * rank) if rank == 0: print(f"{size} ranks, total = {total}, squares = {all}") # pass a message around the ring: each rank sends to rank + 1 var token = "token" for step in 0..size: token = world.shift(token + f"->{rank}", 1) if rank == 0: print(f"after one lap: {token}") # all-to-all: element j of the array goes to rank j let outbox = [[rank, j] for j in 0..size] let inbox = world.exchange(outbox) if rank == size - 1: print(f"rank {rank} received {inbox}") ``` ```sh brine run world.br --ranks 4 ``` Output ```text 4 ranks, total = 499999500000, squares = [0, 1, 4, 9] after one lap: token->0->1->2->3 rank 3 received [[0, 3], [1, 3], [2, 3], [3, 3]] ``` Without `--ranks`, the same program runs as one rank: brine run world.br ```text 1 ranks, total = 499999500000, squares = [0] after one lap: token->0 rank 0 received [[0, 0]] ``` ## The API [Section titled “The API”](#the-api) Every call except `rank()` and `size()` communicates, and every rank must make it. `T` is a [messageable type](#messageable-types). | Call | Returns | What it does | Same on every rank? | | ---------------------------------- | --------------- | ------------------------------------------------------------------------------------------ | ------------------- | | `world.rank()` | `int` | this process’s rank, `0 .. size() - 1` | no | | `world.size()` | `int` | the number of ranks (`1` without `--ranks`) | yes | | `world.barrier()` | nothing | waits until every rank has reached it | | | `world.broadcast(root: int, v: T)` | `T` | every rank gets rank `root`’s `v` | yes | | `world.sum(v)` | the type of `v` | the sum of every rank’s `v` (`int` or `float`) | yes | | `world.min(v)` | the type of `v` | the smallest `v` (`int` or `float`) | yes | | `world.max(v)` | the type of `v` | the largest `v` (`int` or `float`) | yes | | `world.gather_all(v: T)` | `[T]` | every rank’s `v`, in rank order | yes | | `world.shift(v: T, by: int)` | `T` | sends `v` to rank `rank + by` and returns the value from rank `rank - by`, wrapping around | no | | `world.exchange(xs: [T])` | `[T]` | all-to-all: `xs[j]` goes to rank `j`; element `j` of the result came from rank `j` | no | * `world.sum`, `min` and `max` combine on rank 0 in rank order, then send the result to everyone, so they are deterministic for a given number of ranks. Integer `world.sum` stops the program on overflow. * `broadcast`’s root and `shift`’s distance must be the same on every rank ([E0511](/reference/errors/#e0511)). * `exchange` needs exactly one element per rank. Any other length panics: `world.exchange needs one element per rank: got 3 elements, but the world size is 2`. * There is no `send` or `recv` ([E0512](/reference/errors/#e0512)). Point-to-point messages are written with `shift` and `exchange`; see [deadlock freedom](/parallelism/deadlock-freedom/#no-send-or-recv). Every call at once, on three ranks: api.br ```brine fn main(): let rank = world.rank() let size = world.size() world.barrier() let root = world.broadcast(0, f"hello from rank {rank}") let lo = world.min(float(rank) * 1.5) let hi = world.max(rank * 10) let all = world.gather_all([rank, rank * rank]) let flags = world.gather_all(rank % 2 == 0) let left = world.shift(rank, 1) let right = world.shift(rank, -1) let inbox = world.exchange([f"{rank}->{j}" for j in 0..size]) print(f"rank {rank}: root={root} lo={lo} hi={hi} left={left} right={right} inbox={inbox}") if rank == 0: print(all, flags) ``` brine run api.br --ranks 3 ```text rank 2: root=hello from rank 0 lo=0.0 hi=20 left=1 right=0 inbox=["0->2", "1->2", "2->2"] rank 1: root=hello from rank 0 lo=0.0 hi=20 left=0 right=2 inbox=["0->1", "1->1", "2->1"] rank 0: root=hello from rank 0 lo=0.0 hi=20 left=2 right=1 inbox=["0->0", "1->0", "2->0"] [[0, 0], [1, 1], [2, 4]] [true, false, true] ``` Each rank’s lines are in order, but lines from different ranks come out in whatever order the ranks get there (rank 2 printed first in this run). Print results from one rank, usually 0, when the order matters. ## Messageable types [Section titled “Messageable types”](#messageable-types) Values sent between ranks can be `int`, `float`, `bool`, `str`, and arrays of those, nested to any depth (`[int]`, `[[float]]`, `[str]`, …). `world.sum`, `min` and `max` take `int` or `float` only. Anything else is [E0319](/reference/errors/#e0319): point.br ```brine struct P: x: int fn main(): let p = world.broadcast(0, P(x=1)) print(p) ``` ```text error[E0319]: values of type `P` can't be sent between processes yet --> point.br:5:32 | 5 | let p = world.broadcast(0, P(x=1)) | ^^^^^^ not messageable | = note: messageable types: int, float, bool, str, and arrays of those (e.g. [int], [[float]], [str]) = run `brine explain E0319` for more about this error error: could not compile due to 1 error ``` Send a struct as its fields (or an array of them), and a map as its keys and values. ## Running with –ranks [Section titled “Running with –ranks”](#running-with-ranks) ```sh brine run world.br --ranks 4 # 4 processes on this machine brine run world.br --ranks 4 --threads 8 # each with 8 threads for par ``` `brine run --ranks N` builds the program once, reserves `N` free local ports, and starts `N` copies with the [environment variables](#multiple-machines) set. Then: * all ranks print to the same terminal; * only rank 0 reads standard input (the others get an empty one); * `brine run` waits for all of them and exits with the lowest rank’s nonzero exit code (or 0); * if a rank fails, the others are stopped half a second later. Without `--ranks` (or with `--ranks 1`), `world.size()` is `1`, `world.rank()` is `0`, and every call returns at once: `sum(v)` is `v`, `gather_all(v)` is `[v]`, `shift(v, by)` is `v`. ## When a rank fails [Section titled “When a rank fails”](#when-a-rank-fails) A rank that panics or exits early never sends its next message. The ranks waiting for it stop with an error instead of hanging: crash.br ```brine fn main(): let rank = world.rank() let weights = [1.5] let mine = weights[rank] let total = world.sum(mine) print(f"rank {rank}: total = {total}") ``` brine run crash.br --ranks 2 ```text panic (rank 1): index 1 is out of bounds for an array of length 1 --> crash.br:4:16 panic (rank 0): rank 1 exited before sending the expected message --> crash.br:5:17 ``` The exit code is 101, as for any panic. Panic messages name the rank. ## Combining world with par [Section titled “Combining world with par”](#combining-world-with-par) `world` splits the work between processes; `par` splits each process’s share between its cores (and GPU). A common shape: each rank takes a block, reduces it with `par`, and `world.sum` adds up the ranks. harmonic_world.br ```brine fn main(): let rank = world.rank() let size = world.size() let n = 100_000_000 # each rank takes a contiguous block and sums it on all of its cores let lo = n / size * rank let hi = n if rank == size - 1 else n / size * (rank + 1) let local = par sum(1.0 / (float(i) + 1.0) for i in lo..hi) let total = world.sum(local) if rank == 0: print(f"{size} ranks: sum of 1/i for i in 1..={n} = {total}") ``` \--ranks 1, 2 and 4 ```text 1 ranks: sum of 1/i for i in 1..=100000000 = 18.9978964138539 2 ranks: sum of 1/i for i in 1..=100000000 = 18.9978964138539 4 ranks: sum of 1/i for i in 1..=100000000 = 18.997896413853898 ``` Each line is the same on every run and any thread count. The last digit changed at 4 ranks because the blocks changed: each rank’s `par sum` has its own [tree](/parallelism/deterministic-reductions/), and `world.sum` adds the ranks’ results left to right. A float total is reproducible for a given number of ranks, not across different numbers of ranks. If you need the same bits for any rank count, have each rank compute whole, fixed-size blocks and combine them in a fixed order (for example `world.gather_all` of the block sums, then a sum on every rank). Communication can’t happen inside a `par` body ([E0503](/reference/errors/#e0503)): call `world` before or after the construct. On one machine, give each rank its share of the cores with `--threads`, or the ranks’ thread pools compete for them. ## Multiple machines [Section titled “Multiple machines”](#multiple-machines) Each rank is an ordinary process configured by three environment variables. To run across machines, start the built program on each machine with: | Variable | Meaning | | ------------------ | ---------------------------------------------------------- | | `BRINE_RANK` | this process’s rank, `0 .. size - 1` | | `BRINE_WORLD_SIZE` | the number of ranks | | `BRINE_PEERS` | `host:port` for every rank, comma-separated, in rank order | Every rank gets the same `BRINE_PEERS`; entry `r` is where rank `r` listens. For two machines: ```sh brine build world.br --release -o world # on 10.0.0.1: BRINE_RANK=0 BRINE_WORLD_SIZE=2 BRINE_PEERS=10.0.0.1:7101,10.0.0.2:7101 ./world # on 10.0.0.2: BRINE_RANK=1 BRINE_WORLD_SIZE=2 BRINE_PEERS=10.0.0.1:7101,10.0.0.2:7101 ./world ``` The same works on one machine with `127.0.0.1` and different ports, which is what `--ranks` does. Run that way with two ranks, the program above printed rank 0’s lines in one terminal and rank 1’s in the other: rank 0 ```text 2 ranks, total = 499999500000, squares = [0, 1] after one lap: token->0->1 ``` rank 1 ```text rank 1 received [[0, 1], [1, 1]] ``` Without all three variables (or with `BRINE_WORLD_SIZE=1`), a program runs as a single rank. Ranks wait up to 30 seconds for the lower-numbered ranks to start listening, so the machines don’t have to start at the same moment. A `brine launch --hosts` command that does this for you is on the roadmap. ## Transport [Section titled “Transport”](#transport) * **Full-mesh TCP.** Every pair of ranks has one connection: each rank connects to the ranks below it and accepts the ranks above it. * **Sends never block.** Each rank runs a background receiver thread per peer that queues incoming messages, so a send completes even if the receiver is busy. * **FIFO.** Messages between a pair of ranks arrive in the order they were sent. * **Loopback when local.** When every peer is `127.x.x.x` or `localhost`, ranks listen on the loopback interface only: nothing outside the machine can reach them, and firewalls don’t ask. Otherwise they listen on all interfaces. * **No encryption or authentication.** Messages are plain TCP. Run multi-machine jobs on a network you trust. ## Related pages [Section titled “Related pages”](#related-pages) * [Deadlock freedom](/parallelism/deadlock-freedom/): the compile-time check, and what it allows * [Parallelism overview](/parallelism/overview/): `par` inside each rank * [Environment variables](/tooling/environment-variables/)