Learning Where to Steal From: Three-Factor Victim Selection for NUMA Work Stealing

When a core in a parallel program runs out of work, a work-stealing scheduler has it grab a pending task from another core's queue. The classic rule picks that other core, the "victim," uniformly at random. This rule balances load well, but it ignores the fact that a stolen task's data may sit in a cache or memory bank far from the thief. The usual fix hard-codes the machine's topology: steal from cores that share a cache first, then from the same socket, then from remote sockets. That works when data placement follows the topology and nothing else is running on the machine. It fails when data was placed badly, when program phases change which cores share data, or when another job is saturating one socket's memory bandwidth.

We propose to learn the victim preference online with a rule borrowed from computational neuroscience. Each thief keeps a decaying memory of whom it recently stole from, called an eligibility trace. Each socket periodically broadcasts one cheap global number, its useful-work throughput read from hardware counters. Victim preferences change in proportion to trace times signal. The point of this design is that the costs that matter most, such as contention in shared last-level caches, memory-controller queues, and cross-socket traffic, cannot be charged to individual tasks. They appear only as delayed, aggregate signals. That is exactly the setting in which "local trace times global signal" learning rules were built for credit assignment.

Core Claim

A work-stealing scheduler can learn victim preferences online from coarse, delayed, socket-level performance counters. To do this, it multiplies a per-thief eligibility trace over recent steals by a broadcast throughput-error signal. The scheduler leaves the owner's fast path untouched and mixes in a uniform-random floor that keeps the load-balancing guarantees of random stealing. We predict two outcomes. First, on workloads whose data placement matches the topology, the learned scheduler will match static hierarchical stealing; it will not beat it. Second, it will clearly beat static hierarchical stealing when placement is misaligned, when phases shift, or when a co-running job interferes. In the second regime, a static locality hierarchy actively points thieves toward the wrong victims.

The proposal treats the three directions unequally. Eligibility traces supply the learning mechanism. Locality-aware work stealing supplies the action space and the correctness constraints. Dynamic load balancing under interference is the application regime where the idea has to prove itself.

Background and Positioning

Existing locality-aware stealing encodes locality as fixed structure. An enhancement of futures runtime in presence of cache memory hierarchy orders steal targets by shared cache level. An Evaluation of DRete on CUPlD for OPSS Matching restricts migration to topological neighbors. On the efficiency of localized work stealing has idle workers first steal back their own previously stolen tasks, and proves bounds of $T_1/P + O(T_\infty P)$ in general. RDMA-Based Algorithms for Sparse Matrix Multiplication on GPUs lets a GPU steal only tiles whose operands are already in its memory. These works motivate our proposal, because each shows that locality-blind stealing wastes time. They also provide our baselines. All of them fix the locality rule before the program runs. We instead learn it from measured outcomes.

Two other papers constrain the design. Idempotent work stealing shows that fences and atomics on the owner's path dominate fine-grained workloads. Our learning must therefore touch only the thief's slow path and periodic epoch boundaries. The companion record Idempotent work stealing notes that cache misses still cap performance even after synchronization is removed, which is the residual cost we target. Scalable hardware support for conditional parallelization migrates tasks along load gradients in hardware. It needs a "difference of two" rule to prevent tasks from bouncing back and forth, a warning that any adaptive migration rule must damp its own feedback loop.

The learning rule comes from the eligibility-trace literature. Reward-modulated plasticity (Title) shows that a single diffuse global signal can tune specific connections as long as each connection carries its own trace. We reuse that structure directly, with victims in place of synapses. BP(λ): Online Learning via Synthetic Gradients shows that a trace-decay parameter trades bias from short-horizon bootstrapping against the variance of long-horizon credit. We use that view to set trace decay relative to the counter epoch. Learning From the Past with Cascading Eligibility Traces replaces the exponential trace with a chain of states whose response peaks at a chosen delay. This fixes the "temporal blurring" that occurs when feedback arrives late, and we test it as an ablation. Mem-T: Densifying Rewards for Long-Horizon Memory Agents assigns credit in hindsight over logged operation trees. That approach is accurate, but it is offline and its memory grows with the length of the episode. A scheduler needs an online rule with constant memory, which is why we use forward traces.

The research file we worked from did not include a survey of prior learned or reinforcement-learning-based schedulers. Our novelty claim is therefore made against the cited work only, and a literature check on learned victim selection is a first step.

Mechanism

Each worker $i$ keeps a preference $w_{ij}$ for each victim group $j$. Groups are cache-sharing peers, same-socket cores, and each remote socket, so the table stays small. It picks victims with probability

$$p_{ij} = \epsilon \frac{1}{P} + (1-\epsilon)\,\frac{\exp(w_{ij})}{\sum_k \exp(w_{ik})},$$

where $P$ is the number of workers and $\epsilon$ is a uniform floor.

The floor guarantees that every victim is tried with probability at least $\epsilon/P$. We expect the standard delay-sequence argument to then give a bound of the form $T_1/P + O(T_\infty P/\epsilon)$, inflated by at most $1/\epsilon$ over random stealing. Proving this bound is part of the program.

On every successful steal from group $j$, worker $i$ bumps its trace $e_{ij}$ by one. Traces decay with a time constant $\tau$ tied to the counter epoch. At the end of each epoch, socket $s$ computes $\delta_s = r_s - \bar r_s$. Here $r_s$ is useful work per unit time on socket $s$, measured as instructions retired or tasks completed, and $\bar r_s$ is a slow running average. Each worker on that socket then updates

$$w_{ij} \leftarrow w_{ij} + \eta\, \delta_s\, (e_{ij} - \bar e_{ij}),$$

where $\eta$ is a step size and $\bar e_{ij}$ is the trace value expected under the current policy. Subtracting $\bar e_{ij}$ makes the update a policy-gradient estimate rather than a rule that simply reinforces whatever the worker did often.

Using throughput as the signal means the rule weighs locality against idleness on its own terms. A remote steal that rescues an idle core raises throughput and is reinforced. A remote steal that floods the memory controller lowers it and is suppressed. The update happens at epoch boundaries and the selection happens on the steal path, so the owner's push and pop operations are unchanged. That keeps the scheduler compatible with both Chase-Lev and idempotent deques.

Research Program

We will build the scheduler into a Chase-Lev runtime and an idempotent-LIFO runtime on a multi-socket NUMA machine. Throughput will be read from per-socket uncore and per-core counters at epoch lengths between 100 microseconds and 10 milliseconds.

The analysis has three parts. First, we will prove the ε-floor bound, extending the localized-stealing argument from On the efficiency of localized work stealing. Second, we will characterize when the delayed signal can be credited. The key quantity is the ratio of trace time constant to epoch length, which the BP(λ) bias–variance view says should matter. Third, we will measure stability under the bouncing-feedback risk that the hardware-queue work faced, comparing the uniform floor and the slow baseline $\bar r_s$ against an explicit hysteresis threshold.

Baselines

The naive reference is uniform random victim selection on a Chase-Lev deque. Idempotent work stealing reports that its Idempotent LIFO variant outperforms Chase-Lev and Cilk THE by "15-20%, sometimes reaching 50%" on Kgraph, "often by a factor of 3" on 2D Torus, and by 2–10% on random graphs, with redundant work averaging 2% of tasks. We will reproduce these relative gaps on our hardware to confirm that our harness is faithful. Because our method is orthogonal to the deque, we will also run it on top of Idempotent LIFO.

The strongest locality competitor is static hierarchical stealing in the style of An enhancement of futures runtime in presence of cache memory hierarchy, which steals from cache peers, then the socket, then remote sockets. We found no reported result on Lacuna for hierarchical stealing on these graph benchmarks, so we will implement it ourselves within the same runtime.

We also run localized steal-back with hashing and mugging from On the efficiency of localized work stealing. We found no reported empirical result on Lacuna for it; the paper's results are theoretical bounds.

The decisive ablation is a direct-attribution bandit. It tags every stolen task with its source group, reads per-core counters at task boundaries, and updates an exponential moving average of each group's measured cost, with no traces and no global signal.

A second ablation swaps the exponential trace for a cascading trace of order two to ten, following Learning From the Past with Cascading Eligibility Traces.

Every scheduler gets the same machine, thread pinning, memory placement, and inputs. Each also gets the same tuning budget, a fixed grid of at most 30 configurations per method selected on held-out graph instances. Beating hierarchical stealing means a lower median makespan over ten runs, with non-overlapping 95% bootstrap intervals in the misaligned and interference regimes. Parity within 3% is required in the aligned regime.

Why not just…?

Why not just use static topology-ordered stealing? It is the right answer when the topology tells you where the data lives, and we expect it to tie in that case. It cannot react when first-touch allocation puts data on the "wrong" socket, when phase changes move the working set, or when a co-runner saturates one socket's memory controller. In those cases, preferring same-socket victims can be exactly wrong. The interference and misplacement experiments test this directly. If hierarchical stealing still wins there, the proposal fails.

Why not just measure each stolen task's cost and run a simple bandit? This is the real threat. Per-task counters do capture the thief's own private-cache misses. They miss costs that land elsewhere: evictions the steal causes in a shared cache, extra misses the victim later suffers, and queueing at the memory controller. Those appear only in aggregate socket counters. We therefore include workloads designed to push cost onto shared resources, and workloads where cost stays private. If the bandit matches the trace rule on both, then trace-based credit is unnecessary and we will report the simpler method as the result.

Why not just steal back your own tasks, or only steal tasks whose data is local? Steal-back and the operand-locality rule of RDMA-Based Algorithms for Sparse Matrix Multiplication on GPUs are excellent when ownership tracks data. They do not help a core whose own tasks are gone and whose data-local victims are themselves idle. Steal-back's general bound also carries an $O(T_\infty P)$ term. Steal-back is a baseline, and we also test it combined with the learned rule, using the learned preferences only to choose remote victims.

Proposed Experiments

The workloads are transitive closure and spanning tree on Kgraph, 2D Torus, and random graphs, matching the Idempotent work stealing setup. We add SpMM tiles on com-Orkut and Friendster run on a single multi-socket node, adapted from RDMA-Based Algorithms for Sparse Matrix Multiplication on GPUs. Each runs in three regimes. In the aligned regime, data is interleaved by topology. In the misaligned regime, all data is first-touched on one socket. In the interference regime, a memory-bandwidth co-runner is pinned to one socket and switched on and off mid-run. We measure makespan, idle fraction, remote DRAM accesses, last-level-cache misses, steal attempts per success, and the overhead of learning per steal.

Three checks settle the claim. The learned scheduler must tie hierarchical stealing in the aligned regime and beat it in the other two. It must beat the direct-attribution bandit specifically on shared-cache-heavy workloads; if it does not, the trace mechanism is not justified. And it must re-converge within a bounded number of epochs after the co-runner toggles, without oscillating. A cascading trace should help only if counter feedback lags the steal by a consistent delay. If it shows no gain over the exponential trace, we will say so.