parallel自动生成

本页由源码自动生成

数据来自 entelechy serve + {"op":"kernels"} / {"op":"kernel"} · packages/parallel.entpkg/kernels/*.ent。下方的详细描述保留源码中的英文原文。

分类：包 · 清单：use "kernels/";

简述

其他包依赖的数据并行算法：整数键稳定排序、压缩、按所有者布局、连通分量。

描述

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.

Kernel

Kernel	执行模式	简述
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.

方法

函数	简述
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

图预设

名称	接口	说明
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 说明

parallel.compact_blank@1

What a slot holds when nothing was gathered into it.

执行模式	map
需要能力	field.read, field.write
输入	flags: Rows<Int>
参数	—
输出	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.

执行模式	scatter into input 2 with max
需要能力	field.read, field.write
输入	flags: Rows<Int>, offsets: Rows<Int>, slots: Rows<Int>
参数	—
输出	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.

执行模式	prefix with sum
需要能力	field.read, field.write
输入	flags: Rows<Int>
参数	—
输出	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;.

执行模式	reduce
需要能力	field.read, field.write
输入	flags: Rows<Int>
参数	—
输出	result: Rows<Int>

parallel.components_apart@1

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

执行模式	reduce
需要能力	field.read, field.write
输入	edges: Rows<IVec2>, labels: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	packages/parallel.entpkg/kernels/components.ent

parallel.components_flatten@1

Every node pointed straight at its root.

执行模式	map
需要能力	field.read, field.write
输入	parents: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	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.

执行模式	scatter into input 1 with min
需要能力	field.read, field.write
输入	edges: Rows<IVec2>, parents: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	packages/parallel.entpkg/kernels/components.ent

parallel.components_start@1

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

执行模式	map
需要能力	field.write
输入	—
参数	—
输出	result: Rows<Int>
源码	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].

执行模式	prefix with sum
需要能力	field.read, field.write
输入	counts: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	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.

执行模式	map
需要能力	field.read, field.write
输入	ends: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	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.

执行模式	map
需要能力	field.read, field.write
输入	entries: Rows<Int>
参数	—
输出	result: Rows<Int>
源码	packages/parallel.entpkg/kernels/runs.ent

parallel.sort_blank@1

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

执行模式	map
需要能力	field.read, field.write
输入	keys: Rows<Int>
参数	—
输出	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.

执行模式	map
需要能力	field.read, field.write
输入	keys: Rows<Int>
参数	—
输出	result: Rows<Int>

parallel.sort_next_bit@1

执行模式	map
需要能力	field.read, field.write
输入	previous: Rows<Int>
参数	—
输出	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.

执行模式	scatter into input 4 with max
需要能力	field.read, field.write
输入	order: Rows<Int>, keys: Rows<Int>, bit: Rows<Int>, zeros: Rows<Int>, slots: Rows<Int>
参数	—
输出	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.

执行模式	prefix with sum
需要能力	field.read, field.write
输入	order: Rows<Int>, keys: Rows<Int>, bit: Rows<Int>
参数	—
输出	result: Rows<Int>

测试

components.replay, rows.replay