Parallelism overview

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

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

overview.br

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

brine run overview.br

Output

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

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.

fn main():
    let n = 8
    var out = [0.0] * n
    par for i in 0..n:
        out[i] = sqrt(float(i))
    print(out)

Output

[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.
• continue ends the current iteration. break and return are errors (E0505): other iterations are already running.
• A par for can’t have an invariant (E0507): there is no state between iterations.

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.

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

[3, 4, 4, 6] [0, 1, 4, 9, 16, 25]

par [...] can’t have an if filter (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

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.

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

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.

par(a, b)

A fork-join evaluates two or more independent expressions at the same time and returns their values as a tuple.

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

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.

Threads

par constructs share one thread pool per process. It has one thread per core by default; change it with --threads or BRINE_THREADS:

brine run collatz.br --release --threads 8
BRINE_THREADS=8 brine run collatz.br --release    # the same; also works for built binaries

collatz.br

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.

With --ranks N, 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.

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)
out[i] = ... in par for i in a range	out[j] for any other index, or reading out elsewhere in that loop (E0502)
local let/var, local arrays, push on them	push, pop, sort and other changing methods on outer arrays; changing maps (E0501)
calling functions, ref arguments to local variables	ref arguments to outer variables (E0501)
print, eprint, clock, read_file, getenv	write_file, run, exit, changing os calls, world (E0503)
continue, assert, panics	break, return (E0505), ? (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 page.

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:

fn main():
    let rows = par [par sum(i * j for j in 0..4) for i in 0..4]
    print(rows)

Output

[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

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, 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

• Race freedom: the rule and every error it gives
• Deterministic reductions: the order of a par sum
• GPU offload: which constructs run on a GPU, and when
• Multiple processes: world and deadlock freedom