Execution pipeline¶
Connect lazy Poly graphs to the scheduler, memory planner, backend, and JIT capture/replay paths. Read Engine overview first if you need the shorter map.
JIT wraps the same realization machinery with a capture path on cache miss and a replay path on cache hit:
Eager realization schedules, plans, lowers, and runs the lazy graph each time a concrete value is needed. JIT capture uses that same realization machinery on a cache miss while recording scheduled CALLs; replay skips scheduling and lowering for the captured computation when the input specs match a captured plan.
Lazy graph¶
Poly wraps a Node. Poly operations add nodes without launching backend kernels.
a + b,a - b, anda * bcreate arithmetic nodes.a.ntt()anda.intt()create domain conversion nodes.a.to_quotient_ring(ring)anda.lift_to_ring(ring)create aTO_RINGnode, which may become either a real conversion or a buffer view.a.rescale(moduli)creates aRESCALEnode.a.rotate(k)creates a high-levelROTATEnode that is lowered later.a.to(device)creates aCOPYnode.
A Node has an Op, a dtype, zero or more sources in src, and optional operation metadata in arg. Nodes form a DAG, not a tree. If the same polynomial expression is reused, downstream nodes can point at the same producer node.
Ring semantics live on metadata nodes. AS_RING attaches a RingSpec and a domain to storage or computation: Domain.COEFF means coefficient representation, and Domain.NTT means NTT representation.
Creation¶
Creating a public polynomial from coefficients stores the input coefficient limbs in a Python buffer, then converts them into the ring's Montgomery RNS basis with TO_RNS:
coefficients
-> packed u32 limb array
-> BUFFER(device="python")
-> TO_RNS(ring, limb_count)
-> Poly
Random constructors such as uniform(), uniform_on_interval(), ternary(), and sparse_ternary() create lazy RANDOM nodes with ring metadata. Realization materializes the random polynomial. Constant constructors are different: Poly.const() creates a symbolic CONST node and attaches ring metadata. Constants stay allocation-free until a later pass needs to lower them into coefficient or NTT form.
Realization¶
Realization turns lazy polynomial IR into concrete buffers. realize(), tolist(), tobytes(), serialization, decryption, and JIT capture all force realization.
During ren.realize(*values), Ren collects Polys from the supplied values and gathers their requested output nodes into a single SINK:
The single sink gives the scheduler one root that covers every output requested together. If two output polynomials use the same intermediate, scheduling can see that shared dependency in one graph.
The normal realization path is:
ren.realize(*values)
-> tree.collect(..., leaf=Poly)
-> _schedule_and_lower(...)
-> schedule(SINK(...))
-> plan_memory(...)
-> make_exec_units(...)
-> run_exec_units(...)
After scheduling, Ren records a becomes_map from old lazy outputs to their new buffer-backed outputs. Ren updates existing Poly objects whose graphs overlap the realized computation so they point at realized BUFFER or CONST nodes.
Scheduling¶
Scheduling turns a high-level polynomial DAG into a LINEAR sequence of executable CALL nodes. Ren applies this pass sequence:
1. Simplify algebra, ring rules, constants, and copies
2. Lower high-level ring ops such as ROTATE
3. Inject NTT or INTT nodes for domain requirements
4. Simplify domain conversions
5. Parameterize the outer SINK as a CALL with explicit buffer bindings
6. Reuse or create its cached lowered graph, including output expressions
7. Decide materialization boundaries on a cache miss
8. Lower BUFFERIZE markers to storage views or ALLOC + STORE + AFTER
9. Lower automorphisms, ring rules, and constants
10. Indexify elementwise computation with GIDX, INDEX, LOAD, and STORE
11. Kernelize top-level stores into parameterized CALLs
12. Resolve the outer CALL with the current buffers and fresh writable storage
13. Order executable calls under LINEAR and resolve output bindings
The scheduler inserts representation changes based on operation requirements. MUL and ROTATE require NTT inputs, RESCALE requires coefficient-domain input, and some TO_RING conversions require coefficient-domain input. After insertion, domain simplification removes round trips such as NTT(INTT(x)).
Some expressions need materialized buffers. Ren marks materialization boundaries for outputs, conversion operations, copies, contiguous requests, and stores. The scheduler first represents a boundary as BUFFERIZE(x). A storage view already satisfies that request; other values need ALLOC, STORE, and AFTER. AFTER keeps dependency ordering explicit without changing the value that flows through the graph.
Ren lowers eligible TO_RING operations to views. If the destination moduli are a contiguous subset of the source basis and the layout/domain constraints allow it, the scheduler creates a BUFFER_VIEW with an element offset. If a view feeds an elementwise compute chain, the scheduler can also fuse the view into indexed loads.
After indexing, each top-level STORE becomes a CALL. Its body uses positional PARAM nodes instead of concrete buffers and lives in CALL.src[0]; the remaining sources hold the buffers in parameter order. Copies use lightweight COPY bodies. Views remain buffer expressions in arguments and outputs throughout scheduling. They never become calls.
The scheduler uses the same parameterized cache for eager roots and @ren.function bodies. Each cached graph retains its output expressions and dependency edges. Ren binds inputs and fresh allocations together, expands nested calls, then orders the executable calls into the final LINEAR sequence.
Memory planning¶
Before calls become executable units, Ren plans intermediate memory. The memory planner computes first and last use from the LINEAR call sequence. For optimizable intermediate buffers, it simulates a TLSF-style allocator and packs them into one arena per device.
The goal is to reuse storage for temporaries whose live ranges do not overlap. Ren preserves final outputs, already allocated buffers, explicit no-opt buffers, and the bases of preserved output views. Copy buffers also stay out of the arena to preserve transfer parallelism. Other intermediate views can share arena storage with their bases. The memory planner makes allocation decisions once from the schedule. Runtime execution reuses arena offsets instead of allocating and freeing each temporary.
Backend lowering and execution¶
make_exec_units() lowers each CALL to an ExecUnit. Compute calls go through the selected backend: the Python backend interprets the lowered body with NumPy and Montgomery helpers, while the CUDA backend renders kernel code, compiles it, builds launch specs, and runs it on CUDA queues.
Copies lower to either device transfer or host-mediated copy depending on allocator support. Buffer views lower to validation-only exec units that bind a view to its base.
Execution follows a short loop:
for each exec unit:
allocate required buffers
run the unit
let Python refcounts release intermediates after their final use
JIT capture and replay¶
ren.jit wraps a Python function whose arguments and outputs contain Poly objects. Inputs can be direct arguments or nested inside supported Python containers and records, including CKKS Plaintext and Ciphertext objects. See nested values for the traversal contract. Top-level scalar arguments are frozen into the captured plan; if they change on replay, Ren raises instead of running a stale branch.
On a cache miss, JIT realizes inputs, runs the user function under capture, and records scheduled CALLs as outputs are realized. It normalizes bindings, optionally prunes input-independent work, and replans captured intermediate memory. One rewrite binds inputs, outputs, and planned storage before lowering the replay calls into executable units and creating a backend graph runner if possible. Explicit realize() calls inside the body also record and execute their scheduled work. Polynomial host reads and random polynomial generation inside the body are rejected. On a cache hit, JIT passes current input and output bindings to the replay plan.
Eager lazy execution builds and schedules the graph on each realization. JIT pays that cost once per argument shape/spec and reuses the captured execution plan. See ren.jit replay for examples and failure modes.
Source map¶
ren/poly.pyfor the user-facing polynomial API and realization entry pointren/ir/op.pyfor the operation setren/ir/node.pyfor graph structure, metadata, constants, and formattingren/engine/schedule.pyfor the scheduling pass orderren/engine/rules/for the individual rewrite passesren/engine/memory.pyfor arena planningren/engine/realize.pyfor lowering scheduled items into executable unitsren/engine/jit.pyfor capture and replayren/backends/python/andren/backends/cuda/for backend execution