The IREE task system is a cooperative, multi-worker scheduler built around a single abstraction: the process. A process is any unit of work that can be drained incrementally by one or more workers. Workers call drain() on processes, do bounded work, and return — freeing them to handle other work (I/O completions, higher-priority processes, newly-arrived submissions) before coming back for more. There are no task types, no DAGs, no coordinator thread, and no per-operation allocation at execution time.
The drain/return model is the key design choice. Every scheduling decision happens at the boundary between drain() calls — a natural yield point that costs one atomic load (~1ns) to check for higher-priority work. This gives the system fine-grained interleaving of compute and I/O without preemption, context switches, or kernel involvement.
Dispatch-to-dispatch latency < 10μs. The dominant cost should be the kernel itself, not the scheduling machinery around it. No per-command task allocation, no DAG construction, no coordinator round-trip.
Zero-overhead pipelining. Multiple command buffers in flight simultaneously, with I/O completions (semaphore signals, buffer readiness) processed between drain() calls. The system pipeline stays full without explicit overlap management.
Unified execution model. Compute (tiled dispatch), I/O (buffer transfer), host callbacks, VM invocations, and queue management all use the same process interface. One scheduling policy, one worker loop, one wake mechanism.
Direct wake, zero hop. When a GPU completion, semaphore signal, or I/O event makes a process runnable, the signaling thread directly activates it (atomic decrement + list push). No coordinator lock, no ready-queue round-trip, no batched wake — the process is scannable by workers on the next loop iteration.
The previous task system had six task types (NOP, CALL, BARRIER, FENCE, DISPATCH, DISPATCH_SHARD), a coordinator mutex, per-command task allocation during recording, shard fan-out at dispatch issue, and a centralized classify-and-route loop. The process model replaces all of these with one type, one worker loop, and one activation mechanism.
A process has:
A drain function: called by workers to do bounded work. Multiple workers may call concurrently. Returns quickly (one region pass for compute, one operation for queue management).
A suspend count: atomic counter. Process is runnable when count is zero. External events (semaphore signals, upstream process completion) decrement the count. The thread that drives it to zero activates the process.
A wake budget: how many workers the executor should try to wake for this process. Updated dynamically by the drain function (e.g., a block processor updates the budget at each region transition based on available tiles). This is a wake fan-out hint, not an admission limit on active drainers.
A dependent list: processes to activate when this process completes. Completion decrements each dependent's suspend count. This replaces BARRIER tasks — dependency fan-out is an atomic decrement per dependent, inline in the completing worker.
A cancellation flag: atomic. When set, drain() returns completed with an error. Wake events on cancelled processes are no-ops. Cancellation propagates to dependents (they see the error in their scope/group).
An error status: first error wins via CAS. Checked on drain() entry. When a process errors, dependents are still activated (their suspend count decrements normally) but they see the error and bail.
suspend_count > 0
Created ──────────────────────────► Suspended
│ │
│ suspend_count == 0 │ last decrement drives to 0
│ │
▼ ▼
Activated ◄─────────────────────── Activated
│ │
│ pushed to run list │ pushed to run list
│ │
▼ ▼
Runnable ◄──────────────────────── Runnable
│ │
│ worker calls drain() │ worker calls drain()
│ │
▼ ▼
Draining ──── drain() returns ────► Runnable (more work available)
│
│ drain() returns completed
│
▼
Completing ──── resolve dependents ──► (dependents activated)
│
│ cleanup
│
▼
Freed
A sleeping process is one that returned did_work=false from drain(). The executor marks it as deprioritized in the run list — workers skip it during normal scan. When an external event wakes it (semaphore signal changes its input state), the process is reprioritized. This avoids polling sleeping processes on every scan revolution.
Cancellation sets the process's cancel flag. The next drain() call sees it and returns completed with IREE_STATUS_CANCELLED. If the process is sleeping, cancellation wakes it (to trigger the drain-and-exit path).
Cancellation propagates through dependents: when a cancelled process “completes” (with error), its dependents activate normally but inherit the error. Their drain() calls bail immediately, cascading the cancellation through the dependency chain.
For device teardown: a HAL device has a small number of well-defined processes (2-3 per queue). Teardown cancels these processes and waits for them to drain to completion. Child processes (block processors issued by the queue) are cancelled transitively. The teardown is bounded — it waits for at most one drain() call per process per worker, which is sub-millisecond.
Each worker thread has three states:
| State | CPU | Wake latency | Description |
|---|---|---|---|
| Draining | Full | N/A | Executing a drain() call |
| Spinning | ~Full | < 100ns | Scanning for work, no drain() in progress |
| Parked | Zero | 1-5μs | Sleeping on notification (futex) |
State transitions:
The spin timeout is adaptive: when aggregate worker budget is high (lots of compute work available), spinning workers wait longer before parking. When budget is low (few processes, low parallelism), they park quickly to avoid wasting CPU.
while (!exit_requested) {
// 1. Check for immediate work (budget-1, FIFO).
process = try_pop(executor.immediate_list);
if (process) {
process.drain(worker_index, worker_state, &result);
process_complete(process);
continue;
}
// 2. Scan compute processes (budget-N, array-based).
process = scan_compute(executor.compute_slots, &my_position);
if (process && is_runnable(process)) {
process.drain(worker_index, worker_state, &result);
if (result.completed) process_complete(process);
continue;
}
// 3. No work — transition toward parked.
if (should_park()) {
park_on_notification();
}
}
Why two lists? The immediate list handles short-lived, single-worker operations (queue issue, host callback, retire/signal). The compute list handles long-lived, multi-worker operations (block processor, streaming queue). Separating them means the compute scan — the hot path, 99% of all cycles — never touches immediate-work process metadata. A failed try_pop on an empty immediate list costs one atomic load (~1ns).
Workers maintain per-process state across drain() calls (e.g., the block processor's worker_state_t with cached block_sequence). This state is indexed by process slot and owned entirely by the worker — no sharing, no atomics. The executor allocates this state per-worker when a process is activated, sized by process.worker_state_size.
Each process declares a wake budget — how many concurrent drainers it benefits from waking. The executor maintains an aggregate budget (sum across all runnable processes) and uses it for worker management:
Budget is a hint, not a hard limit. Any worker can drain any process. A process with budget=4 will work correctly with 1 worker or 16 — the budget only affects how many workers the executor tries to keep active.
The compute list is an array of process slots. Workers scan by index, starting at different positions (worker_id modulo slot count) to spread coverage. The scan is read-only — workers load slot pointers and check runnable flags. No contention between scanners.
The scan order determines scheduling policy. Options:
Round-robin (default): scan all slots in index order. Simple, fair, predictable. Each process gets visited proportional to the number of active workers.
Priority-ordered: maintain an indirection table that orders slots by priority. Workers scan through the indirection table instead of raw slots. The indirection table is updated when processes are activated/deactivated, and is immutable between updates (read-only for scanners). High-priority processes get visited first.
Budget-weighted: workers visit processes proportional to their worker budget. A process with budget=8 gets visited ~4x as often as one with budget=2. Implemented via the indirection table (repeat high-budget entries).
The scan function is a small, hot piece of code in the worker loop — easy to swap, easy to benchmark, easy to tune per-deployment. The process type and drain interface are agnostic to scan policy.
When an external event makes a process runnable, the signaling thread activates it directly:
This is zero-hop activation — no coordinator, no ready-queue, no lock. The signaling thread (proactor, semaphore callback, completing worker) does the activation inline. The latency from “event occurs” to “process is scannable” is one atomic operation + one slist push.
Waking many workers from a single event (e.g., 0 → 32 workers when a large command buffer becomes ready after all workers were idle) is expensive if done serially: one futex wake per worker, ~5μs each, ~160μs total for 32 workers.
Wake trees distribute the wake cost:
desired_wake = wake_budget and wakes one parked worker.desired_wake (fetch_sub) and wakes that many additional workers before starting to drain.Workers interleave waking with draining: a worker that wakes two others immediately starts scanning for work. It doesn't wait for the tree to complete. Useful work begins on the first wake, not the last.
The primary workload. A block processor process wraps a recorded command buffer (block ISA) and executes it cooperatively:
This is where 99% of cycles are spent. The drain() hot path is: atomic load (block_sequence check) → atomic load (packed region_state) → CAS loop on tile_index → kernel call. No allocation, no indirection beyond the drain function pointer.
A HAL queue is a persistent process that manages submissions:
The queue process replaces the current wait_cmd → issue_cmd → retire_cmd CALL task chain. Three task allocations per submission → zero (queue process is pre-allocated, block processor context is arena-allocated).
Not all queue operations warrant a separate process. Transient allocations (queue_alloca is typically a sub-allocation from a pool, queue_dealloca releases back to it) and host callbacks are small, synchronous operations that execute inline in the queue process's drain().
Each pending queue operation (command buffer submission, alloca, dealloca, host call) has its own wait count — one per unsatisfied semaphore dependency. Semaphore timepoint callbacks decrement the wait count directly. When the last wait resolves (count driven to zero), the callback pushes the operation onto the queue's ready list (lock-free slist) and wakes the queue process. No scanning — the ready list contains only operations that are immediately executable.
The queue process's drain() pops from the ready list and handles each operation by type:
This is the same direct-wake pattern used everywhere else: the signaling thread (semaphore callback, proactor, completing worker) does the readiness transition inline. The queue process never scans — it wakes, pops ready work, handles it, and sleeps again if the ready list is empty. Execution order is determined entirely by semaphore resolution timing, not submission order.
A VM invocation context that runs model execution graphs. The VM executes bytecode until it hits an async wait (e.g., waiting for HAL operations to complete), then the process sleeps. When the waited-on semaphore signals, the process wakes and resumes execution.
sleeping=true. The process is deprioritized until the semaphore signal wakes it.This turns the proactor's “offload work from the CQ thread” problem into a scheduling problem: the proactor signals a semaphore, the semaphore activates a VM process, a worker picks it up on its next scan. No dedicated offload thread, no thread-hop latency, no oversubscription. The CQ thread stays focused on completions; the worker pool handles everything else.
An alternative to recording full command buffers: individual dispatches, fills, and copies submitted directly to a queue. The queue accumulates operations in a ringbuffer, and workers drain them directly.
This is a future extension — the block processor handles the general case (recorded command buffers with barriers and multi-dispatch regions). The streaming process handles the simple case (independent operations, no barriers).
Process metadata is laid out for minimal false sharing:
Cache line 0 (immutable after creation):
drain function pointer, worker_state_size, scope pointer,
dependent list, dependent count, ...
Cache line 1 (activation/completion — written by signaling threads):
suspend_count, cancelled flag, state
Cache line 2 (scheduling — written by drain function):
wake_budget, sleeping flag, last_did_work
Cache line 3+ (process-specific mutable state):
Block processor: packed region_state, remaining_tiles, tile_indices, ...
Workers scanning the compute list touch cache line 0 (read function pointer) and cache line 1 (read state/runnable). These are read-shared in L1 across workers — no coherence traffic during scan.
Workers draining touch cache line 3+ (process-specific state). For the block processor, tile_indices are individually cache-line-padded so workers claiming tiles from different dispatches have zero contention.
The compute list is a fixed-size array of pointers (process_t*). The array size is bounded (e.g., 64 slots — matching the maximum number of concurrent command buffer executions). Workers scan by loading pointers, which are 8 bytes each — 8 slots fit in one cache line. Scanning 64 slots touches 8 cache lines, all read-shared.
Activation (writing a slot) uses CAS: NULL → process_ptr. Deactivation uses CAS: process_ptr → NULL. Scanners never write to the array — zero contention between scanners and rare contention between scanner and activator (one CAS per process lifetime).
A lock-free MPSC slist (multiple producers — any thread can push; single consumer — one worker pops per item). Push is slist_push (CAS on head). Pop is slist_pop (CAS on head). Typical size: 0-2 items. The list is empty 99.9% of the time; the failed pop costs one atomic load.
A process's suspend count is the synchronization mechanism for all dependencies. The ordering guarantee: all writes performed by the signaling thread before the fetch_sub are visible to the draining worker after a successful scan (the scan loads the process pointer with acquire, which pairs with the release in the activating push).
The wake sequence for a process with two dependencies:
Thread A (upstream process completes):
[writes to shared state]
fetch_sub(&process.suspend_count, 1, release) → old=2, new=1
// Old was 2, not driving to 0 — do nothing.
Thread B (semaphore signals):
[writes to shared state]
fetch_sub(&process.suspend_count, 1, acq_rel) → old=1, new=0
// Drove to 0 — this thread activates the process.
// The acquire on this fetch_sub sees Thread A's release.
slist_push(&run_list, process) // release semantics on push
wake_workers()
Worker C (scans and finds process):
process = load(&slot, acquire) // sees the push's release
process.drain(...) // sees all state from A and B
| Operation | Latency | Mechanism |
|---|---|---|
| Drain boundary (check for other work) | ~1ns | Atomic load of immediate list head |
| Process activation (suspend→runnable) | ~10ns | fetch_sub + slist_push |
| Worker wake (parked→spinning) | 1-5μs | futex/notification |
| Wake tree (0→N workers) | ~5μs × log2(N) | Distributed wake |
| Scan revolution (64 compute slots) | ~40ns | 8 cache line reads |
| Command buffer issue (queue→compute) | ~200ns | Arena alloc + context init |
Workers spend 99%+ of their time in drain() calls (kernel execution). The scheduling overhead per drain() call is:
try_pop on immediate list (failed): ~1nsFor a drain() call that executes a single tile of a 100μs kernel, the scheduling overhead is 0.01%. For a 1μs kernel, it's 1.3%.
| Metric | Previous (task DAG) | Process model |
|---|---|---|
| Per-command allocation at recording | 1 task per command | 0 (builder writes .text) |
| Per-dispatch allocation at issue | 1 dispatch + N shards | 0 (processor context from arena) |
| Coordinator lock per submission | 1 acquire/release | 0 (no coordinator) |
| Dispatch-to-dispatch latency | ~300μs | Target: < 10μs |
| Semaphore signal → dependent start | 3+ hops (coordinator) | 1 hop (direct wake) |
| Worker wake mechanism | Serial (N futex calls) | Tree (log2(N) rounds) |
1. User records command buffer (builder writes .text). 2. User calls queue_execute(wait=[], cmd_buf, signal=[S@100]). 3. Queue process drain(): a. No waits — submission goes directly to ready state. b. Allocate block processor context from arena. c. Wrap as compute process (suspend_count=0, budget=8). d. Push to compute list. e. Wake workers (wake tree, desired_wake=8). 4. Workers scan compute list, find block processor process. 5. Workers call drain() concurrently: a. Epoch-tagged CAS claims tiles from current region. b. Execute kernels. c. Completer advances region, updates wake_budget. d. Repeat until RETURN reached. 6. Last worker's drain() returns completed=true. 7. process_complete(): a. Signal semaphore S to value 100. b. Free arena (processor context + submission state). c. Remove from compute list.
1. User submits: CB1 (signal S@1) then CB2 (wait S@1, signal S@2).
2. Queue process drain() — first call:
a. CB1 has no waits → issue as compute process P1.
b. CB2 waits on S@1 → register timepoint on S.
Submission stays in waiting state.
3. Workers drain P1. Meanwhile:
a. I/O completion arrives on proactor thread.
b. Proactor signals a different semaphore → activates unrelated process.
c. A worker handles the activation between drain() calls (sub-μs).
4. P1 completes → process_complete() signals S to value 1.
5. Semaphore S dispatches timepoints:
a. CB2's timepoint fires → decrements CB2 submission wait count.
b. Wait count reaches 0 → submission moves to ready.
c. Wake queue process.
6. Queue process drain() — second call:
a. CB2 is ready → issue as compute process P2.
b. Push P2 to compute list, wake workers.
7. Workers drain P2. Latency from "P1 done" to "first P2 tile":
~200ns (signal + timepoint + queue drain + first scan).
1. VM invocation starts as a coroutine process (on immediate list). 2. Worker drains: VM executes bytecode, submits HAL operations. 3. VM hits async wait (waiting for HAL results) → process sleeps. Worker moves on to other work. 4. HAL operations execute (block processor processes on compute list). 5. Last HAL operation completes → signals semaphore. 6. Semaphore timepoint decrements VM process's suspend count. 7. Suspend count hits 0 → VM process activated (pushed to immediate list). 8. Next worker scan: pops VM process, calls drain(). 9. VM resumes execution from where it left off. Latency from "HAL done" to "VM resumes": < 5μs.