bend-parallel

Search uses release 0.1.0.0 · 112 definitions

Releases (1)

0.1.0.0 indexed

Definitions (112)

histogram.bend

type Bufs
def Bufs.newEmpty buffers: the first call allocates what it needs.
def kbits.of
def kbitsceil(log2 K), for K >= 1.
def Bufs.sizedBuffers for 2^lg keys at fork depth b and k buckets, allocated now.
def fit.pick
def fit.eqt when it holds exactly 2^d entries, else a new one.
def fit.get when it holds at least 2^d entries, else a new one.
type Two
def two.join
def two.rejoin
def zero.gon + 1 zeros from at.
def bump.at
def bumpOne more at t[i].
def count.gor 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.
def rows.leafBlock i (2^e keys from i * 2^e): its row, at i * 2^kb, zeroed, then its keys counted into it.
def rowsPass 1's forks: d levels down to the blocks under block index i.
def smalld is below 12: the table is small, and its rows are not split.
def col.gor 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 ins.goAs col.go, but each entry becomes the sum through it (in place).
def grp.put
def grp.oneColumn 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.goColumns c to c + n of a group.
def grp.leafLane i: rows group i / 2^gc (2^m rows of 2^kb), columns group i % 2^gc (2^w columns).
def grpPass 2a's forks (sort.bend's too, with sc): d levels down to the lanes under lane i, with two handles to the table.
def col.put
def col.oneColumn 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 cols.goColumns c to c + n.
def colsPass 2b's forks: d levels down to groups of 2^w columns under group index j.
def count.fin
def count.colsPass 2b over the 2^kb columns, 2^min(d, kb) groups: each sums its columns over the 2^r groups' last rows.
def count.grpPass 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.at
def countThe histogram of keys into k buckets at fork depth b.

scan.bend

def sum.gor holds the array and the entry x read at j: adds x and the n entries after it to s.
def ex.gor 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.
def in.goAs ex.go, but a[j] becomes the sum through it.
def goThe scan of the n + 1 entries from j, from base s.
type Two
def two.join
def two.rejoinA leaf's spare handles, joined back after its work.
def sums.leaf.fin
def sums.leafBlock i (2^e entries): its sum into s[i].
def sumsPass 1's forks: d levels down to the leaves under leaf index i.
def puts.leaf.fin
def puts.leaf.at
def puts.leafBlock i: its scan in place, from its base s[i].
def putsPass 3's forks, shaped as pass 1's.
def halffloor(d / 2).
def run.fin
def run.midPass 3, from pass 2's bases and total.
def run.prePass 1 over a (2^lg entries) at depth d, into a new s.
def run0.sumsThe scan with pass 2 on one lane.
def run0
def run1.sumsThe scan with pass 2 by run0 at depth d / 2.
def run.pickPass 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
def exclusivea[j] becomes a[0] + ..
def inclusivea[j] becomes a[0] + ..

sort.bend

type Bufs
def Bufs.newEmpty buffers: the first call allocates what it needs.
def Bufs.sizedBuffers for 2^lg keys at fork depth b and k buckets, allocated now.
type Three
def three.join
def three.rejoin
def xs.gor 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 sum.put
def sum.colThe nb + 1 entries from at, step apart: their sum; when wr, each also becomes the sum of those before it.
def sum.oneColumn 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.
def sum.goColumns c to c + n.
def sumsPass 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.
def base.fin
def base.gor 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.atA 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.os
def base.oneColumn 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.colsColumns c to c + n of a group.
def base.leafLane i: rows group i / 2^gc, columns group i % 2^gc (as Hist.grp.leaf).
def basesPass 2c's forks, shaped as pass 2a's (Hist.grp), with two handles each to the table and the offsets.
def fwd.gor 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.at
def fwd.oneColumn c, when c < K: its entries from its first slot offs[c].
def fwd.colsColumns c to c + n.
def fwdsThe forks, shaped as pass 2b's, with two handles each to the table and the offsets.
def put.at
def put.oneKey j, whose bucket's next slot is t[slot]: perm[that slot] <- j, and the slot moves on.
def put.fin
def put.gor 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.
def puts.leafBlock i (2^e keys from i * 2^e, its row at i * 2^kb).
def putsPass 3's forks: d levels down to the blocks under block i, with two handles each to the keys, the table and perm.
def run.fin
def run.putsPass 3.
def run.basesPass 2c: by fwds when lo (a small table), else by bases.
def run.scanPass 2b's scan: offs becomes its exclusive scan.
def run.totsPass 2b, after 2a (t): over the 2^h groups' last rows.
def run.sumsPass 2a: each group's running column sums (Hist.grp), then 2b.
def runPass 1.
type MovedA gather's arrays: the permutation, the source and the destination.
type Sd
def gat.at