Scheduling and Preemption on Accelerator Queues

A device that runs work to completion without interruption is easy to share as long as every user waits their turn. The moment a user’s work is long, or a user with higher priority arrives, or a process exits while its work is queued, waiting becomes unacceptable. Sharing an accelerator therefore requires the same machinery a processor needs: a notion of what is running, a way to stop it, a way to save what it was doing, and a way to resume it later. For a processor, all four exist in hardware. For an accelerator, they exist only to the extent the design paid for them, and the price is visible in both the device’s area and its worst-case latency.

The queue is the scheduling entity

On the host side, work is submitted to a queue and the queue is owned by a context. The context is what the scheduler manipulates: it holds the address space, the queue base and size, and whatever device-side state is associated with the workstream. Contexts are the unit of isolation and the unit of accounting, and a device’s ability to stay busy while contexts are switched determines whether sharing costs throughput.

The device’s view is different. A device with a single hardware work slot processes one context’s queues at a time, and switching contexts requires evicting the current one. A device with $k$ hardware contexts holds $k$ contexts resident and can switch between them without eviction, at the cost of $k$ copies of everything a context needs: queue state, page table pointers, and usually some cached configuration. The trade is memory and area on the device against the cost of an eviction.

The standard scheduling policies apply directly. Round-robin gives every runnable context a time slice and is simple to reason about. Priority scheduling lets a latency-sensitive context preempt a throughput context. And hierarchical scheduling, in which contexts are grouped and the group is scheduled before the members, is what makes virtualized sharing tractable, because the guest’s internal policy becomes irrelevant to the host’s fairness guarantee.

Where the boundary lies

The important distinction is between scheduling at work-unit granularity and preemption within a work unit. A unit is a descriptor, a kernel launch, or a command: the smallest thing the device accepts. If the device can only switch between units, then a unit that runs for a long time blocks every other context for that duration, and the scheduler’s effectiveness is bounded by the longest unit.

This is why unit granularity is a design parameter and not a detail. A device whose units are individually bounded — a copy of fixed size, a single command — can be time-sliced safely by unit boundaries alone. A device whose units are arbitrary kernels cannot, because a kernel’s duration is decided by the code it runs, which the device cannot predict.

Preemption within a unit requires three capabilities.

A stop point. The device must be able to stop at a defined instruction boundary, not mid-operation. Stopping between two memory accesses is possible; stopping in the middle of a transaction is not, because the transaction is already in flight and cannot be withdrawn.

Saved state. Everything the unit needs to continue must be captured. For a fixed-function engine this may be a handful of registers. For a highly parallel machine it includes the state of every execution lane, its registers, its program counter, and any partial results in shared memory.

A resume path. The state must be restorable into a clean context, which usually means the saved state is written to memory in a layout the device can reload without help from the driver.

The cost of the middle item is what makes preemption hard. A machine with thousands of lanes holding tens of registers each has hundreds of kilobytes of state per resident block, and writing that to memory on every preemption is a transfer whose duration is comparable to the work being interrupted.

Three levels of preemption

Implementations usually offer a graduated set, because the cheap levels cover most of the need.

Preempt at work-unit boundaries. The device finishes what it has, reports completion, and the scheduler chooses another context. Nothing is saved because nothing is interrupted. The latency to switch is the duration of the longest unit in flight, which can be arbitrarily long. This is the level that most devices provide by default, and it is adequate for throughput-oriented sharing where fairness over seconds matters more than fairness over microseconds.

Preempt at a hardware-supported instruction boundary. The device drains its pipeline at a point where it can save a consistent state, writes the state out, and signals completion. The drain is what makes it safe: in-flight operations must complete or be cancelled, and the device must be able to tell which. This level bounds the switch latency by the drain time plus the state write, both of which are device-specific constants.

Preempt with fast restore. The saved state is kept in device memory rather than written out to host memory, and restore reads it back. This trades device memory for switch latency and is what makes fine-grained interleaving practical. The device must allocate space for as many saved contexts as it intends to keep resident, which is the same resource question as hardware contexts, answered in memory rather than in registers.

A switch is therefore a sequence rather than a command: the host asks the device to stop at its next safe point, waits for a status that says the state has been written out, and only then releases the hardware slot for reuse. Each of the three steps can fail or time out, and the wait is bounded by the drain time plus the state write rather than by the work that was interrupted.

The timeout is not defensiveness. A device that cannot reach a safe point — because its lanes are all waiting on a memory operation, or because the code it runs contains a loop with no preemption check — may not drain within any bound. Designs that promise preemption therefore usually establish an upper bound on how long a unit can run without a check point, either by limiting unit duration or by inserting periodic checks into the code the device executes.

What preemption costs the interrupted work

Preemption is not free even when it succeeds. The state written out and read back passes through memory, so the interrupted context resumes with an empty cache and a cold translation cache, and the first accesses after resume miss. For a device whose performance depends on keeping operand data resident, a preemption that flushes that data can cost far more than the switch itself.

There is also an amplification effect with repeated preemption. A context that is preempted frequently spends a growing fraction of its scheduled time in save and restore rather than in work, and the useful fraction falls as the slice shrinks. Below some slice length the device does more state movement than computation, and the scheduler’s fairness guarantee is met while aggregate throughput collapses. Time-slice sizes are therefore chosen against this curve, not against a fairness target alone.

The third cost is interaction with the host. A preemption is asynchronous from the host’s point of view: the host issues the command and waits. During the wait the host context that issued it may itself be descheduled, which delays the switch. Systems that need a hard bound on switch latency usually handle the preemption in a context that is not preemptible, or in firmware that runs independently of the host scheduler.

Oversubscription and what it actually means

A device with $k$ hardware contexts supporting $n > k$ runnable contexts is oversubscribed, and the scheduler must evict to admit. The behaviour under oversubscription is where the design differences show up most clearly.

If eviction requires a full state write to host memory, admission of a new context costs a transfer proportional to state size, and the system’s throughput under oversubscription is bounded by the memory bandwidth available for state movement rather than by the device’s compute. Systems that support large degrees of oversubscription therefore keep state on the device, either in a dedicated area or in the same memory the device uses for its own working set, and eviction becomes a pointer change rather than a copy.

If the device cannot preempt, oversubscription is implemented by waiting for units to finish, and the scheduler has no control over admission latency. This is workable for batch workloads with uniform unit durations and unusable for interactive ones.

Where the guarantees stop

The guarantees a scheduler can offer depend entirely on what the hardware provides, and the common mistake is to assume a guarantee the device does not implement. A fair-share policy enforced at unit boundaries offers no bound on the delay a context can experience from a single long unit. A preemption capability that is disabled in the driver’s configuration offers nothing at all. And a device that advertises preemption at instruction boundaries may still have code paths — firmware routines, error recovery, internal maintenance — during which it cannot stop.

The interaction with memory is where these limits become visible. Preemption does not suspend a device’s outstanding DMA, so a context that is evicted while its transfers are in flight must either have those transfers cancelled and acknowledged or have its mappings kept alive until they drain. That requirement is the reason the address-space teardown described in Shared Virtual Addressing and Peer-to-Peer Transfers must be ordered after quiescence rather than concurrent with it.