Algorithm and schedule

A SKaiNET network says what is computed. Since SKEEP-005 a second, optional object says how the independent parts of one op are mapped onto cores: the schedule. The split is Halide’s — algorithm here, schedule there — and it exists for the same reason: the same model must run on a phone core, a laptop and a server without being rewritten, and the choice of threads is a property of the deployment, not of the mathematics.

This page states the principle, the contract, and how to observe it. Its companion pages: The DSL is compute (the doctrine this follows), Kernel SPI and the selection algorithm (what runs inside a task), The memory model (why a task must not allocate), and Schedules: parallel ops, same results (the executable walk-through).

The principle

A network definition is a pure description of computation. A schedule says how many tasks compute the independent parts of one op and on which threads. It lives on the execution context, never in the DSL — and it never changes a result: a scheduled run is bit-identical to a sequential one.

Three consequences follow.

  • No schedule words in network { }. A model is defined once. Whether its attention heads run on one thread or twelve is decided where the model is run, with ctx.withSchedule(…), exactly like forwardScope decides where activations live.

  • The default is sequential — except where the platform already parallelised. On the JVM a DirectCpuExecutionContext() runs CoroutineSchedule.hardware(), the core-count coroutine schedule; that is what the Panama matmul kernels always did, now visible and switchable. Every other target and every context that does not opt in runs Schedule.Sequential.

  • A request that cannot be honoured is visible. A context that cannot rebuild its ops returns itself from withSchedule and emits TraceEvent.ScheduleDowngraded. Nothing is silently approximated.

What a Schedule is

public interface Schedule {
    public val parallelism: Int                       // 1 = sequential
    public val name: String                           // "sequential", "coroutines(12)", …
    public fun forRange(n: Int, grain: Int = 1, body: (start: Int, end: Int) -> Unit)
    public fun forEach(count: Int, minPerTask: Int = 1, body: (index: Int) -> Unit)
    public object Sequential : Schedule
}

It is deliberately small, non-suspending and dependency-free: ops are synchronous on every Kotlin target, and skainet-lang-core takes no coroutine dependency. The JVM implementation, CoroutineSchedule in skainet-backend-cpu, keeps the structured-concurrency guarantees without ever letting the caller block on work that still needs a pool thread. One region is one shared queue of chunks:

  • the calling thread runs the first chunk itself, then keeps claiming chunks until the queue is empty, so no core idles blocked on the join;

  • tasks - 1 helpers are dispatched to the dispatcher (Dispatchers.Default by default) and claim chunks from the same queue; a helper the pool never started finds the queue empty and exits without running a body;

  • the region returns only when every claimed chunk has finished — the first failure stops the chunks that have not started and is rethrown to the caller once the running ones are done;

  • because the caller only waits for chunks that are already running somewhere, a region entered from a thread of the dispatcher’s own pool cannot deadlock, however many pool threads are busy;

  • a region reached from inside another region runs inline; CoroutineSchedule.dedicated(n) owns its own pool for callers that want isolation from Dispatchers.Default.

The contract a body must keep

forRange hands a body disjoint half-open ranges covering [0, n). In exchange the body promises:

  1. it writes only into pre-allocated, disjoint regions of the output and reads only inputs that are immutable for the region;

  2. it never allocates through an ExecutionContext and never calls ctx.ops — the step allocator (ForwardScope), the scratch pool and the op caches are single-threaded by design;

  3. it never starts a nested region (an implementation runs one inline anyway);

  4. its arithmetic and the order of that arithmetic do not depend on how the range was cut.

The last promise is what makes results bit-identical. The engine’s first scheduled op, scaledDotProductAttention, is the model: every (batch, head) pair computes exactly the loop it computed before, into its own rows, with its own scores scratch; the schedule only decides which pairs share a task. A tiny call (a decode step on a handful of heads) stays on the caller — a region costs more than it saves below SDPA_PARALLEL_MIN_WORK multiply-adds.

Where it hangs

Seam Role

ExecutionContext.schedule

