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:
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¶
ren/engine/schedule.py: pass order, function expansion, and call extraction.ren/engine/rules/callify.py: function preparation rules, root parameterization, and call binding.ren/engine/rules/indexing.py: materialization planning, view planning, and index lowering.ren/engine/rules/domain.py: domain requirements and injected conversions.ren/engine/rules/kernelize.py: parameterization and call construction.ren/kernel.py: compute-kernel metadata.- Runtime for the next step after scheduling.