Skip to content

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 = 0 gives (M, 0) outputs; K > N pads with (+inf, -1).
  • ±inf is a valid value, not a missing candidate: a +inf term 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 = −inf has zero weight, and a NaN weight on such a term is ignored;
  • a single f = +inf: LOGSUMEXP gives +inf, SUMSOFTMAXWEIGHT NaN, LOGSUMEXPWEIGHT +inf if Σ_{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 the dim contiguous components of the current row, wherever the backend keeps them (registers, shared or local memory, global memory).
  • The returned PairSource has source, name, dialect, scalar_type, out_type, out_fields, out_ctypes, arg_layout (one ArgLayout(param, arg, role, dim) per argument, with C names xi_<n>, yj_<n>, p_<n>), generator_version and sha256. Several plans can share one compilation unit through distinct names.
  • The source defines the helpers kp_pow2/3/4 under the KP_PAIR_HELPERS guard, and INFINITY/NAN in 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, unrequested rsqrt), no implicit FP64 to FP32 conversion. FP64 is refused on a device without FP64 support.
  • FMA contraction. With fp_contract=True, the compiler may contract a*b + c within an expression (NVRTC --fmad=true, hipRTC -ffp-contract=on, icpx -fp-model=precise). With fp_contract=False, no contraction is allowed (--fmad=false, -ffp-contract=off). A backend that cannot guarantee this leaves fp_contract_off unset and the runtime refuses the plan.
  • fast_math. Only exp and log may be approximated, in the formula and in the LOGSUMEXP states and final log. Special values are preserved (exp(−inf) = 0, log(0) = −inf, NaN propagates). The CUDA backend uses ex2.approx.f32 and lg2.approx.f32 without .ftz in 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_e of the LOGSUMEXP family, and are ignored by the other kinds:

    • direct: one accumulator per thread, partial sums added together;
    • block: each tile of T terms is summed into a fresh accumulator, then added to the total; T is published in CompileInfo.options as sum_block=T;
    • kahan: Neumaier compensated summation, state (s, c); insertion t = s + x; c += (|s| ≥ |x|) ? (s − t) + x : (x − t) + s; s = t; merge with TwoSum of the sums plus c1 + c2; result s + c, or s if s is not finite. The LOGSUMEXP rescaling multiplies s and c (and t_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 to direct. - 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, with block summation by default. Results are converted to float16 at the end (±inf beyond 65504). - Constants are rounded once, to nearest even, when the plan is built. Exact rationals are emitted as p/q in the dtype. Overflow, or a non-zero value rounded to zero, raises ConstantConversionError.

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_stream for CUDA and ROCm, torch.xpu.current_stream for XPU). launch performs 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 = 0 and K = 0 are handled by the runtime without calling launch. N = 0 is handled by launch, which writes the identities.
  • No unsupported operation is replaced by a CPU or PyTorch computation: supports answers Support(False, reason) and the runtime raises UnsupportedError before 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
  • CompileInfo publishes the backend, device name, architecture, exact compiler, options, cache hit, compilation time, temporary bytes per launch, source hash and effective variant.
  • inputs maps argument names to tensors; outputs maps the keys of output_shapes to 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 gradient G (an extra input named kp_grad), the core builds an i-side SUM plan with outputs Σ_e G_e ∂F_e/∂x[c] and Σ_e G_e ∂F_e/∂p[c] (the latter summed over i by PyTorch), and a j-side plan, with i and j swapped, for Σ_e G_e ∂F_e/∂y[c]. Gradient plans keep the dtype, acc_dtype, fp_contract, fast_math and sum_scheme of 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) ∂f for LOGSUMEXP. A row with L = −inf has 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_add on the j side; an index −1 contributes nothing.
  • Derivatives come from symox.diff. Heaviside(z) becomes 1, 0 or 1/2 for z > 0, z < 0, z = 0; DiracDelta becomes 0; an unevaluated Derivative raises UnsupportedError. A Piecewise is differentiated branch by branch.
  • With ranges, the i side uses the forward triplet and the j side 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_variant is the heuristic choice of the estimate level. It must be deterministic.
  • variants(..., "measure") returns at most 4 candidates and variants(..., "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_variant and variants, or a compile without a variant parameter) is only used at the estimate level.

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.