The schedule this context’s ops run under. Default Schedule.Sequential.

ExecutionContext.withSchedule(s)

The context rebuilt so its ops carry s — the same seam as withTensorDataFactory. A context that cannot rebuild returns itself and traces ScheduleDowngraded.

ctx.withSchedule(s) { scheduled → … }

The decorator form (ScheduledExecutionContext), composable with forwardScope. Tensors created through scheduled are bound to the scheduled ops — the usual ops-binding rule.

DirectCpuExecutionContext(schedule = …)

The JVM context; omitted, it takes platformDefaultSchedule().

DefaultCpuOpsBase(dataFactory, schedule)

Ops hold the schedule; parallelChunks(outputDim, schedule) is how a kernel asks for tasks.

What runs where

Target Default schedule Parallel schedule available

JVM

CoroutineSchedule.hardware() — availableProcessors() on Dispatchers.Default

yes (CoroutineSchedule, dedicated())

Android

Sequential

not yet (coroutines are a JVM-only dependency of the backend today)

Kotlin/Native (Linux, Apple, Android native)

Sequential

not yet

JS, Wasm

Sequential

no — single-threaded runtimes; a parallel schedule cannot be constructed there

How to see which schedule ran

ctx.schedule.name tells you what a context carries. To see what actually happened, attach a sink:

val sink = RecordingTraceSink()
val ctx = DirectCpuExecutionContext(schedule = CoroutineSchedule.hardware(sink = sink))
// … run …
sink.eventsOf<TraceEvent.ScheduleRegion>()      // op, schedule, elements, tasks, duration
sink.eventsOf<TraceEvent.ScheduleDowngraded>()  // requested, effective, reason

A ScheduleRegion is emitted per parallel region; a ScheduleDowngraded whenever a request was not honoured. The Perfetto exporter and the Android trace sink render both.

The compile lane

The eager schedule is a runtime object; the compiled graph gets the same fact as metadata. In the dag { } DSL a request is stamped on nodes the way a dtype policy is:

dag {
    schedule(parallel("heads")) {                 // every op recorded inside
        op(sdpa, listOf(q, k, v))
    }
    op(matmul, listOf(x, w), schedule = parallel("rows", parallelism = 8))
}

ScheduleAnnotationPass (a core pass whenever a target is named) validates the requested dimensions against what the op can be split on — batch/heads for attention, rows for matmul, batch/out_channels for convolutions — stamps the normalised hint into the node’s metadata and reports every rejection as a diagnostic. The StableHLO export carries it in the module header beside the layouts:

module attributes {skainet.tensor_layouts = {…}, skainet.schedule = {attn = {parallel_dims = ["batch", "heads"], parallelism = 8}}} {

One graph, extra schedule metadata. A consumer that ignores the attribute computes the same result — and by decision no compile-time consumer reads parallelism.

Who schedules what

The compiled leg follows one rule: structure at compile time, cores at run time. SKaiNET’s passes state the structure — an attention without any DSL hint is still stamped parallel_dims = [batch, heads], and grouped-query attention lowers with the head groups as a batching dimension of both dot_general`s instead of broadcasting or concatenating K/V. The compiler backend (IREE) owns the instruction set, tiling and workgroup formation, and its task runtime maps workgroups onto cores when the device is created. A `parallelism that the DSL asked for is emitted but advisory; the same number reaches the device as its task-topology group count at run time, so one .vmfb runs unchanged on any core count. On the JVM the compiled ComputeGraphExecutor is built from the context’s ops and therefore runs under the context’s schedule like the eager path. The full decision, with a diagram, is in SKEEP-005.

What this rules out

  • A parallel = true on a layer in network { }. The layer does not know the device.

  • A kernel that spawns its own threads. It asks the schedule for ranges.

  • A body that reaches for ctx.zeros(…​) or ctx.ops.matmul(…​) inside a region. It gets a data race in the step allocator, not a faster op.

  • Silent fallbacks. A schedule that cannot run says so in the trace.