Core and backend contract¶
This page describes the rules shared by the kernox core and the GPU backends:
what a backend receives, what it must compute, and how it must behave. It is
written for people working on kernox or on a new backend. Code:
kernox/plan.py and
kernox/backends/base.py.
Changes to these rules are made here first; a backend does not change them on its own.
Layers¶
| Layer | Owner | Content |
|---|---|---|
| Frontend | core (expr.py, ops.py, complex.py) |
Vi, Vj, Param, operators, constants, where, reductions, compile |
| Plan | core (plan.py, builder.py, _plan_key.py) |
immutable, normalized Plan (always a reduction over j) |
| Runtime | core (runtime.py) |
input validation, output allocation, backend selection, batch and ranges layouts, autotuning |
| Gradients | core (autograd.py) |
gradient plans, run by the same backend |
| Pair function | core (codegen/pair.py) |
scalar device function generated by symox for each dialect |
| Oracle | core (oracle.py) |
blockwise PyTorch reference on the CPU |
| Reduction kernel | backends (backends/{cuda,hip,sycl}/) |
tiling, accumulators, launch, compilation cache |
Backends only consume the plan module. They never depend on the frontend classes.
The plan¶
A Plan describes one fused reduction completely:
| Field | Meaning |
|---|---|
args |
ordered arguments: i arguments, then j, then parameters, each group sorted by name; each has a name, a role, a dim and its component symbols |
outputs |
scalar symox expressions, one per output component (boolean for COUNT) |
reduction |
kind (below), and k for the K-nearest kinds |
dtype |
float16, float32 or float64: inputs and formula evaluation |
acc_dtype |
accumulator of SUM and of the LOGSUMEXP family (see dtypes) |
fp_contract |
FMA contraction allowed within an expression (default True) |
fast_math |
approximate exp and log allowed (default False) |
sum_scheme |
direct, block or kahan |
batch_rank |
number of leading batch dimensions of the inputs (0 without batch) |
ranges |
True for a block-sparse reduction |
meta |
frontend information, outside the key (for example whether i and j were swapped) |
The frontend normalizes a reduction over i by swapping the roles, so
backends only implement reductions over j. A plan needs at least one i
argument and one j argument. plan.key() is a stable hash of everything that
affects the generated code; batch_rank, ranges and a non-default
sum_scheme only enter it when they are set.
Reductions¶
| Kind | Outputs for M rows | Definition |
|---|---|---|
SUM |
(M, D) |
Σ_j f_d |
COUNT |
(M, D) int64 |
number of j where the boolean f_d holds |
MIN, MAX |
(M, D) |
extremum per component |
ARGMIN, ARGMAX |
(M, D) int64 |
index of the extremum |
MIN_ARGMIN, MAX_ARGMAX |
value (M, D) and index (M, D) |
both from the same pass |
KMIN, ARGKMIN, KMIN_ARGKMIN |
(M, K) |
the K smallest values of a scalar f, their indices, or both |
LOGSUMEXP |
(M, D) |
log Σ_j exp f_d |
SUMSOFTMAXWEIGHT |
(M, E) |
outputs (f, g_1..g_E): Σ_j exp(f) g_e / Σ_j exp(f) |
LOGSUMEXPWEIGHT |
(M, E) |
outputs (f, g_1..g_E): log Σ_j exp(f) g_e |
Output shapes and dtypes come from output_shapes(plan, m, batch). SUM and
the LOGSUMEXP family return acc_dtype, except FP16 plans, which return
float16 (accumulated_output_dtype(plan)).
Semantics¶
| Kind | Identity (N = 0) | Ties | NaN |
|---|---|---|---|
| SUM | 0 | propagated | |
| COUNT | 0 | a comparison with NaN is false | |
| MIN / MAX | +inf / -inf |
NaN candidate ignored | |
| ARGMIN / ARGMAX | -1 |
smallest j |
ignored; -1 without candidate |
| MIN_ARGMIN / MAX_ARGMAX | (±inf, -1) |
as ARGMIN | as MIN and ARGMIN |
| KMIN / ARGKMIN | padding (+inf, -1) |
lexicographic order (value, j) |
ignored |
| LOGSUMEXP | -inf |
propagated | |
| SUMSOFTMAXWEIGHT | NaN (0/0) | propagated | |
| LOGSUMEXPWEIGHT | -inf |
propagated |
- K outputs are sorted by increasing value, ties by increasing index.
K = 0gives(M, 0)outputs;K > Npads with(+inf, -1). ±infis a valid value, not a missing candidate: a+infterm can be returned with an index≥ 0.- Indices are int64 and never stored as floating point. COUNT accumulates in int64.
- The summation order of SUM is not specified; tests use a tolerance relative to the L1 norm of the terms.
The LOGSUMEXP family¶
All three kinds use a single pass with a running maximum. The state per row
and per component is (m, s), plus t_1..t_E for the weighted kinds, in
acc_dtype. Inserting a term, or merging two states (tiles, split ranges):
m' = max(m1, m2)
s = s1·exp(m1 − m') + s2·exp(m2 − m') (t_e likewise)
with exp(−inf − (−inf)) = 0, so the empty state (−inf, 0) is neutral.
Results: m + log s (LOGSUMEXP), t_e / s (SUMSOFTMAXWEIGHT),
m + log t_e (LOGSUMEXPWEIGHT). Special values:
- a term with
f = −infhas zero weight, and a NaN weight on such a term is ignored; - a single
f = +inf: LOGSUMEXP gives+inf, SUMSOFTMAXWEIGHT NaN, LOGSUMEXPWEIGHT+infifΣ_{f=+inf} g_e > 0, NaN otherwise; - negative weights make LOGSUMEXPWEIGHT NaN, like
log; - a NaN
f, or a NaN weight with non-zero weight, propagates.
The pair function¶
kernox.codegen.pair.pair_function(plan, dialect, name=..., out_type=...)
generates an inline device function, independent of the kernel strategy:
// cuda/hip: __device__ __forceinline__ ; sycl: inline
struct kp_out { T o0; ...; T o{D-1}; }; // bool for COUNT
kp_out kp_pair(const T* __restrict__ xi_0, ..., // one pointer per i argument
const T* __restrict__ yj_0, ..., // one pointer per j argument
const T* __restrict__ p_0, ...); // one pointer per parameter
- Arguments follow
plan.args. Each pointer designates thedimcontiguous components of the current row, wherever the backend keeps them (registers, shared or local memory, global memory). - The returned
PairSourcehassource,name,dialect,scalar_type,out_type,out_fields,out_ctypes,arg_layout(oneArgLayout(param, arg, role, dim)per argument, with C namesxi_<n>,yj_<n>,p_<n>),generator_versionandsha256. Several plans can share one compilation unit through distinctnames. - The source defines the helpers
kp_pow2/3/4under theKP_PAIR_HELPERSguard, andINFINITY/NANin CUDA and HIP if they are missing. Backends must not redefine these names. SYCL needs<sycl/sycl.hpp>included before the source. - Constants are emitted in the plan's dtype. The generator never enables fast-math and never converts FP64 to FP32.
Common subexpressions and where¶
Repeated subexpressions are computed once. With where (a symox
Piecewise), the elimination works by region: a common subexpression is
hoisted (evaluated unconditionally) if it is already evaluated outside any
branch, or if it appears in at least two different regions; otherwise it stays
inside its branch.
This is valid because the pair function is pure and GPUs do not trap on
floating-point exceptions: evaluating a subexpression outside its domain gives
NaN or ±inf without stopping the kernel, and only the branches that use it
read the value. The result is always that of the active branch. Calls to
functions other than the kp_pow* helpers are never hoisted. The cost is at
most one speculative evaluation per shared temporary.
Numerical rules¶
- IEEE by default. No fast-math, no reassociation, no flush-to-zero, no
TF32, no approximate functions (
__expf, unrequestedrsqrt), no implicit FP64 to FP32 conversion. FP64 is refused on a device without FP64 support. - FMA contraction. With
fp_contract=True, the compiler may contracta*b + cwithin an expression (NVRTC--fmad=true, hipRTC-ffp-contract=on, icpx-fp-model=precise). Withfp_contract=False, no contraction is allowed (--fmad=false,-ffp-contract=off). A backend that cannot guarantee this leavesfp_contract_offunset and the runtime refuses the plan. fast_math. Onlyexpandlogmay be approximated, in the formula and in the LOGSUMEXP states and finallog. Special values are preserved (exp(−inf) = 0,log(0) = −inf, NaN propagates). The CUDA backend usesex2.approx.f32andlg2.approx.f32without.ftzin float32; float64 is unchanged and float16 is refused. A backend must refuse the flag rather than ignore it. The oracle stays IEEE.-
Summation schemes apply to SUM and to the sums
s,t_eof the LOGSUMEXP family, and are ignored by the other kinds:direct: one accumulator per thread, partial sums added together;block: each tile ofTterms is summed into a fresh accumulator, then added to the total;Tis published inCompileInfo.optionsassum_block=T;kahan: Neumaier compensated summation, state(s, c); insertiont = s + x; c += (|s| ≥ |x|) ? (s − t) + x : (x − t) + s; s = t; merge with TwoSum of the sums plusc1 + c2; results + c, orsifsis not finite. The LOGSUMEXP rescaling multipliessandc(andt_e,c_e).
No compiler option may destroy the compensation. A backend lists the schemes it implements in
sum_schemes; the runtime refuses the others instead of falling back todirect. - FP16. The formula is evaluated in binary16, each operation rounded. Accumulators default to float32 for SUM and the LOGSUMEXP family;acc_dtype="float16"gives half accumulation, withblocksummation by default. Results are converted to float16 at the end (±infbeyond 65504). - Constants are rounded once, to nearest even, when the plan is built. Exact rationals are emitted asp/qin the dtype. Overflow, or a non-zero value rounded to zero, raisesConstantConversionError.
Execution rules¶
- Inputs are already validated by the runtime: same device, dtype
plan.dtype, conforming shapes, contiguous (except batch dimensions). Backends re-check cheaply whatever native memory safety depends on. - The kernel runs on the current PyTorch stream of the device
(
torch.cuda.current_streamfor CUDA and ROCm,torch.xpu.current_streamfor XPU).launchperforms no host synchronization and no host copy. - No M×N matrix is materialized. Temporaries are bounded, allocated through
PyTorch on the same device and stream, and their size is published in
CompileInfo.temp_bytes_per_launch. M = 0andK = 0are handled by the runtime without callinglaunch.N = 0is handled bylaunch, which writes the identities.- No unsupported operation is replaced by a CPU or PyTorch computation:
supportsanswersSupport(False, reason)and the runtime raisesUnsupportedErrorbefore any launch.
Backend interface¶
A backend is a module kernox.backends.<name> exposing get_backend(), or an
object registered with kernox.register_backend(name, factory). A missing
backend raises BackendUnavailableError; there is no fallback.
class Backend:
name: str
fp_contract_off: bool # can compile without FMA contraction (absent: False)
sum_schemes: tuple # implemented schemes (absent: ("direct",))
batch: bool # accepts launch(..., batch=BatchLayout) (absent: False)
ranges: bool # accepts launch(..., ranges=RangesLayout) (absent: False)
supports(plan, device) -> Support
default_variant(plan, device, sizes: Sizes) -> Variant
variants(plan, device, sizes: Sizes, effort: str) -> list[Variant]
compile(plan, device, variant: Variant | None = None) -> CompiledReduction
device_identity(device) -> dict # optional, for wisdom
class CompiledReduction:
info: CompileInfo
launch(inputs: dict, outputs: dict, **layouts) -> None
CompileInfopublishes the backend, device name, architecture, exact compiler, options, cache hit, compilation time, temporary bytes per launch, source hash and effective variant.inputsmaps argument names to tensors;outputsmaps the keys ofoutput_shapesto tensors preallocated by the core.
Batch dimensions¶
For a plan with batch_rank > 0, the runtime calls
launch(inputs, outputs, batch=BatchLayout). Inputs keep their shapes
(*B, L, d) and their batch strides (any value, including 0); their last two
dimensions are contiguous. BatchLayout carries, per argument, an int64 table
of nb offsets in elements relative to data_ptr, on the device (offsets)
and on the host (host_offsets, for references only). Outputs are contiguous
(nb, M, ...). Each batch element is an independent reduction with local
indices.
Block-sparse ranges¶
For a plan with ranges=True, the runtime calls
launch(inputs, outputs, ranges=RangesLayout). The layout holds a device work
list of tiles (i0, i1, k0, k1) of height at most tile_m (published by the
compiled object as ranges_tile_m) and the reduced intervals redranges.
A tile reduces its rows over ∪ redranges[k0:k1]; rows covered by no tile
receive the identity, written by launch. Ties go to the smallest j
whatever the order of the intervals. Batch and ranges together are refused.
Gradients¶
Gradients need nothing new from backends: they are ordinary plans built by the core and compiled by the same backend.
- SUM. For
out[i, e] = Σ_j F_e(x_i, y_j, p)and an upstream gradientG(an extra input namedkp_grad), the core builds ani-side SUM plan with outputsΣ_e G_e ∂F_e/∂x[c]andΣ_e G_e ∂F_e/∂p[c](the latter summed overiby PyTorch), and aj-side plan, withiandjswapped, forΣ_e G_e ∂F_e/∂y[c]. Gradient plans keep thedtype,acc_dtype,fp_contract,fast_mathandsum_schemeof the forward plan, and are themselves differentiable. - LOGSUMEXP family (first order): the gradient is a SUM plan in which the
forward output is a fixed input, for example
Σ_j exp(f − L) ∂ffor LOGSUMEXP. A row withL = −infhas a zero gradient. - MIN, MAX, KMIN and the values of the combined kinds (first order): the
derivatives are evaluated by PyTorch at the selected pairs only (O(M·K)),
with
scatter_addon thejside; an index−1contributes nothing. - Derivatives come from
symox.diff.Heaviside(z)becomes 1, 0 or 1/2 forz > 0,z < 0,z = 0;DiracDeltabecomes 0; an unevaluatedDerivativeraisesUnsupportedError. APiecewiseis differentiated branch by branch. - With ranges, the
iside uses the forward triplet and thejside the transposed one (an explicit error if it is missing).
Kernel variants and autotuning¶
A backend may offer several kernel variants (Variant(name, params), with
JSON-serializable parameters). All variants of a plan have exactly the same
semantics, dtypes, accumulator, fast-math and contraction settings; only the
order of floating-point additions may differ.
default_variantis the heuristic choice of theestimatelevel. It must be deterministic.variants(..., "measure")returns at most 4 candidates andvariants(..., "patient")at most 32, default first. Longer lists are truncated by the core. Candidates invalid on the device are excluded.- A backend without variants (no
default_variantandvariants, or acompilewithout avariantparameter) is only used at theestimatelevel.
The core does the measuring: on the real inputs of the call, outputs in
temporary tensors, compilation excluded from timing, 1 warm-up then 5 timed
launches with GPU events, within a time budget (2 s for measure, 30 s for
patient). A decision is stored only if the spread (max − min)/median of
each of the two best candidates is at most 25%. Size classes are half-octaves
of (M, N, nb, 1/ρ) (nb batch elements, ρ density of the ranges).
The wisdom key combines plan.key(), the backend, the device identity (from
device_identity, or else from the default variant's CompileInfo), the
PyTorch device fingerprint (name, UUID, runtime version), the generator
version and the size class.
Compilation cache¶
Each backend keeps a disk cache keyed by plan.key(), the generator version,
the compiler and its exact version, the options, the architecture and the
variant. Files are written atomically (temporary file, then rename), and
concurrent compilations of the same key are serialized by a file lock, so N
processes compile a kernel once.