Manycore chips pack hundreds of simple cores that share no cache coherence, so programmers must place every piece of data and synchronize every core by hand, and the easy programming model only supports rigid parallel loops — this work from Cornell, the University of Washington, and UC Santa Cruz shows that a work-stealing runtime, long assumed impossible on such chips, actually runs well on them and speeds up uneven workloads by up to 28.5 times, by keeping a single copy of shared data in the chip's fast local memories and letting idle cores steal work from busy ones.
The argument in one glance
-
Problem
Manycore chips are powerful but painfully hard to program
To reach hundreds or thousands of cores on one chip, manycore architectures keep each core simple and replace hardware cache coherence with small, fast, software-managed scratchpad memories. The programmer then has to place every piece of data and coordinate every core by hand. This burden is one of the main reasons these chips have not caught on.
-
What people did
Offer only static parallel loops, or narrow domain frameworks
The programming models these chips ship with mostly support static parallel loops, where the work is split across cores once, at compile time. Some projects instead build a framework for one domain, such as graph processing or deep learning. Both approaches leave the programmer without general, automatic load balancing.
-
Why it fell short
Static loops cannot balance uneven work, and coherence is missing
A static parallel loop hands each core a fixed slice of the work. If the slices take very different amounts of time, most cores sit idle waiting for a few slow ones. The natural fix on ordinary CPUs is dynamic task parallelism with a work-stealing runtime. But conventional wisdom said that runtime cannot work on chips with only scratchpads, because its shared task queues and counters seem to need the cache coherence these chips do not have.
-
This paper's idea
Build a work-stealing runtime that keeps one copy in scratchpad
This work implements a Cilk-style, fork-join work-stealing runtime on the HammerBlade manycore. The key realization is that these chips let any core read and write any other core's scratchpad directly, so the runtime keeps exactly one copy of each shared value and needs no coherence protocol. It then moves the hot runtime data into the fast scratchpad space the programmer left unused, and speeds uneven workloads up by up to 28.5 times.
Why this problem is worth solving
To see why this matters, it helps to understand what these chips are and why they resist normal programming. A manycore architecture is a single chip with a very large number of simple processor cores — more than a hundred, and in recent research prototypes over a thousand. To fit that many cores, designers make each core small and, most importantly, remove the hardware that keeps ordinary caches consistent. On a normal multi-core processor, hardware cache coherence quietly makes sure that when one core writes a value, every other core sees the new value. That hardware grows expensive and slow as the number of cores rises. So manycore designers drop it and give each core a small, fast, software-managed scratchpad memory instead — for example, four kilobytes per core on the HammerBlade chip used in this paper, reachable in two clock cycles, while the shared off-chip memory takes tens to hundreds of cycles. The cores are wired together by a mesh network, and any core can read or write any other core’s scratchpad. This layout is called a partitioned global address space, meaning every core’s private memory has its own region of one big address map. The catch is that nothing keeps copies consistent automatically. The programmer must decide where every value lives, move data between scratchpads and off-chip memory by hand, and place every synchronization operation correctly. This manual work is error-prone and slow, and it is widely seen as one of the main barriers to these chips being adopted.
The everyday way to program such chips is too rigid, and the flexible alternative was thought impossible. The programming models that ship with these chips mostly offer static parallel loops. A static parallel loop divides the iterations of a loop across the cores once, before the program runs. This works well when every iteration does about the same amount of work. It fails when the work is uneven or when the amount of work is not known until the program runs, which is common for graph algorithms, search, and sorting. In those cases a few cores get heavy slices and the rest finish early and wait. On ordinary multi-core CPUs the solution is dynamic task parallelism. The program is written as many small tasks that can spawn more tasks while it runs, in the familiar fork-join style of Cilk, Intel Threading Building Blocks, and OpenMP. Underneath sits a work-stealing runtime. Each core owns a queue of ready tasks. When a core runs out of its own tasks, it becomes a thief and steals a task from a busy core, called the victim. This automatically spreads uneven work across the chip. The problem is that the task queues and the counters that track unfinished child tasks are shared data, and the standard belief was that keeping them correct requires cache coherence, which manycore chips do not have. This paper sets out to show that belief is wrong.
What people did before, and where it broke
- Static parallel loops (the shipped model). Split a loop’s iterations across the cores once, at compile time, and let each core run its slice. Where it broke. It cannot balance uneven or unpredictable work, so on irregular workloads a few cores stay busy while the rest idle, wasting most of the chip.
- Domain-specific frameworks. Build a specialized framework for one area, such as graph processing or deep learning, that hides the manual memory management for that area. Where it broke. It only helps inside its domain, forces programmers to rewrite their code into the framework’s shapes, and cannot be extended by someone who does not know the hardware deeply.
- Work-stealing on coherent or software-coherent caches. Prior work ran Cilk-style runtimes on manycores that still had caches, keeping the shared task queues correct with extra cache invalidate and write-back instructions or special coherence hardware. Where it broke. Those techniques assume caches exist. They do not apply to chips whose only local memory is a plain scratchpad with no coherence at all.
- The gap. No one had shown that a general work-stealing runtime is even possible, let alone beneficial, on a manycore whose cores have only software-managed scratchpads and no cache coherence. Conventional wisdom said it was not. Building that runtime, and measuring that it wins on real workloads, is what this paper provides.
How the work-stealing runtime works
From a familiar task-parallel program to a scratchpad-aware runtime
-
-
new
-
new
-
new
-
new
-
new
The idea
Make dynamic task parallelism cheap enough to run on tiny simple cores. The whole contribution rests on taking the fork-join, spawn-and-wait model that programmers already know from Cilk and making its work-stealing engine light enough for cores with only a few kilobytes of memory and no coherence. The runtime lets a program express far more parallelism than the chip has cores, then hands the scheduling and balancing to software that decides, at run time, which idle core should pick up which piece of work. Bringing rich dynamic task parallelism to a setting where the naive cost of creating and moving tasks would normally be crushing is the same ambition the heartbeat-scheduling work covered elsewhere on this site pursues, letting a program name all its potential parallelism while paying to actually create a parallel task only when a periodic signal shows it is worth it.
Reclaim the fast memory the programmer left sitting idle. The scratchpad is small, and most programs do not use all of it, so the runtime quietly borrows the leftover space for its own hot data — the call stack and the task queues — where accesses cost two cycles instead of the hundreds an off-chip trip costs. Nothing about the program changes; the runtime simply notices an underused fast resource and puts it to work. Turning a resource that would otherwise sit idle into extra performance, without asking the programmer to manage it, is the same instinct the idle-flash-bandwidth storage work covered elsewhere on this site follows, handing each tenant an agent that harvests the flash bandwidth other tenants are not using at that moment.
Replace a shared lookup with direct address arithmetic. A naive runtime would keep a table in shared memory that maps each core to the location of its task queue, and a thief would read that table before every steal — a slow trip to off-chip memory on the busiest path in the system. The runtime removes the table entirely by placing every queue at the identical offset inside each core’s scratchpad, so a thief computes a victim’s queue address from its own with a little arithmetic. Removing a layer of indirection by computing a location directly instead of looking it up in a shared structure is the same move the direct page-table indexing work covered elsewhere on this site makes, jumping straight to the final translation entry rather than walking a multi-level table to find it.
Following a task steal through the runtime
Stealing a Fibonacci task across two cores
Tracing one spawn-and-steal shows why a single shared copy stays safe.
Step 1 of 5
A core spawns a child task
Core zero computes fib of n. It spawns fib of n minus two as a task and starts running fib of n minus one itself. The new child task is pushed onto core zero's own task queue.
Fib is a standard test for work-stealing because it makes many tiny tasks.
Why it works
- One copy replaces coherence. Because every core can read and write any other core’s scratchpad through the single global address space → the runtime keeps exactly one copy of each shared value and every core touches that same copy → so the coherence protocol these chips deliberately omit is simply not needed.
- The fork-join rule prevents races for free. Because a parent task cannot continue past a wait until all its children have joined → a parent and a stolen child never access the same variable at the same moment → so the single shared copy stays correct without locking the user’s data.
- Fast local memory beats off-chip memory. Because a scratchpad access takes two cycles while an off-chip access takes tens to hundreds → moving the frequently touched stack and task queue into unused scratchpad slashes the latency of the runtime’s most common operations → so workloads with many small tasks speed up sharply.
- Direct address math keeps stealing off the slow path. Because every core’s queue sits at the identical offset in its scratchpad → a thief computes a victim’s queue address by arithmetic rather than reading a shared table in off-chip memory → so a steal never has to touch slow shared memory to find its target.
- Automatic balancing beats fixed scheduling on uneven work. Because idle cores pull tasks from busy cores as the program runs → uneven and unpredictable work spreads itself evenly across the whole chip → so load imbalance turns from wasted idle cores into a measured speedup of up to 28.5 times.
What it costs (trade-offs and scope)
- Work-stealing adds instructions. Creating tasks, queuing them, and scheduling them all cost extra work, and the count rises further once the task queue is in fast scratchpad, because idle cores now attempt steals faster and fail more often. Those failed steals run on idle cores off the critical path, but for very fine-grained tasks the overhead is real — which is why already-balanced workloads see only small gains, or a slowdown of no more than about ten percent.
- It helps only some workloads. Workloads limited by off-chip memory bandwidth, such as sparse matrix-vector multiply and sparse matrix transpose, or workloads without frequent stack or queue operations, gain little, because their true bottleneck is memory traffic the runtime cannot remove.
- Deep recursion spills to slow memory. Each core has only four kilobytes of scratchpad, so a deep chain of recursive calls overflows to off-chip memory. The design keeps the newest frames in scratchpad and the oldest in off-chip memory, and optimizes for the common case where the whole stack fits.
- Some speedups need hardware or compiler help. The fast stack-overflow check uses a small hardware extension that watches the stack pointer and two new control registers. A pure-software version works too, but it adds two instructions to every function call and return.
- Read-only data must be duplicated. Removing the network hot spot means copying read-only values to every core, which uses extra memory and changes how the user’s code captures those values.
- Measured on one architecture. All results come from cycle-accurate simulation of a single, silicon-validated 128-core HammerBlade design. The authors argue the techniques carry to other scratchpad manycores with a shared address space, but that is reasoned, not measured here.
The evaluation
Three ways to run parallel work on a scratchpad manycore
| Property | Static parallel loops | Work-stealing, data in DRAM | Work-stealing, data in scratchpad |
|---|---|---|---|
| Load balancing | Automatic, idle cores steal | ||
| Handles irregular and nested parallelism | No, loops only | Yes | |
| Where hot runtime data lives | Not applicable | ||
| Needs cache coherence | No | No, one copy | |
| Speedup on uneven workloads | Baseline, one time | Up to tens of times |
Check yourself
Check your understanding
1. Why are manycore chips with software-managed scratchpad memories so hard to program?
2. The paper challenges a piece of conventional wisdom. What was that wisdom, and what did the paper show?
3. Why does the runtime place each core's task queue at the same fixed offset inside every core's scratchpad?
4. A workload is already perfectly balanced and limited by off-chip memory bandwidth. What does the paper predict for it?
Sources
The paper is “Beyond Static Parallel Loops: Supporting Dynamic Task Parallelism on Manycore Architectures with Software-Managed Scratchpad Memories” by Lin Cheng, Max Ruttenberg, Dai Cheol Jung, Dustin Richmond, Michael Taylor, Mark Oskin, and Christopher Batten, published at ASPLOS 2023, DOI 10.1145/3582016.3582020. The authors are at Cornell University, the University of Washington, and the University of California, Santa Cruz. The HammerBlade manycore development was funded by DARPA.
This explainer is written from the full text of the paper, obtained from the authors’ own copy hosted on the Cornell Computer Systems Laboratory publications page, which matches the ASPLOS 2023 proceedings and is distributed under a Creative Commons Attribution license. Everything above comes from the paper’s own sections: the introduction and background framing the manycore programmability challenge, the HammerBlade architecture (128 cores in a 16-by-8 mesh, RISC-V cores with four-kilobyte scratchpads, a partitioned global address space, and a relaxed-consistency memory model), and the fork-join, work-stealing programming model; the naive runtime that places all data in off-chip memory to keep a single copy; the three scratchpad optimizations (the hardware-and-software stack-overflow scheme with two new control registers, the fixed-offset scratchpad task queue with a separated lock, and read-only data duplication measured at a 1.57 times speedup on PageRank); the cycle-accurate register-transfer-level evaluation methodology on a silicon-validated design with one high-bandwidth memory channel; the nine workloads in four categories (static-balanced, static-unbalanced, dynamic-balanced, and dynamic-unbalanced); and the headline results of 1.2 to 28.5 times speedup for workloads that benefit, a slowdown of no more than about ten percent for those that do not, and up to 25 percent additional benefit from the scratchpad optimizations.