Locality-Aware Work Stealing for Parallel Runtimes

14 concepts10 papers1 proposal

In parallel computing, the goal is often to keep every processor busy. The classic solution is work stealing: when a processor runs out of tasks, it "steals" a task from the queue of a busy neighbor. While this effectively balances the computational load, it often ignores a critical performance factor: data locality.

If a task is moved to a processor far away from the data it needs, the time saved by balancing the load is quickly lost to the latency of fetching data from remote caches or main memory. Locality-aware work stealing addresses this by ensuring that tasks move toward the data, rather than just moving to any idle processor.

The Cost of Moving Work

Traditional work-stealing algorithms prioritize high throughput by minimizing idle time. However, as Michael et al. observe, the effectiveness of these algorithms is often bottlenecked by cache misses, particularly when the computational cost of a task is low compared to the cost of moving its data.

When a processor steals a task, it must populate its local cache with the task's working set. If the task is "cold" in the new processor's cache but "hot" in the original processor's cache, the steal triggers expensive memory traffic. Certner et al. argue that even the order of stealing matters; fetching the most recently created tasks (tail tasks) from a local queue is often superior because the parent task's data is more likely to still reside in the local cache.

Hierarchical Stealing

Modern hardware is rarely flat; it is a hierarchy of cores, shared caches, and sockets. Runje et al. propose aligning the stealing strategy with this physical topology. Instead of stealing from a random processor, an idle core first attempts to steal from a neighbor that shares the closest level of the cache hierarchy (e.g., a sibling core sharing an L2 cache). Only if that fails does it look further away.

This hierarchical approach minimizes the latency and bandwidth costs of moving task data across distant memory domains. Similarly, in the context of multi-GPU systems, Wang et al. utilize a dynamic scheduler that prioritizes tasks based on their likelihood of hitting local or shared peer-to-peer caches, rather than relying on static partitioning.

Localized and Neighbor-Based Migration

A simpler but effective intuition is to restrict how far a task can travel. Kelly et al. demonstrated that migrating tasks only to immediate neighbors in a processor array can provide significant performance gains without the overhead of global coordination. By keeping migration local, the system avoids the "thundering herd" problem and reduces the distance data must travel.

Leiserson et al. take this further with the concept of localized work stealing, where a processor prioritizes reclaiming its own previously offloaded tasks before attempting to steal from others. This "steal-back" mechanism ensures that if a processor becomes free, it returns to the data it already has cached, effectively treating its own cache as a primary resource to be exploited.

Data-Aware Task Routing

For irregular workloads—such as sparse matrix multiplication or graph processing—load imbalance is common, but data movement is prohibitively expensive. In these scenarios, the scheduler must be "data-aware."

Lima et al. show that for tasks with complex dependencies, strategies that prioritize data locality significantly outperform those that only consider raw processing power. This is echoed by Buluc et al., who found that in distributed GPU environments, dynamic stealing is most effective when it targets tasks whose data is already present in the "thief's" local memory, bypassing the need for high-latency RDMA transfers.

Even at the software level, Bai et al. suggest routing numerically "close" tasks to the same worker threads. By grouping tasks that access similar memory regions, the system creates artificial temporal and spatial locality, keeping data "hot" across multiple consecutive tasks. In big data contexts, Rundensteiner et al. apply a similar logic to recurring queries, balancing workloads specifically to maximize the reuse of cached intermediate results.

Summary

Locality-aware work stealing transforms the scheduler from a simple load balancer into a data-traffic controller. By acknowledging that data movement is often the primary bottleneck, these strategies—whether through hierarchical stealing, neighbor-based migration, or data-aware routing—ensure that the cost of balancing the load does not exceed the benefit of the parallel execution itself.

Key Foundational Work

An Evaluation of DRete on CUPlD for OPSS Matching (1989) — contributed 2 concept elements to this direction.
A Key-based Adaptive Transactional Memory Executor (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_locality_aware_work_stealing_66a551dd,
  title = {locality-aware work stealing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/locality-aware-work-stealing/rdr_66a551dd9b4f47039e050cacd38be2d7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_locality_aware_work_stealing_66a551dd_v1,
  title = {locality-aware work stealing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/locality-aware-work-stealing/rdr_66a551dd9b4f47039e050cacd38be2d7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake