scan.bend relies on unsafe/foreign

raw source on the hub · import 0xeef3a8486d410ea6f25709aac90dbf40/scan.bend as Scan

scan.bend: parallel prefix sums over an Array<U32>, in place.

import ./scan.bend as Scan Scan.exclusive(8n, a) # (a, total): a[j] becomes a[0] + .. + a[j - 1] Scan.inclusive(8n, a) # (a, total): a[j] becomes a[0] + .. + a[j]

A call's result is taken apart by a def's parameter (a def of yours taking r: Array<U32> & U32), not by a let or match on the call itself.

Sums wrap at 2^32, as U32.add does. The first argument is the fork depth b: the array is cut into 2^b blocks of equal size (b is lowered to log2 of the size when larger). Every b gives the same bits; b only sets how many lanes share the work. A call under ! (Scan.exclusive!(b, a), or a def of yours that calls it, marked with !) runs its forks on the GPU; without ! they run on the CPU threads.

Three passes, with no atomics: 1. per block, in parallel: the block's sum into s[i]; 2. s becomes its exclusive scan (the blocks' bases) and the total: on one lane below 2^12 sums; else by this same scan at half the depth (the 2^b sums in 2^(b/2) blocks), whose own pass 2 runs on one lane; 3. per block, in parallel: the block's scan from its base, in place. ref.bend's exclusive and inclusive are the sequential references; the tests check both passes against them bit for bit at many sizes and b.

Sharing. The blocks' lanes read and write one array through handles from Array.fork (Base, @unsafe): two O(1) handles to one block, joined back by Array.join. No def here is @unsafe itself: the fork trees below recurse on their depth, which the checker verifies. But in Bend's theory Array.fork(a) is (a, a) and Array.join(a, b) is a, so the theory drops the writes made through the second handle: never evaluate these defs in the checker (a main that returns a value); call them from an IO main, which runs compiled. bend lists every def that relies on the fork.

1 import

import Base

Types

type Two source · line 88 · raw

Type

Two
```
@a:Array<U32> -> @s:Array<U32> -> Two
```

Definitions

def sum.go source · line 41 · raw

@+n:Nat -> @+j:U32 -> @+s:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

r holds the array and the entry x read at j: adds x and the n entries after it to s. Returns the array and the sum.

def ex.go source · line 54 · raw

@+n:Nat -> @+j:U32 -> @+s:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

r holds the array and the entry x read at j: a[j] becomes s, the sum before it, and so on for the n entries after it. Returns the array and the running sum past the last entry.

def in.go source · line 65 · raw

@+n:Nat -> @+j:U32 -> @+s:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

As ex.go, but a[j] becomes the sum through it.

def go source · line 78 · raw

@+inc:Bool -> @+n:Nat -> @+j:U32 -> @+s:U32 -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

The scan of the n + 1 entries from j, from base s.

def two.join source · line 91 · raw

@l:Two -> @r:Two -> Two

def two.rejoin source · line 97 · raw

@a2:Array<U32> -> @s2:Array<U32> -> @r:Two -> Two

A leaf's spare handles, joined back after its work.

def sums.leaf.fin source · line 104 · raw

@+i:U32 -> @s:Array<U32> -> @r:Pair(Array<U32>, U32) -> Two

def sums.leaf source · line 109 · raw

@+i:U32 -> @+e:Nat -> @a:Array<U32> -> @s:Array<U32> -> Two

Block i (2^e entries): its sum into s[i].

def sums source · line 116 · raw

@+d:Nat -> @+i:U32 -> @+e:Nat -> @fa:Pair(Array<U32>, Array<U32>) -> @fs:Pair(Array<U32>, Array<U32>) -> Two

Pass 1's forks: d levels down to the leaves under leaf index i. fa and fs are two handles each to the data a and the sums s. Leaf i reads only its block of a and writes only s[i], so no two lanes touch one slot.

def puts.leaf.fin source · line 133 · raw

@s:Array<U32> -> @r:Pair(Array<U32>, U32) -> Two

def puts.leaf.at source · line 137 · raw

@+inc:Bool -> @+i:U32 -> @+e:Nat -> @a:Array<U32> -> @r:Pair(Array<U32>, U32) -> Two

def puts.leaf source · line 143 · raw

@+inc:Bool -> @+i:U32 -> @+e:Nat -> @a:Array<U32> -> @s:Array<U32> -> Two

Block i: its scan in place, from its base s[i].

def puts source · line 148 · raw

@+inc:Bool -> @+d:Nat -> @+i:U32 -> @+e:Nat -> @fa:Pair(Array<U32>, Array<U32>) -> @fs:Pair(Array<U32>, Array<U32>) -> Two

Pass 3's forks, shaped as pass 1's. Leaf i reads s[i] and reads and writes only its block of a: no two lanes touch one slot.

def half source · line 166 · raw

@+d:Nat -> Nat

floor(d / 2).

def run.fin source · line 177 · raw

@r:Two -> @+total:U32 -> Pair(Array<U32>, U32)

def run.mid source · line 182 · raw

@+inc:Bool -> @+d:Nat -> @+e:Nat -> @a:Array<U32> -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

Pass 3, from pass 2's bases and total.

def run.pre source · line 187 · raw

@+d:Nat -> @+e:Nat -> @a:Array<U32> -> Two

Pass 1 over a (2^lg entries) at depth d, into a new s.

def run0.sums source · line 191 · raw

@+inc:Bool -> @+d:Nat -> @+e:Nat -> @r:Two -> Pair(Array<U32>, U32)

The scan with pass 2 on one lane.

def run0 source · line 195 · raw

@+inc:Bool -> @+b:Nat -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

def run1.sums source · line 203 · raw

@+inc:Bool -> @+d:Nat -> @+e:Nat -> @r:Two -> Pair(Array<U32>, U32)

The scan with pass 2 by run0 at depth d / 2.

def run.pick source · line 210 · raw

@lo:Bool -> @+inc:Bool -> @+d:Nat -> @+e:Nat -> @r:Two -> Pair(Array<U32>, U32)

Pass 2 by run1 from 2^12 sums up, else on one lane: on the GPU we measured, the nested scan's forks cost more than one lane's walk below that.

def run source · line 217 · raw

@+inc:Bool -> @+b:Nat -> @r:Pair(Array<U32>, U32) -> Pair(Array<U32>, U32)

def exclusive source · line 229 · raw

@+b:Nat -> @a:Array<U32> -> Pair(Array<U32>, U32)

a[j] becomes a[0] + .. + a[j - 1] (a[0] becomes 0); returns the array and the total, a[0] + .. + a[n - 1].

def inclusive source · line 233 · raw

@+b:Nat -> @a:Array<U32> -> Pair(Array<U32>, U32)

a[j] becomes a[0] + .. + a[j]; returns the array and the total.