bend-parallel Releases (1): 0.1.0.0 0xeef3a8486d410ea6f25709aac90dbf40 indexed https://jend.leeeet.dev/files.txt?path=bend-parallel@0.1.0.0 Definitions (112, 1 to 100 shown): Histogram.Bufs (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=Bufs) type Bufs is Type: Bufs{counts: Array, table: Array} Histogram.Bufs.new (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=Bufs.new) # Empty buffers: the first call allocates what it needs. def Bufs.new() -> Bufs: Histogram.kbits.of (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=kbits.of) def kbits.of(big: Bool, +k: U32) -> Nat: Histogram.kbits (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=kbits) # ceil(log2 K), for K >= 1. def kbits(+k: U32) -> Nat: Histogram.Bufs.sized (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=Bufs.sized) # Buffers for 2^lg keys at fork depth b and k buckets, allocated now. def Bufs.sized(+b: Nat, +k: U32, +lg: Nat) -> Bufs: Histogram.fit.pick (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=fit.pick) def fit.pick(ok: Bool, +d: Nat, t: Array) -> Array: Histogram.fit.eq (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=fit.eq) # t when it holds exactly 2^d entries, else a new one. def fit.eq(+d: Nat, r: Array & U32) -> Array: Histogram.fit.ge (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=fit.ge) # t when it holds at least 2^d entries, else a new one. def fit.ge(+d: Nat, r: Array & U32) -> Array: Histogram.Two (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=Two) type Two is Type: Two{a: Array, b: Array} Histogram.two.join (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=two.join) def two.join(l: Two, r: Two) -> Two: Histogram.two.rejoin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=two.rejoin) def two.rejoin(a2: Array, b2: Array, r: Two) -> Two: Histogram.zero.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=zero.go) # n + 1 zeros from at. def zero.go(+n: Nat, +at: U32, t: Array) -> Array: Histogram.bump.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=bump.at) def bump.at(+i: U32, r: Array & U32) -> Array: Histogram.bump (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=bump) # One more at t[i]. def bump(+i: U32, t: Array) -> Array: Histogram.count.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count.go) # r holds the keys and the key x read at j: one more in x's bucket of the # row at row, then the same for the n keys after j. k1 is K - 1. def count.go(+n: Nat, +j: U32, +row: U32, +k1: U32, t: Array, r: Array & U32) -> Two: Histogram.rows.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=rows.leaf) # Block i (2^e keys from i * 2^e): its row, at i * 2^kb, zeroed, then its # keys counted into it. k is K (at least 1). def rows.leaf(+i: U32, +e: Nat, +kb: Nat, +k: U32, ks: Array, t: Array) -> Two: Histogram.rows (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=rows) # Pass 1's forks: d levels down to the blocks under block index i. fk and # ft are two handles each to the keys and the table. Block i reads only # its keys and reads and writes only its row (entries i * 2^kb to # i * 2^kb + K - 1): no two lanes touch one slot. def rows(+d: Nat, +i: U32, +e: Nat, +kb: Nat, +k: U32, fk: Array & Array, ft: Array & Array) -> Two: Histogram.small (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=small) # d is below 12: the table is small, and its rows are not split. def small(+d: Nat) -> Bool: Histogram.col.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=col.go) # r holds the table and the entry x read at at: adds x and the n entries # after it, each step further on, to s. def col.go(+n: Nat, +at: U32, +step: U32, +s: U32, r: Array & U32) -> Array & U32: Histogram.ins.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=ins.go) # As col.go, but each entry becomes the sum through it (in place). def ins.go(+n: Nat, +at: U32, +step: U32, +s: U32, r: Array & U32) -> Array: Histogram.grp.put (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=grp.put) def grp.put(+at: U32, r: Array & U32) -> Array: Histogram.grp.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=grp.one) # Column c of a group (rows from top, nm + 1 of them, step apart), when # c < K: sc, each entry becomes the group's sum through it; else the sum # goes into the last row (at last). def grp.one(lt: Bool, +sc: Bool, +c: U32, +top: U32, +last: U32, +step: U32, +nm: Nat, t: Array) -> Array: Histogram.grp.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=grp.go) # Columns c to c + n of a group. def grp.go(+n: Nat, +sc: Bool, +c: U32, +k: U32, +top: U32, +last: U32, +step: U32, +nm: Nat, t: Array) -> Array: Histogram.grp.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=grp.leaf) # Lane i: rows group i / 2^gc (2^m rows of 2^kb), columns group i % 2^gc # (2^w columns). def grp.leaf(+sc: Bool, +i: U32, +gc: Nat, +w: Nat, +m: Nat, +kb: Nat, +k: U32, t: Array) -> Array: Histogram.grp (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=grp) # Pass 2a's forks (sort.bend's too, with sc): d levels down to the lanes # under lane i, with two handles to the table. Lane i reads and writes # only its group's rows in its columns: no two lanes touch one slot. def grp(+d: Nat, +sc: Bool, +i: U32, +gc: Nat, +w: Nat, +m: Nat, +kb: Nat, +k: U32, ft: Array & Array) -> Array: Histogram.col.put (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=col.put) def col.put(+c: U32, cs: Array, r: Array & U32) -> Two: Histogram.col.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=col.one) # Column c's count into cs[c]: the sum of its nb + 1 entries from o + c, # step apart (the groups' last rows), when c < K; else 0. def col.one(lt: Bool, +c: U32, +o: U32, +step: U32, +nb: Nat, p: Two) -> Two: Histogram.cols.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=cols.go) # Columns c to c + n. def cols.go(+n: Nat, +c: U32, +k: U32, +o: U32, +step: U32, +nb: Nat, p: Two) -> Two: Histogram.cols (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=cols) # Pass 2b's forks: d levels down to groups of 2^w columns under group index # j. ft and fc are two handles each to the table and the counts. Group j # reads only its columns of the table and writes only its counts (entries # j * 2^w to j * 2^w + 2^w - 1): no two lanes write one slot. def cols(+d: Nat, +j: U32, +w: Nat, +k: U32, +o: U32, +step: U32, +nb: Nat, ft: Array & Array, fc: Array & Array) -> Two: Histogram.count.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count.fin) def count.fin(keys: Array, r: Two) -> Array & Bufs: Histogram.count.cols (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count.cols) # Pass 2b over the 2^kb columns, 2^min(d, kb) groups: each sums its # columns over the 2^r groups' last rows. def count.cols(+r: Nat, +m: Nat, +g: Nat, +k: U32, +kb: Nat, keys: Array, counts: Array, table: Array) -> Array & Bufs: Histogram.count.grp (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count.grp) # Pass 2a over 2^r groups of 2^m rows by 2^min(d, kb) groups of columns, # then 2b; below 2^12 rows, 2b alone, over 2^d groups of one row. def count.grp(lo: Bool, +d: Nat, +k: U32, +kb: Nat, counts: Array, p: Two) -> Array & Bufs: Histogram.count.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count.at) def count.at(+b: Nat, +k: U32, bufs: Bufs, r: Array & U32) -> Array & Bufs: Histogram.count (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/histogram.bend&name=count) # The histogram of keys into k buckets at fork depth b. Returns the keys, # unchanged, and the buffers, whose counts field holds the counts. def count(+b: Nat, +k: U32, keys: Array, bufs: Bufs) -> Array & Bufs: Scan.sum.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=sum.go) # 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 sum.go(+n: Nat, +j: U32, +s: U32, r: Array & U32) -> Array & U32: Scan.ex.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=ex.go) # 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 ex.go(+n: Nat, +j: U32, +s: U32, r: Array & U32) -> Array & U32: Scan.in.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=in.go) # As ex.go, but a[j] becomes the sum through it. def in.go(+n: Nat, +j: U32, +s: U32, r: Array & U32) -> Array & U32: Scan.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=go) # The scan of the n + 1 entries from j, from base s. def go(+inc: Bool, +n: Nat, +j: U32, +s: U32, r: Array & U32) -> Array & U32: Scan.Two (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=Two) type Two is Type: Two{a: Array, s: Array} Scan.two.join (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=two.join) def two.join(l: Two, r: Two) -> Two: Scan.two.rejoin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=two.rejoin) # A leaf's spare handles, joined back after its work. def two.rejoin(a2: Array, s2: Array, r: Two) -> Two: Scan.sums.leaf.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=sums.leaf.fin) def sums.leaf.fin(+i: U32, s: Array, r: Array & U32) -> Two: Scan.sums.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=sums.leaf) # Block i (2^e entries): its sum into s[i]. def sums.leaf(+i: U32, +e: Nat, a: Array, s: Array) -> Two: Scan.sums (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=sums) # 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 sums(+d: Nat, +i: U32, +e: Nat, fa: Array & Array, fs: Array & Array) -> Two: Scan.puts.leaf.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=puts.leaf.fin) def puts.leaf.fin(s: Array, r: Array & U32) -> Two: Scan.puts.leaf.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=puts.leaf.at) def puts.leaf.at(+inc: Bool, +i: U32, +e: Nat, a: Array, r: Array & U32) -> Two: Scan.puts.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=puts.leaf) # Block i: its scan in place, from its base s[i]. def puts.leaf(+inc: Bool, +i: U32, +e: Nat, a: Array, s: Array) -> Two: Scan.puts (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=puts) # 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 puts(+inc: Bool, +d: Nat, +i: U32, +e: Nat, fa: Array & Array, fs: Array & Array) -> Two: Scan.half (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=half) # floor(d / 2). def half(+d: Nat) -> Nat: Scan.run.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run.fin) def run.fin(r: Two, +total: U32) -> Array & U32: Scan.run.mid (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run.mid) # Pass 3, from pass 2's bases and total. def run.mid(+inc: Bool, +d: Nat, +e: Nat, a: Array, r: Array & U32) -> Array & U32: Scan.run.pre (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run.pre) # Pass 1 over a (2^lg entries) at depth d, into a new s. def run.pre(+d: Nat, +e: Nat, a: Array) -> Two: Scan.run0.sums (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run0.sums) # The scan with pass 2 on one lane. def run0.sums(+inc: Bool, +d: Nat, +e: Nat, r: Two) -> Array & U32: Scan.run0 (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run0) def run0(+inc: Bool, +b: Nat, r: Array & U32) -> Array & U32: Scan.run1.sums (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run1.sums) # The scan with pass 2 by run0 at depth d / 2. def run1.sums(+inc: Bool, +d: Nat, +e: Nat, r: Two) -> Array & U32: Scan.run.pick (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run.pick) # 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.pick(lo: Bool, +inc: Bool, +d: Nat, +e: Nat, r: Two) -> Array & U32: Scan.run (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=run) def run(+inc: Bool, +b: Nat, r: Array & U32) -> Array & U32: Scan.exclusive (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=exclusive) # a[j] becomes a[0] + .. + a[j - 1] (a[0] becomes 0); returns the array # and the total, a[0] + .. + a[n - 1]. def exclusive(+b: Nat, a: Array) -> Array & U32: Scan.inclusive (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/scan.bend&name=inclusive) # a[j] becomes a[0] + .. + a[j]; returns the array and the total. def inclusive(+b: Nat, a: Array) -> Array & U32: Sort.Bufs (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Bufs) type Bufs is Type: Bufs{perm: Array, counts: Array, offs: Array, table: Array} Sort.Bufs.new (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Bufs.new) # Empty buffers: the first call allocates what it needs. def Bufs.new() -> Bufs: Sort.Bufs.sized (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Bufs.sized) # Buffers for 2^lg keys at fork depth b and k buckets, allocated now. def Bufs.sized(+b: Nat, +k: U32, +lg: Nat) -> Bufs: Sort.Three (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Three) type Three is Type: Three{a: Array, b: Array, c: Array} Sort.three.join (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=three.join) def three.join(l: Three, r: Three) -> Three: Sort.three.rejoin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=three.rejoin) def three.rejoin(a2: Array, b2: Array, c2: Array, r: Three) -> Three: Sort.xs.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=xs.go) # r holds the table and the entry x read at at: it becomes s, and the n # entries after it (each step further on) follow, from s + x. Returns the # table and the sum past the last. def xs.go(+n: Nat, +at: U32, +step: U32, +s: U32, r: Array & U32) -> Array & U32: Sort.sum.put (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=sum.put) def sum.put(+c: U32, cs: Array, os: Array, r: Array & U32) -> Three: Sort.sum.col (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=sum.col) # The nb + 1 entries from at, step apart: their sum; when wr, each also # becomes the sum of those before it. def sum.col(+wr: Bool, +at: U32, +step: U32, +nb: Nat, t: Array) -> Array & U32: Sort.sum.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=sum.one) # Column c, when c < K: over its nb + 1 entries from o + c, step apart # (the groups' last rows, or all the rows of a small table), the total # into cs[c] and os[c], by sum.col. Else 0 into both. def sum.one(lt: Bool, +wr: Bool, +c: U32, +o: U32, +step: U32, +nb: Nat, p: Three) -> Three: Sort.sum.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=sum.go) # Columns c to c + n. def sum.go(+n: Nat, +wr: Bool, +c: U32, +k: U32, +o: U32, +step: U32, +nb: Nat, p: Three) -> Three: Sort.sums (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=sums) # Pass 2b's forks: d levels down to groups of 2^w columns under group j, # with two handles each to the table, the counts and the offsets. Group j # reads (and when wr writes) only its columns of the table and writes # only its own entries of counts and offs (j * 2^w to j * 2^w + 2^w - 1). def sums(+d: Nat, +wr: Bool, +j: U32, +w: Nat, +k: U32, +o: U32, +step: U32, +nb: Nat, ft: Array & Array, fc: Array & Array, fo: Array & Array) -> Three: Sort.base.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.fin) def base.fin(+q: U32, +s: U32, t: Array) -> Array: Sort.base.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.go) # r holds the table and x, the entry a row (step) above at, which holds # the group's running sum through that row: at becomes s + x, and so up # for the n rows above; the group's first row, the next above, becomes s. def base.go(+n: Nat, +at: U32, +step: U32, +s: U32, r: Array & U32) -> Array: Sort.base.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.at) # A group's column from its last row at (nm + 1 rows): r holds the table # and the group's base b, which the last row holds; o is offs[c]. def base.at(+at: U32, +step: U32, +nm: Nat, +o: U32, r: Array & U32) -> Array: Sort.base.os (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.os) def base.os(+c: U32, +last: U32, +step: U32, +nm: Nat, t: Array, r: Array & U32) -> Hist.Two: Sort.base.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.one) # Column c of a group, when c < K: from its first slot offs[c] plus the # group's base, which its last row holds. def base.one(lt: Bool, +c: U32, +last: U32, +step: U32, +nm: Nat, p: Hist.Two) -> Hist.Two: Sort.base.cols (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.cols) # Columns c to c + n of a group. def base.cols(+n: Nat, +c: U32, +k: U32, +last: U32, +step: U32, +nm: Nat, p: Hist.Two) -> Hist.Two: Sort.base.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=base.leaf) # Lane i: rows group i / 2^gc, columns group i % 2^gc (as Hist.grp.leaf). def base.leaf(+i: U32, +gc: Nat, +w: Nat, +m: Nat, +kb: Nat, +k: U32, p: Hist.Two) -> Hist.Two: Sort.bases (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=bases) # Pass 2c's forks, shaped as pass 2a's (Hist.grp), with two handles each # to the table and the offsets. Lane i reads the offsets and reads and # writes only its group's rows in its columns. def bases(+d: Nat, +i: U32, +gc: Nat, +w: Nat, +m: Nat, +kb: Nat, +k: U32, ft: Array & Array, fo: Array & Array) -> Hist.Two: Sort.fwd.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=fwd.go) # r holds the table and the entry x read at at: it becomes s, and the n # entries after it (each step further on) follow, from s + x. def fwd.go(+n: Nat, +at: U32, +step: U32, +s: U32, r: Array & U32) -> Array: Sort.fwd.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=fwd.at) def fwd.at(+c: U32, +kb: Nat, +nb: Nat, t: Array, r: Array & U32) -> Hist.Two: Sort.fwd.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=fwd.one) # Column c, when c < K: its entries from its first slot offs[c]. def fwd.one(lt: Bool, +c: U32, +kb: Nat, +nb: Nat, p: Hist.Two) -> Hist.Two: Sort.fwd.cols (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=fwd.cols) # Columns c to c + n. def fwd.cols(+n: Nat, +c: U32, +k: U32, +kb: Nat, +nb: Nat, p: Hist.Two) -> Hist.Two: Sort.fwds (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=fwds) # The forks, shaped as pass 2b's, with two handles each to the table and # the offsets. Group j reads only its own offsets and reads and writes # only its columns of the table. def fwds(+d: Nat, +j: U32, +w: Nat, +k: U32, +kb: Nat, +nb: Nat, ft: Array & Array, fo: Array & Array) -> Hist.Two: Sort.put.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=put.at) def put.at(+j: U32, +slot: U32, pm: Array, r: Array & U32) -> Hist.Two: Sort.put.one (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=put.one) # Key j, whose bucket's next slot is t[slot]: perm[that slot] <- j, and # the slot moves on. def put.one(+j: U32, +slot: U32, p: Hist.Two) -> Hist.Two: Sort.put.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=put.fin) def put.fin(ks: Array, p: Hist.Two) -> Three: Sort.put.go (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=put.go) # r holds the keys and the key x read at j: key j goes to the next slot # of its bucket in the row at row, then the n keys after j. k1 is K - 1. def put.go(+n: Nat, +j: U32, +row: U32, +k1: U32, p: Hist.Two, r: Array & U32) -> Three: Sort.puts.leaf (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=puts.leaf) # Block i (2^e keys from i * 2^e, its row at i * 2^kb). def puts.leaf(+i: U32, +e: Nat, +kb: Nat, +k: U32, ks: Array, t: Array, pm: Array) -> Three: Sort.puts (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=puts) # Pass 3's forks: d levels down to the blocks under block i, with two # handles each to the keys, the table and perm. Block i reads only its # keys, reads and writes only its row of the table, and writes perm only # at the slots its row hands it: pass 2 gave each (block, bucket) pair its # own run of slots, so no two lanes write one slot. def puts(+d: Nat, +i: U32, +e: Nat, +kb: Nat, +k: U32, fk: Array & Array, ft: Array & Array, fp: Array & Array) -> Three: Sort.run.fin (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.fin) def run.fin(cs: Array, os: Array, r: Three) -> Array & Bufs: Sort.run.puts (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.puts) # Pass 3. def run.puts(+d: Nat, +e: Nat, +kb: Nat, +k: U32, ks: Array, pm: Array, cs: Array, r: Hist.Two) -> Array & Bufs: Sort.run.bases (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.bases) # Pass 2c: by fwds when lo (a small table), else by bases. def run.bases(lo: Bool, +d: Nat, +e: Nat, +kb: Nat, +k: U32, ks: Array, pm: Array, cs: Array, t: Array, r: Array & U32) -> Array & Bufs: Sort.run.scan (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.scan) # Pass 2b's scan: offs becomes its exclusive scan. def run.scan(lo: Bool, +d: Nat, +e: Nat, +kb: Nat, +k: U32, ks: Array, pm: Array, r: Three) -> Array & Bufs: Sort.run.tots (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.tots) # Pass 2b, after 2a (t): over the 2^h groups' last rows. def run.tots(+d: Nat, +e: Nat, +kb: Nat, +k: U32, ks: Array, pm: Array, cs: Array, os: Array, t: Array) -> Array & Bufs: Sort.run.sums (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run.sums) # Pass 2a: each group's running column sums (Hist.grp), then 2b. For a # small table (lo), no 2a: 2b sums each column over all the rows. def run.sums(lo: Bool, +d: Nat, +e: Nat, +kb: Nat, +k: U32, pm: Array, cs: Array, os: Array, r: Hist.Two) -> Array & Bufs: Sort.run (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=run) # Pass 1. def run(+b: Nat, +k: U32, bufs: Bufs, r: Array & U32) -> Array & Bufs: Sort.Moved (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Moved) # A gather's arrays: the permutation, the source and the destination. type Moved<-T: Data> is Type: Moved{perm: Array, src: Array, dst: Array} Sort.Sd (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=Sd) type Sd<-T: Data> is Type: Sd{src: Array, dst: Array} Sort.gat.at (https://jend.leeeet.dev/definition.txt?path=bend-parallel@0.1.0.0/sort.bend&name=gat.at) def gat.at(~T: Data, +j: U32, dst: Array, r: Array & T) -> Sd: More: https://jend.leeeet.dev/packages/bend-parallel.txt?definitions_offset=100