parallelGenerated

Generated from the source

Data comes from entelechy serve + {"op":"kernels"} / {"op":"kernel"} · packages/parallel.entpkg/kernels/*.ent.

Category: Packages · Manifest: use "kernels/";

Brief

The data-parallel algorithms other packages build on.

Description

The data-parallel algorithms other packages build on: a stable sort of integer keys, the compaction of flagged rows, runs of entries laid out by owner, and the connected components of nodes joined by edges.

Layer: Foundation. Uses: no other package.

use "parallel.entpkg";

Kernels

• kernels/compact.ent — Stream compaction, the three steps, over a row of flags where a non-zero flag keeps that element’s index. Kernels: parallel.compact_blank@1, parallel.compact_offsets@1, parallel.compact_total@1, parallel.compact_gather@1.
• kernels/components.ent — Connected components: the nodes an edge joins share a label, the least index of their component, found by hooking roots under roots and flattening the trees, a few passes. Kernels: parallel.components_start@1, parallel.components_hook@1, parallel.components_flatten@1, parallel.components_apart@1.
• kernels/runs.ent — Runs. Kernels: parallel.runs_ends@1, parallel.runs_entries@1, parallel.runs_slots@1.
• kernels/sort.ent — A permutation that puts a row of integer keys in order. Kernels: parallel.sort_identity@1, parallel.sort_blank@1, parallel.sort_next_bit@1, parallel.sort_zeros@1, parallel.sort_place@1.

Graph presets

• graphs/compact.esn — Filters a row, stream compaction.
• graphs/components.esn — Connected components: every node’s label, the least index of the nodes the edges join it to.
• graphs/components_pass.esn — One pass of components.esn.
• graphs/runs.esn — Runs.
• graphs/sort.esn — The permutation that orders keys, least significant bit first.
• graphs/sort_pass.esn — One bit of the sort.

Tests

tests/ holds scenes and their replays, run on every backend: components.replay, rows.replay. Every Kernel of the package is reached by one of them.

Used by the culled, physics, surface, swarm examples.

Kernels

Kernel	Mode	Brief
parallel.compact_blank@1	map	What a slot holds when nothing was gathered into it.
parallel.compact_gather@1	scatter into input 2 with max	Every kept element’s index, written where its rank says. An address outside the target is dropped, so a flag of zero sends its index to -1 and nothing lands.
parallel.compact_offsets@1	prefix with sum	The rank of each kept element: an inclusive prefix sum, so a kept element at i belongs at offsets[i] - 1.
parallel.compact_total@1	reduce	How many were kept, as a row of one, which is what a domain reads: domain = value(count) * per_thing;.
parallel.components_apart@1	reduce	How many edges still join two labels: none once the passes were enough.
parallel.components_flatten@1	map	Every node pointed straight at its root.
parallel.components_hook@1	scatter into input 1 with min	The larger root of each edge’s ends hooked under the smaller. An edge with an end outside the nodes (-1) joins nothing.
parallel.components_start@1	map	Every node its own component; the node’s domain is how many nodes.
parallel.runs_ends@1	prefix with sum	Where each owner’s run ends: an inclusive prefix sum of the counts, so owner i’s run is ends[i] - counts[i] up to ends[i].
parallel.runs_entries@1	map	How many entries the runs hold, as a row of one that a domain reads (domain = value(entries)): at least one, so the row they are laid in is never empty.
parallel.runs_slots@1	map	The row the runs are laid in, every slot -1 until a scatter fills it with max: an entry is never negative, so a slot is what landed in it or the -1 that says nothing did.
parallel.sort_blank@1	map	The row a pass scatters into, as long as the keys.
parallel.sort_identity@1	map	Where every element starts: at its own place. The keys are bound for their extent — a node with no domain of its own runs over its first input’s — and never read.
parallel.sort_next_bit@1	map
parallel.sort_place@1	scatter into input 4 with max	Every element to its place: a zero at this bit lands at its rank among the zeros, a one behind all of them at its rank among the ones. Each place is written by exactly one element, so the rule is free, and max over integers is the one that costs a device a single pass of atomics.
parallel.sort_zeros@1	prefix with sum	How many elements with a zero at this bit stand at or before each place. The rank is the whole of what a stable radix pass needs, and an integer sum folds in any grouping, so a device blocks it.

Methods

Function	Brief
components_root(parents: Rows<Int>, i: Int) -> Int	The root of node i: its parents walked until one is its own. The walk may take as many steps as there are nodes, so a parent row of any shape gives a root, never a node part way up.
owner(e: Int, ends: Rows<Int>) -> Int

Graph presets

Name	Interface	Description
compact	input flags: Rows<Int> output indices <- gathered.result output count <- total.result	Filters a row, stream compaction: flags in (non-zero keeps an element), the kept elements’ indices gathered to the front and their count out. Place it with node kept: graph “parallel.entpkg/graphs/compact.esn” { flags <- visible.result; } and size what does the work with domain = value(count) * per_thing; reading kept.indices to know which thing each element belongs to.
components	input edges: Rows<IVec2> input labels: Rows<Int> param passes: Int = 12 output labels <- joined.labels output apart <- apart.result	Connected components: the label of every node, the least index of the nodes edges join it to, given the nodes each their own label (parallel.components_start@1, its domain the number of nodes). Place it with node start: parallel.components_start@1 { domain = 4096; } node parts: graph “parallel.entpkg/graphs/components.esn” { edges <- joined.result; labels <- start.result; } An edge with an end of -1 joins nothing, so a row of edges may hold one place for each edge there could be. apart counts the edges still joining two labels: zero when passes were enough. A path through 131072 nodes in scrambled order takes 8.
components_pass	input edges: Rows<IVec2> input labels: Rows<Int> output labels <- flat.result	One pass of components.esn: the roots hooked, then flattened.
runs	input counts: Rows<Int> output ends <- ends.result output entries <- entries.result output slots <- slots.result	Runs: from each owner’s count of entries, where each owner’s run ends, how many entries there are, and the row of -1 they are laid in. Place it with node lists: graph “parallel.entpkg/graphs/runs.esn” { counts <- counted.result; } and fill lists.slots with a scatter over the owners that walks what the count walked, emitting each entry at ends[i] - counts[i] plus its rank; size what reads the entries with domain = value(entries) and find an entry’s owner with owner(e, ends).
sort	input keys: Rows<Int> param bits: Int = 16 output result <- sorted.result	The permutation that orders keys, least significant bit first. Place it with node order: graph “parallel.entpkg/graphs/sort.esn” { keys <- cell.result; bits = 12; } and read a row through it: at(bodies, at(order, slot)). bits is how many bits of the key matter, 1 to 31; the keys must be non-negative and below 2^bits.
sort_pass	input order: Rows<Int> input keys: Rows<Int> input bit: Rows<Int> input slots: Rows<Int> output result <- placed.result output step <- next.result	One bit of the sort: the rank of the zeros, then every element to its place. sort.esn places this once a bit, carrying both the permutation and the bit it is on.

Kernel descriptions

parallel.compact_blank@1

What a slot holds when nothing was gathered into it.

Mode	map
Requires	field.read, field.write
Inputs	flags: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.compact_gather@1

Every kept element’s index, written where its rank says. An address outside the target is dropped, so a flag of zero sends its index to -1 and nothing lands.

The rule is max and not last because a rank is unique: no two kept elements have the same one, so no slot is written twice and every rule agrees. It is worth choosing: last means the greatest source wins, which no invocation can know until every other one is done, so a backend writes the winners with atomics in one pass and gathers their values in another. max over integers is one pass of atomics and nothing else — a million sources go 1.30 ms to 0.96, four thousand 0.41 to 0.35. blank fills the slots with -1 and an index is never negative, so the maximum of a slot is what landed in it or the -1 that says nothing did.

Mode	scatter into input 2 with max
Requires	field.read, field.write
Inputs	flags: Rows<Int>, offsets: Rows<Int>, slots: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.compact_offsets@1

The rank of each kept element: an inclusive prefix sum, so a kept element at i belongs at offsets[i] - 1.

prefix with sum and not scan: a scan is ordered work — each step reads what the step before it left, so one thread walks the row — and a sum of integers does not need that order. Saying the rule instead of writing the carry lets a backend fold the row in whatever grouping it likes, which is how a device does this in three passes over blocks rather than in one invocation walking every element.

Mode	prefix with sum
Requires	field.read, field.write
Inputs	flags: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.compact_total@1

How many were kept, as a row of one, which is what a domain reads: domain = value(count) * per_thing;.

Mode	reduce
Requires	field.read, field.write
Inputs	flags: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.components_apart@1

How many edges still join two labels: none once the passes were enough.

Mode	reduce
Requires	field.read, field.write
Inputs	edges: Rows<IVec2>, labels: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/components.ent

parallel.components_flatten@1

Every node pointed straight at its root.

Mode	map
Requires	field.read, field.write
Inputs	parents: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/components.ent

parallel.components_hook@1

The larger root of each edge’s ends hooked under the smaller. An edge with an end outside the nodes (-1) joins nothing.

Mode	scatter into input 1 with min
Requires	field.read, field.write
Inputs	edges: Rows<IVec2>, parents: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/components.ent

parallel.components_start@1

Every node its own component; the node’s domain is how many nodes.

Mode	map
Requires	field.write
Inputs	—
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/components.ent

parallel.runs_ends@1

Where each owner’s run ends: an inclusive prefix sum of the counts, so owner i’s run is ends[i] - counts[i] up to ends[i].

Mode	prefix with sum
Requires	field.read, field.write
Inputs	counts: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/runs.ent

parallel.runs_entries@1

How many entries the runs hold, as a row of one that a domain reads (domain = value(entries)): at least one, so the row they are laid in is never empty.

Mode	map
Requires	field.read, field.write
Inputs	ends: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/runs.ent

parallel.runs_slots@1

The row the runs are laid in, every slot -1 until a scatter fills it with max: an entry is never negative, so a slot is what landed in it or the -1 that says nothing did.

Mode	map
Requires	field.read, field.write
Inputs	entries: Rows<Int>
Params	—
Outputs	result: Rows<Int>
Source	packages/parallel.entpkg/kernels/runs.ent

parallel.sort_blank@1

The row a pass scatters into, as long as the keys.

Mode	map
Requires	field.read, field.write
Inputs	keys: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.sort_identity@1

Where every element starts: at its own place. The keys are bound for their extent — a node with no domain of its own runs over its first input’s — and never read.

Mode	map
Requires	field.read, field.write
Inputs	keys: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.sort_next_bit@1

Mode	map
Requires	field.read, field.write
Inputs	previous: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.sort_place@1

Every element to its place: a zero at this bit lands at its rank among the zeros, a one behind all of them at its rank among the ones. Each place is written by exactly one element, so the rule is free, and max over integers is the one that costs a device a single pass of atomics.

Mode	scatter into input 4 with max
Requires	field.read, field.write
Inputs	order: Rows<Int>, keys: Rows<Int>, bit: Rows<Int>, zeros: Rows<Int>, slots: Rows<Int>
Params	—
Outputs	result: Rows<Int>

parallel.sort_zeros@1

How many elements with a zero at this bit stand at or before each place. The rank is the whole of what a stable radix pass needs, and an integer sum folds in any grouping, so a device blocks it.

Mode	prefix with sum
Requires	field.read, field.write
Inputs	order: Rows<Int>, keys: Rows<Int>, bit: Rows<Int>
Params	—
Outputs	result: Rows<Int>

Tests

components.replay, rows.replay