Reduce

Karray.reduce folds N elements down to one winner using a comparison you write in Python. Kathryn builds a balanced 2:1 tournament tree in hardware: your select function is called once per compared pair, its return value becomes the mux select, and the winner’s fields ripple up the tree as combinational wires. Use it for priority pickers, max/min finders, oldest-entry selection — anything of the shape “scan the table, keep the best”.

Each compared pair is resolved by your select_fn; winners ripple up the tree:

flowchart TB
    E0["elem 0"] --> P0["select_fn(a,b,0)"]
    E1["elem 1"] --> P0
    E2["elem 2"] --> P1["select_fn(a,b,0)"]
    E3["elem 3"] --> P1
    P0 --> F["select_fn(a,b,1)"]
    P1 --> F
    F --> WIN["winner (combinational)"]

winner = karray.reduce(dims, select_fn=None, fields=None, request_index=False)

• dims — one entry per dimension: an int pins the dimension (reduce only that slice), Reduce or Reduce(fn) folds it. At least one dimension must be folded. Reg- or wire-backed Karrays only.
• select_fn — the shared comparison, used by every folded dim that did not bring its own Reduce(fn). A folded dim with no function at all is a TypeError.
• fields — optionally limits which fields are carried up the tree (default: all).
• Returns the winner as a scalar reference — read its fields as winner.field. Each is a combinational wire of the field’s width.

The select function

For every compared pair the function is called as fn(a, b, level), where a and b are ReduceViews and level is the tree layer (0 at the leaves). A ReduceView has:

• .fields — a dict mapping each carried field name to its current signal: a leaf element’s field at level 0, a prior layer’s mux output above.
• .indices — the list of element coordinates this subtree covers.

Return a 1-bit signal; true picks a. The expression you build becomes real combinational logic.

class RegFile(Karray):
    valid = kaf(1)
    data  = kaf(8)

def pick_max(a, b, level):
    return a.fields["data"] >= b.fields["data"]

def pick_valid(a, b, level):
    av, bv = a.fields["valid"], b.fields["valid"]
    ad, bd = a.fields["data"],  b.fields["data"]
    # a wins if a is valid AND (b is invalid OR a.data >= b.data)
    return av & ((~bv) | (ad >= bd))

with seq():
    w_max   = self.rf.reduce([Reduce], pick_max)     # element with max data
    w_valid = self.rf.reduce([Reduce], pick_valid)   # max data among VALID elements

    self.o_dm |= w_max.data
    self.o_dv |= w_valid.data
    self.o_vv |= w_valid.valid       # the winner's other fields come along too

pick_valid shows why the callback style matters: the comparison consumes both fields, so an invalid global maximum loses to the best valid element — logic that a fixed “max by field” primitive could not express (worked example: tc30).

Odd element counts are handled automatically: the unpaired node is carried up to the next layer and compared there.

Folding vs pinning dimensions

On a multi-dimensional array, each entry of dims decides that dimension’s fate:

self.grid = Cell(HwComponentType.REG, (2, 3), "grid")

# pin dim 0 to row 1, fold dim 1: reduce only row 1's three elements
w = self.grid.reduce([1, Reduce], pick_max)

When several dimensions fold, they reduce innermost-first (highest dim index first), and each can carry its own rule via Reduce(fn):

# cols reduce by MAX within each row, then rows reduce by MIN
gwin = self.grid.reduce([
    Reduce(row_min),      # dim 0 (rows)  — applied second
    Reduce(col_max),      # dim 1 (cols)  — applied first (innermost)
])

Winner coordinates: request_index

Knowing which element won is often as important as its value. With request_index=True, reduce returns (winner, coords) — one index signal per folded dimension, in dimension order, each just wide enough for its extent:

gwin, gcoords = self.grid.reduce(
    [Reduce(row_min), Reduce(col_max)], request_index=True)

self.o_gd   |= gwin.data
self.o_grow |= gcoords[0]     # winner row index (1 bit for extent 2)
self.o_gcol |= gcoords[1]     # winner col index (2 bits for extent 3)

Carrying extras between layers

A select function may return (select, {name: signal}) instead of a bare select. The named extras are attached to the merged node and appear in the next layer’s .fields, letting you thread intermediate values up the tree.

This example picks by running sum: each pair’s winner carries the sum of the subtree, and upper layers compare those sums instead of raw data:

def pick_sum(a, b, level):
    asum = a.fields.get("runsum", a.fields["data"])   # seed from data at the leaves
    bsum = b.fields.get("runsum", b.fields["data"])
    return (asum >= bsum), {"runsum": asum + bsum}

rwin = self.rf.reduce([Reduce], pick_sum)

Note the .get(...) with a fallback: leaves have no runsum yet, so the first layer seeds it from data (worked example: tc31).

What gets built

The reduce algorithm — the pairing, the odd-node carry, the extras, the per-dimension coordinates — runs in the Rust core; the Python callback is only invoked to build each pair’s select expression. Everything it produces is combinational: the winner is available in the same cycle its inputs settle. Reading winner.field yields a wire, which you typically latch into an output register with |= inside a flow block.

See tc30 (basic reduce) and tc31 (nested per-dim functions, coordinates, extras) in the Examples Gallery.