Parallelism

Deadlock freedom

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

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). Every call in the world 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

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:

A communication call can’t be controlled by a varying value (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.
Arguments that steer communication must be uniform (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

fn main():
    if world.rank() == 0:
        let total = world.sum(1)
        print(total)

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:

fn main():
    let mine = 1 if world.rank() == 0 else 0
    let total = world.sum(mine)
    if world.rank() == 0:
        print(total)

Loops whose length varies

A loop whose condition or range depends on the rank runs a different number of times on each rank:

fn main():
    let rank = world.rank()
    var steps = 0
    while steps < rank:
        world.barrier()
        steps += 1

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

and, or and conditional expressions decide whether their right side runs, so they count as branches. clock() differs between processes:

fn main():
    let t = clock()
    if t > 1.0 and world.sum(1) > 0:
        print("ok")

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

shift and exchange give each rank a different value, so their results are varying too:

fn main():
    let got = world.shift(world.rank(), 1)
    if got == 0:
        world.barrier()

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:

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}")

rank 0 got 2, someone got 0: true

What’s 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:

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}")

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

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:

fn report(x: int):
    let total = world.sum(x)
    print(total)

fn main():
    if world.rank() == 0:
        return
    report(1)

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:

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()))

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:

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}")

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:

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)

Roots and distances

world.broadcast(root, v) needs every rank to agree on the root, and world.shift(v, by) on the distance:

fn main():
    let root = world.rank()
    let v = world.broadcast(root, 42)
    print(v)

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

fn main():
    let x = world.recv(0)

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:

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]}")

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

world calls can’t appear in a par body (E0503): iterations run in no fixed order, so the ranks’ calls couldn’t line up.

fn main():
    let total = par sum(world.sum(i) for i in 0..10)
    print(total)

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.

What the check doesn’t 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.
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

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).
broadcast roots, shift distances and parameters that steer communication must be uniform (E0511).
No send or recv (E0512); use shift and exchange.
No communication in par (E0503).
Make a local fact uniform with world.sum, min, max, broadcast or gather_all, then branch on it.