Parallel loops are easy to write but murderously hard to make fast on irregular workloads like sparse matrices and graphs, because spawning a task per loop iteration costs thousands of cycles while each iteration may do only tens — so programmers hand-tune a chunk size that never transfers between machines or inputs; this work from Northwestern and Carnegie Mellon builds HBC, the first compiler that automatically turns ordinary OpenMP-style C/C++ into binaries using heartbeat scheduling, which expresses all the parallelism but only materializes it at a fixed-rate runtime event, lifting irregular-workload speedups from 14.2 to 21.7 times on 64 cores with no manual tuning.
The argument in one glance
-
Problem
Parallel loops are easy to write but hard to make fast
Modern languages let you mark a loop as parallel — OpenMP's parallel for, Cilk, and the like — and you can nest one parallel loop inside another. But turning that expressiveness into speed on a real multicore machine is hard, because actually creating and managing parallel tasks has a cost that can wipe out the benefit of running them at all. This is especially punishing for irregular workloads like sparse-matrix math and graph analytics, whose performance depends heavily on the input.
-
What people did
Make the programmer choose a granularity by hand
The status quo puts the decision on the application programmer. They either spawn a task per iteration (and drown in overhead), or coarsen iterations into chunks and pick a chunk size by hand, hoping to balance the cost of parallelism against its benefit. Some automatic granularity-control schemes exist, and a recent idea called heartbeat scheduling even comes with formal guarantees.
-
Why it fell short
Hand-tuning does not transfer, and heartbeat needs assembly
A hand-picked chunk size does not carry over between machines (it depends on out-of-order width, inter-core costs, thread-creation costs) or between inputs (an irregular workload's balance shifts with the data), so the code becomes platform-specific and brittle, or it leaves performance on the table. Heartbeat scheduling would solve this in principle, but its existing implementations require programmers to restructure their code by hand, partly in assembly — months of work that only a few experts can do, with no compiler support.
-
This paper's idea
Compile ordinary parallel loops into heartbeat binaries automatically
HBC is the first compiler that takes plain C/C++ with high-level fork-join loops and automatically produces a binary that runs heartbeat scheduling. The program expresses all its potential parallelism and runs sequentially by default; a fixed-rate heartbeat event decides, at runtime, when to split a running task into fresh parallel tasks — amortizing task cost against real work and adapting to the input. A companion linker embeds the signaling and runtime, so what once took experts months in assembly now compiles in seconds and lifts irregular-workload speedups from 14.2 to 21.7 times on 64 cores.
Why this problem is worth solving
The reason a fixed chunk size cannot win on these workloads is that the right amount of work per task depends on data the programmer does not have at compile time. Consider a sparse matrix-times-vector multiply, where each row is a loop iteration and the work for that row is proportional to how many non-zero entries it has. On a well-behaved matrix the non-zeros are spread evenly, so any reasonable chunk of rows does about the same work. But on an arrowhead matrix — non-zeros packed into the first row, first column, and diagonal — the rows are wildly unequal: a few carry most of the work and the rest are nearly empty. Now static chunking backfires. Because the fork-join model puts a barrier at the end of the loop, the single unlucky task that landed the heavy rows dictates the finish time of the whole loop, while every other core sits idle waiting for it. To balance this you would need a finer chunk size, but a finer chunk means more tasks, and more tasks means more of the thousands-of-cycles spawn-and-manage overhead — which is ruinous when each light row does only tens of cycles of real work. The chunk size that balances load and the chunk size that controls overhead pull in opposite directions, and where the sweet spot sits depends entirely on the matrix, which is only known at runtime. That is why no compile-time constant can be right, and why the decision has to be made dynamically.
Heartbeat scheduling is worth building a compiler around because it is the first granularity-control idea that is both automatic and provably safe. Heartbeat scheduling postpones the decision of how much parallelism to create until runtime, and makes that decision at a regularly occurring event called the heartbeat, which fires at a fixed time rate as the program runs. The rule is simple: a task is only allowed to spawn more parallelism once it has run long enough to earn a heartbeat, so the cost of the new task is always amortized against a guaranteed amount of useful work already done. This gives two proven properties: task-related overheads stay well amortized (you never pay for parallelism you did not earn), and the asymptotic parallelism of the original program is preserved (you do not accidentally serialize work that could have scaled). Crucially, these guarantees do not depend on any platform-specific constant baked into the code — the programmer expresses all the parallelism their algorithm contains, and the runtime decides which portion to actually materialize and when, adapting continuously to how the computation is unfolding on this input, on this machine. The catch, before this paper, was that using it meant hand-writing your program in an unconventional structure down to the assembly level, which is why it had never left the hands of a few experts.
What people did before, and where it broke
- Spawn one task per loop iteration. Maximize parallelism by letting every iteration be its own task. Where it broke. Creating and managing a task costs thousands of cycles, so on irregular workloads whose iterations do only tens of cycles of work, the overhead slows execution by orders of magnitude instead of speeding it up.
- Hand-picked static chunking (OpenMP). Coarsen iterations into chunks and let the programmer set the chunk size to amortize task cost. Where it broke. The best chunk size depends on the input (an irregular workload’s balance shifts with the data) and the machine, so a hand-tuned constant is brittle, non-portable, and on skewed inputs leaves cores idle behind one overloaded task at the barrier.
- Automatic and oracle-guided granularity control. Predict future work to switch between serial and parallel execution, some with formal overhead bounds. Where it broke. The bounds need assumptions about runtime behavior that are hard to know, and the approach is not fully automatic — it asks programmers to annotate fork points with abstract cost functions, which is manual and often impractical.
- Manual heartbeat scheduling (TPAL). Get heartbeat scheduling’s provable guarantees by restructuring the program by hand. Where it broke. It required inserting promotion points, chunking, and closure logic by hand, partly in assembly, tuned per benchmark over months — leaving a provably good technique usable only by a handful of experts.
- The gap. Every path forced a bad trade: crippling overhead, brittle hand-tuning, impractical annotations, or months of expert assembly work. What was missing was a compiler that could take ordinary high-level parallel loops and automatically generate the unconventional structure heartbeat scheduling needs — which is exactly what HBC provides.
How HBC works
From ordinary parallel loops to an adaptive heartbeat binary
-
-
new
-
new
-
new
-
new
-
new
The idea
Express all the parallelism, and separate that from deciding when to realize it. The programmer’s job in HBC is only to say which loops may run in parallel; the entirely separate question of how much of that parallelism to actually create, and when, is handed to the runtime. The program is written as if every iteration could be its own task, but it runs sequentially until a heartbeat decides a split is worth it — so the expression of parallelism is fully decoupled from its materialization. Pulling apart two concerns that used to be tangled into one hand-tuned constant, so each can be handled where it belongs, is the same move the resize-scheduling work covered elsewhere on this site makes, separating what should be adjusted from when it should be adjusted so neither decision has to be frozen prematurely.
Only pay for parallelism once a task has earned it. A new task costs thousands of cycles, so the disaster is spawning one before it can pay for itself. Heartbeat scheduling refuses to split a task until it has already run for one heartbeat interval of useful work, which guarantees the spawn cost is amortized and, because the interval is measured in time rather than iterations, the guarantee holds no matter how lumpy the input is. Doing the expensive structural operation only when the workload proves it will actually pay off, rather than eagerly or on a fixed schedule, is the same discipline the page-table replication work covered elsewhere on this site follows, replicating only when the access pattern shows the copy will earn back its cost instead of paying for it up front everywhere.
Automate in a compiler what only experts could do by hand. Heartbeat scheduling was provably good but practically inaccessible, because materializing it meant restructuring a program into an unconventional shape down to assembly — inserting promotion points, generating loop closures, chunking, and wiring a signaling mechanism, tuned per benchmark over months. HBC turns that entire manual craft into automatic compiler passes and a linker, generating even the quadratically-many leftover tasks a human could never write out, and finishing in seconds. Taking an optimization that is impractical to apply by hand and making a compiler perform it automatically and at scale is exactly the contribution the recommendation-model compiler work covered elsewhere on this site makes, mechanizing a transformation whose payoff is real but whose manual application would be hopeless.
Following a sparse multiply through HBC
Balancing an arrowhead matrix on 64 cores
Tracing the compiled sparse multiply shows the heartbeat splitting work as it goes.
Step 1 of 5
Start sequential, with all parallelism latent
The compiled sparse matrix-times-vector routine begins as one task running its outer row loop and inner column loop straight through. No tasks have been spawned, so there is zero parallel overhead — the potential parallelism is expressed but not yet realized.
HBC replaces each loop with a call to a resumable loop-slice task over its whole iteration space.
Why it works
- Sequential-by-default means overhead is bounded. Running straight through costs nothing until parallelism is actually needed → a task spawns only when a heartbeat proves it has already done a full interval of useful work → so task overhead is always amortized and never wipes out the speedup the way spawning-per-iteration does.
- A time-based heartbeat tracks real work, not iteration counts. The heartbeat fires at a fixed time rate rather than after a fixed number of iterations → so the decision to parallelize follows how much work has actually elapsed, however unevenly the input distributes it → so irregular workloads stay balanced with no input-specific tuning.
- Promoting the outermost loop first exposes coarse parallelism fast. Splitting the outer loop targets the largest available chunks of independent work → so a handful of promotions is enough to fill every core → so the scheme scales up instead of drowning the machine in tiny tasks.
- The leftover task takes work off the critical path. Giving the current iteration’s tail its own complete closure → lets it run in parallel with the two loop-slice halves instead of blocking their continuation → so HBC generates an extra level of parallelism and beats even the hand-tuned prior system on kmeans, mandelbrot, and srad.
- A poll is far cheaper than an interrupt. A timestamp poll costs about 50 cycles against roughly 3800 for a hardware-interrupt event → so even ten polls per heartbeat cost an order of magnitude less than one interrupt, and adaptive chunking keeps polls rare → so software polling matches hardware interrupts with no special OS support at all.
What it costs (trade-offs and scope)
- Heartbeat scheduling hurts regular workloads. When every iteration does about the same work, the promotion and polling machinery is pure overhead a balanced loop never needed — HBC runs slower than a plain OpenMP static schedule on regular benchmarks, so an ideal compiler would keep both and choose per loop.
- The chunk-size bookkeeping can land on the critical path. For extremely fine-grained loops, tracking and transferring the remaining chunk count before each poll adds cost that is not amortized — on the arrowhead sparse matrix HBC is about 22 percent slower than the hand-tuned prior system and adds over 58 percent overhead versus the sequential baseline.
- It targets loops, not recursion. HBC handles nested DOALL loops; the recursive fork-join programs the prior TPAL work also covered are out of scope here, so it is not yet a complete replacement for that work.
- The programmer still marks the parallel loops. HBC removes the granularity decision but not the annotation — it relies on OpenMP-style DOALL pragmas to know which loops may legally run in parallel.
- It is tied to LLVM and x86. HBC builds on the NOELLE and LLVM 14 framework, and the low-level pieces — timestamp polling, the rollforward tables, the APIC-timer kernel module — are x86-specific; the hardware-interrupt path needs a kernel module, though the default software-polling path avoids it.
- The evaluation disables vectorization. Following the prior work’s setup, benchmarks were compiled with vectorization passes turned off, so how heartbeat scheduling interacts with auto-vectorization is not measured.
The evaluation
Three ways to set the granularity of a parallel loop
| Property | One task per iteration | Hand-tuned static chunking | HBC (heartbeat) |
|---|---|---|---|
| When task cost is paid | Amortized over a fixed chunk | ||
| Balance on a skewed input | Balanced but overwhelmed by overhead | ||
| Tuning effort | None, but unusable | ||
| Irregular-workload speedup on 64 cores | Orders of magnitude slowdown | 14.2 times (OpenMP) |
Check yourself
Check your understanding
1. Why does a hand-picked static chunk size fail to make an irregular workload fast?
2. What is the core idea of heartbeat scheduling that HBC automates?
3. What is the "leftover task" that HBC generates, and why does it matter?
4. Which statement best reflects the evaluation and scope of HBC?
Sources
The paper is “Compiling Loop-Based Nested Parallelism for Irregular Workloads” by Yian Su, Mike Rainey, Nick Wanninger, Nadharm Dhiantravan, Jasper Liang, Umut A. Acar, Peter Dinda, and Simone Campanoni, published at ASPLOS 2024, DOI 10.1145/3620665.3640405. The authors are at Northwestern University and Carnegie Mellon University, and the system (HBC) and its benchmarks are open-source.
This explainer is written from the full 19-page text. Everything above comes from the paper’s own sections: the introduction and background motivating the granularity-control problem (task-creation costs of thousands of cycles versus tens-of-cycles iterations, the arrowhead-matrix example, the fork-join barrier) and explaining heartbeat scheduling, promotion, the outer-loop-first policy, and the limits of the prior manual TPAL implementation; the HBC compiler pipeline covering loop-nested-tree outlining and inter-procedural loop IDs, loop-slice task generation with the loop-slice-task context and loop chunking, the leftover-task generation algorithms, and task linking; the heartbeat linker with software polling and rollforwarding-based hardware interrupts (the 250-line Perl rollforward compiler); the runtime with adaptive chunking and the Linux kernel module (about 3800 cycles per event); and the evaluation on a 64-core Intel Xeon Platinum 8375C at a 100-microsecond heartbeat rate, reporting the 14.2-to-21.7-times improvement over OpenMP on irregular workloads, the comparison to hand-written TPAL (including the kmeans, mandelbrot, and srad gains and the spmv chunk-size-transferring slowdowns), the software-polling-versus-interrupt comparison (about 50 versus 3800 cycles), the adaptive-chunking overhead analysis (the 7.5-times slowdown without chunking), the regular-workload results where static scheduling wins, and the OpenMP granularity experiments where parallelizing all DOALL loops caused several benchmarks not to finish.