Skip to content

Scheduling

Scheduling turns a high-level Node DAG into executable kernel work. The entry point is schedule(SINK(...)), and the pass sequence lives in ren/engine/schedule.py. Read Engine overview or Execution pipeline first if you want the wider realization path before the scheduler details.

Pass shape

Ren runs these scheduler passes:

Step Purpose
Simplify Algebra, ring rules, constants, and copies.
Lower high-level ops Lower high-level ring ops such as ROTATE.
Prepare domains and functions Insert required NTT or INTT, remove redundant conversions, and lower FUNCTION to CALL.
Parameterize the root Replace concrete buffers with positional PARAM nodes under one outer CALL.
Reuse the schedule Cache lowering by the parameterized SINK body and active rules.
Plan materialization Choose nodes that need buffers.
Lower storage Convert BUFFERIZE(x) into a storage view or ALLOC, STORE, and AFTER.
Lower ring ops Enforce ring-specific reductions and conversions.
Lower constants Give ring constants explicit coefficient or NTT semantics.
Indexify Convert elementwise work into GIDX, INDEX, LOAD, STORE.
Kernelize Parameterize top-level stores and wrap them in CALL nodes.
Bind scheduled calls Expand nested schedules and bind current inputs and fresh intermediates.
Linearize Order executable calls under LINEAR, then discard ordering edges from buffer bindings.
Build becomes_map Map lazy outputs to their concrete output bindings.

Each pass fixes representation decisions needed by later passes. Preparation resolves argument domains before preparing each function body and lowering it to a CALL. The same pass then places the function's resolved outputs in the domains its callers require. Materialization and lowering run only on a schedule-cache miss, then the outer CALL binds the current buffers and fresh outputs.

Trace scheduler rewrites

schedule(...) accepts a trace callback. This example records a small summary of pass-level replacements.

Tracing records passes that actually run. A schedule-cache hit returns the cached lowering without replaying the original lowering events.

from ren.engine.schedule import schedule
from ren.ir.node import Node
from ren.poly import Poly
from ren.ring import RingSpec


ring = RingSpec(n=8, moduli=(17, 97))

x = Poly([1, 2, 3, 4, 0, 0, 0, 0], ring)
y = Poly([4, 3, 2, 1, 0, 0, 0, 0], ring)

expr = (x + y) * 2
root = Node.sink(expr.node)

events: list[tuple[str | None, str, str]] = []


def trace(pass_name: str | None, before: Node, after: Node) -> None:
    if before is after:
        return
    events.append((pass_name, before.op.name, after.op.name))


linear, becomes_map = schedule(root, trace=trace)

print("initial root:", root.op.name)
print("scheduled root:", linear.op.name)
print("materialized outputs:", [node.base.op.name for node in becomes_map.values()])
print("rewrite events:", len(events))
for pass_name, before, after in events[:8]:
    print(f"{pass_name}: {before} -> {after}")
initial root: SINK
scheduled root: LINEAR
materialized outputs: ['BUFFER']
rewrite events: 82
prepare: ADD -> NTT
prepare: AS_RING -> NTT
prepare: NTT -> AS_RING
prepare: MUL -> MUL
prepare: MUL -> MUL
prepare: SINK -> SINK
callify: SINK -> CALL
bufferize: MUL -> BUFFERIZE

The example schedules (x + y) * 2. The scalar 2 enters as a ring constant. Ren treats this as a normal MUL, so domain injection gives both operands NTT-domain semantics before constant lowering turns 2 into its NTT broadcast form. The bufferize: MUL -> BUFFERIZE row marks the multiplication's output for storage.

The trace stays compact by design. To debug a scheduling issue, filter by pass name first, then inspect the graph before and after that pass.

Materialization

Ren materializes values that need buffer identity. Common boundaries are:

  • final outputs;
  • conversion operations;
  • explicit contiguous() requests;
  • stores and copies;
  • views over realized sources that must remain addressable.

The AFTER node is a dependency edge. It keeps ordering explicit while letting the value continue to behave like the buffer it wraps.

Kernelization

Kernelization replaces buffer references in a store body with positional PARAM nodes. The CALL keeps the lowered body in src[0] and its buffer bindings in the remaining sources.

Compute kernels use this shape:

CALL(
  SINK(STORE(INDEX(PARAM(0), GIDX), value)),
  buffers...
)

Copies use the same CALL shape with lightweight non-compute bodies. Views remain buffer expressions; explicit copies of views still write their destination buffers. All executable calls are collected in execution order under LINEAR.

The outer eager graph and each @ren.function body use the same parameterized schedule cache. It retains the lowered graph with its output expressions and dependency edges. The scheduler binds inputs and fresh allocations for each invocation, expands nested calls, then builds one LINEAR sequence.

Scheduler terms

Term Meaning
SINK Single root node used to schedule one or more requested outputs together.
BUFFERIZE Temporary marker saying a value needs buffer identity.
ALLOC Temporary storage request, bound to a fresh buffer for each invocation.
STORE Store a computed value into a buffer.
AFTER Dependency edge that preserves ordering while returning the wrapped value.
GIDX Global element index used after elementwise work is indexified.
INDEX Read a logical element from a node at an index.
LOAD Load from a buffer slot during indexed lowering.
PARAM Positional buffer parameter in a function or lowered call body.
FUNCTION Unscheduled invocation of a reusable high-level body.
CALL Executable body plus concrete buffers in parameter order.
LINEAR Ordered sequence of executable calls.

Files to read