Task-based parallel runtimes like Legion take a sequential-looking program, watch the stream of tasks it issues, and figure out at run time which tasks depend on which so they can run in parallel — but that dependence analysis is costly per task, so it dominates once tasks get small; the fix is tracing (memoize the analysis of a repeated fragment and replay it), but until now a programmer had to hand-annotate the repeats, which is brittle and nearly impossible for programs built by composing libraries; this paper (Stanford and NVIDIA — Rohan Yadav, Michael Bauer, Alex Aiken, Fredrik Kjolstad, and colleagues) presents Apophenia, which finds the repeated fragments automatically by hashing the task stream into tokens and running fast online string algorithms over it — matching hand-traced performance (0.92 to 1.03 times) and speeding up previously untraceable programs by up to 2.82 times on the Perlmutter and Eos supercomputers.
The argument in one glance
-
Problem
The runtime figures out parallelism at a cost that dominates for small tasks
An implicitly parallel task-based runtime system lets you write a program that looks sequential, issuing a stream of tasks, while the runtime automatically finds the parallelism. It does this with dynamic dependence analysis: as each task is issued, the runtime examines the data the task reads and writes and works out which earlier tasks it depends on, so independent tasks can run at the same time and communication can be arranged. This is powerful — it lets high-level libraries be composed on top of the runtime — but the analysis costs real time for every task. When tasks are large, that cost is negligible. When task granularity drops, the per-task analysis overhead comes to dominate, which puts a floor on how small a task, or how fine-grained a problem, can be and still run efficiently. In systems like Legion the per-task overhead can be around a millisecond, which is enormous for a small task. So exactly when you want many small tasks for flexibility or scale, the very machinery that finds the parallelism becomes the bottleneck.
-
What people did
Trace repeated fragments by hand, and replay the memoized analysis
The established fix is tracing. Programs are usually iterative, issuing the same fragment of tasks over and over, so a programmer annotates such a repeated fragment as a trace. The first time the fragment runs, the runtime memoizes its dependence analysis; every later time, it replays the stored result instead of re-analyzing. This can cut the per-task overhead dramatically — in Legion from around a millisecond to around a hundred microseconds — widening the range of applications a task-based runtime can handle.
-
Why it fell short
Manual annotation is brittle and breaks down for composed programs
Tracing works, but it depends on the programmer correctly marking the repeated fragments, and that is fragile. The annotations are easy to get wrong, and they assume the programmer can see where the real repetition is. That assumption fails for modern programs built by composing independent high-level components and libraries, where no single person sees the whole stream of tasks the runtime actually receives. An intuitive trace placed around a program's main loop may not even correspond to a genuinely repeated fragment in the underlying task stream, because the composition of libraries reshapes what repeats. So the very programs that most need tracing — large, modular, composed ones running at scale — are the hardest to annotate by hand, and many simply go untraced and pay the full analysis cost. What is needed is a way for the runtime to discover the repeated fragments itself, from the task stream, without any programmer annotation.
-
This paper's idea
Automatically discover the repeats in the task stream, like a trace-based JIT
Apophenia is a system that automatically traces the dependence analysis of a task-based runtime, removing the annotation burden and letting complex, composed programs be traced for the first time. Its insight is to treat trace-finding as a pattern-detection problem over the runtime's stream of tasks — the problem of automatic trace identification, close in spirit to a trace-based Just-In-Time (JIT) compiler that detects hot repeated paths at run time. But unlike a JIT, Apophenia sees only a raw stream of tasks, with no control-flow landmarks like function boundaries or loop labels to guide it, so it must find repetition in the operations alone. It does this with a series of fast online string analyses. First, it turns each task, together with its data (region) arguments, into a hash token, converting the task stream into a string of tokens on which string-processing algorithms can run directly. Second, it finds repeated, non-overlapping substrings in that token string to propose traces; because standard suffix-tree methods for non-overlapping repeats run in quadratic time (too slow online), the authors design an efficient repeated-substring algorithm (using a suffix array) that assembles a set of traces covering much of the stream. Third, it runs online as tasks arrive, memoizing the analysis of a newly found trace and replaying it when the same fragment recurs. Built into the Legion runtime, Apophenia matches hand-traced performance (0.92 to 1.03 times) and speeds up previously untraceable programs by 0.91 to 2.82 times on the Perlmutter and Eos supercomputers.
Why this problem is worth solving
Task-based runtimes are how much of modern high-performance and scientific computing gets its parallelism, and their per-task overhead sets a hard limit on what they can do. In an implicitly parallel programming model, you write code that reads as if it runs sequentially, but instead of executing operations directly it issues them as tasks to a runtime system such as Legion. Each task names the data it will read and write (in Legion, regions of data), and the runtime performs dynamic dependence analysis: it inspects each newly issued task against the ones already in flight to determine which it truly depends on, so it can run independent tasks concurrently, schedule them across many nodes of a supercomputer, and move data where it is needed. The great advantage is composability — high-level libraries can be layered on top, and the runtime sorts out the parallelism across all of them without the programmer coordinating it. The catch is that this analysis is not free; every task pays for it. When tasks are coarse (long-running), the overhead is lost in the noise. But there is strong pressure toward finer-grained tasks — for flexibility, for load balance, and to scale to more processors on smaller problems — and as tasks shrink, the fixed per-task analysis cost becomes the dominant expense, effectively setting a floor on the smallest problem size that runs efficiently. Lowering that overhead directly widens the set of applications for which a task-based runtime is viable, which is why it has been a central concern for these systems.
The established remedy helps enormously but has a flaw that bites exactly where it is most needed. Because task-based programs are typically iterative — a simulation step, a training iteration, a solver sweep repeated thousands of times — the same sequence of tasks recurs again and again. Tracing exploits this: mark a repeated fragment, and the runtime memoizes its dependence analysis the first time and replays that memoized result on every recurrence, skipping the expensive re-analysis. In Legion this can cut per-task overhead by roughly an order of magnitude, from around a millisecond to around a hundred microseconds, which is the difference between fine-grained tasks being impractical and being efficient. The problem is that traces are placed by hand. A programmer must identify the repeated fragments and annotate them, and this is brittle: the annotation must line up precisely with what actually repeats in the task stream. In a simple program written by one person, that may be manageable. But real high-performance programs are increasingly assembled by composing independent libraries and components, and then no one has a global view of the task stream the runtime sees. A trace the programmer draws around the visible main loop may not match a truly repeated fragment underneath, once library calls are interleaved. So the modular, large-scale programs that would benefit most from tracing are precisely the ones where manual annotation is hardest or impossible, and they end up paying the full analysis cost. Removing the human from the loop is what makes tracing usable for these programs.
What people did before, and where it broke
- Pay the full dependence analysis on every task. Let the runtime analyze each task as it is issued, with no memoization. Where it broke. The per-task cost (around a millisecond in Legion) dominates once tasks are small, capping how fine-grained a program can be while staying efficient.
- Manual tracing with programmer annotations. Have the programmer mark repeated fragments so the runtime memoizes and replays their analysis. Where it broke. It works but is brittle — the annotation must match the real repetition, and mistakes are easy.
- Manual tracing for composed, modular programs. Apply the same annotation approach to programs built from independent libraries. Where it broke. No one sees the whole task stream, so a trace around the visible main loop may not correspond to a genuinely repeated fragment underneath; such programs are hard or impossible to trace by hand and go untraced.
- Borrow control-flow landmarks like a language JIT. Detect repeated regions using function boundaries or loop labels, as trace-based JIT compilers do for bytecode. Where it broke. The runtime sees only a raw stream of tasks with no such landmarks, so it cannot rely on code structure to find the repeats.
- The gap. No system automatically identified the repeated fragments directly from a task-based runtime’s operation stream, so tracing could not be applied without manual annotation, and complex composed programs could not be traced at all.
How Apophenia works
Finding repeats in the task stream and memoizing their analysis
-
-
new
-
new
-
new
-
new
-
new
The idea
Detect the repeated work at run time and memoize it, instead of recomputing it. Apophenia’s foundation is the same one behind tracing generally: a program’s heavy dynamic work — here, dependence analysis — repeats, so capture it once and reuse it. Apophenia’s advance is to find the repeats automatically. Capturing a program’s recurring dynamic behaviour at run time and compiling or memoizing it so later repetitions are cheap is the same principle the work on faster machine learning through dynamic Python bytecode transformation covered elsewhere on this site is built on, turning observed repetition into reused, pre-digested work. Apophenia applies that principle to a task-based runtime’s dependence analysis, discovering what repeats from the task stream rather than from source code.
Recover the program’s structure that the runtime does not see. The hard part is that the runtime gets only a flat stream of tasks, with none of the loop or function structure that would reveal repetition; Apophenia reconstructs that structure by finding repeated substrings in the stream. Recovering the latent structure of a task-parallel program that has been flattened into a stream, so a runtime can exploit it, is the same problem the work on accelerating task-parallel workloads by recovering program structure covered elsewhere on this site tackles, inferring the shape of the computation to run it better. Apophenia recovers repetition specifically, and uses it to decide what to trace.
Make the detection an efficient online string computation. Because trace-finding must run while the program executes, over a growing stream, Apophenia treats it as an online string-analysis problem — hashing tasks into tokens and finding non-overlapping repeats fast enough to keep up. Turning a runtime pattern-detection task into an efficient analysis over a stream of tokens is the same move the work on static analysis for efficient streaming tokenization covered elsewhere on this site makes, processing a token stream cheaply enough to be practical. Apophenia had to design a new repeated-substring algorithm to do this, since the natural suffix-tree approach was too slow, and the result is a detector that finds traces without slowing the program down.
Following a composed program through Apophenia
Tracing an iterative program assembled from libraries, with no annotations
A trace, drawn from the paper, of how Apophenia discovers and reuses a repeated fragment in a task stream.
Step 1 of 5
A composed program issues tasks with no traces marked
An iterative program built from several libraries runs on a supercomputer, issuing tasks to Legion. The programmer has not (and could not easily) annotate traces, because the repetition lives in the interleaved task stream, not in any one visible loop.
Without help, every task pays the full dependence analysis.
Why it works
- Iterative programs repeat, so the analysis is reusable. A task-based program issues the same fragment of tasks many times → so the dependence analysis for that fragment is identical each time → so memoizing it once and replaying it eliminates almost all the repeated cost.
- Hashing turns tasks into a searchable string. Repetition in a raw task stream is hard to spot directly → but hashing each task and its arguments into a token makes recurrences into identical subsequences → so string algorithms can find the repeats.
- A custom algorithm keeps detection online. Standard suffix-tree methods for non-overlapping repeats are quadratic and too slow to run live → but a purpose-built suffix-array algorithm finds them efficiently → so Apophenia can identify traces without stalling the running program.
- Working from the stream handles composed programs. Manual annotation needs a global view no one has for modular programs → but detecting repeats in the runtime’s own task stream needs no such view → so programs assembled from independent libraries can finally be traced.
- Automatic detection matches hand-tuning. Skilled programmers place good traces manually when they can → but the same repeats can be found automatically from the stream → so Apophenia reaches 0.92 to 1.03 times manual performance while removing the annotation burden entirely.
What it costs (trade-offs and scope)
- The detection itself runs during execution. Apophenia hashes every task and searches the growing token stream online, which is work the program would not otherwise do; the algorithms are designed to be efficient, but automatic detection is not free and must stay cheap enough not to erode the savings.
- It can slightly trail hand-tuning in the best case. Against manually traced programs, Apophenia ranges from 0.92 to 1.03 times — usually matching or beating manual tracing, but occasionally a little slower, since an expert who can annotate perfectly may still find a marginally better trace than the automatic detector.
- Benefits depend on there being real repetition. The whole approach relies on the task stream containing repeated fragments; a program with little or no repetition, or whose repeats are too small to be worth memoizing, gains little, and one of the previously untraced results is a slight slowdown (0.91 times).
- It is demonstrated within one runtime. The implementation targets the Legion runtime and its region-based tasks; the ideas are about task streams in general, but applying them elsewhere would require integrating the hashing and detection into another runtime’s task and dependence machinery.
- It memoizes analysis, not correctness-checking of change. Replaying a memoized trace assumes the recurring fragment truly is identical; the system must correctly identify genuine repeats (which the hashing and formulation aim to ensure), because replaying the wrong analysis would be incorrect, so the trace-identification criteria carry real weight.
The evaluation
Reducing per-task dependence-analysis overhead
| Property | No tracing | Manual tracing | Apophenia (automatic) |
|---|---|---|---|
| Per-task analysis overhead | |||
| Programmer annotation needed | |||
| Works for composed, modular programs | |||
| Performance vs manual tracing | |||
| Effect on previously untraced programs |
Check yourself
Check your understanding
1. Why does dependence-analysis overhead become a problem in task-based runtimes, and how does tracing address it?
2. What was the limitation of existing tracing that Apophenia removes?
3. How does Apophenia automatically find the repeated fragments in the task stream?
4. Predict: you run a large program assembled from several libraries — one you could not trace by hand — under Apophenia, and separately a simple program an expert has already traced perfectly. What should you expect in each case?
Sources
The paper is “Automatic Tracing in Task-Based Runtime Systems” by Rohan Yadav, Michael Bauer, David Broman, Michael Garland, Alex Aiken, and Fredrik Kjolstad (Stanford University, NVIDIA, and KTH Royal Institute of Technology), published at ASPLOS 2025, DOI 10.1145/3669940.3707237. It is licensed CC BY.
This explainer is written from the paper’s full text (arXiv:2406.18111). Implicitly parallel task-based runtime systems perform dynamic dependence analysis to discover dependencies and extract parallelism from sequential programs, and this analysis becomes expensive as task granularity drops. Tracing memoizes the dependence analysis of programmer-annotated repeated fragments and replays it, greatly reducing overhead, but manual annotation is brittle and not easily applicable to complex programs built by composing independent components. Apophenia automatically traces the dependence analysis of task-based runtime systems, removing manual annotations and enabling new and complex programs to be traced. It identifies traces dynamically through a series of dynamic string analyses that find repeated program fragments in the stream of tasks issued to the runtime: hashing each task and its region arguments into a token stream, finding repeated non-overlapping substrings with a custom suffix-array-based algorithm (because standard suffix-tree approaches to non-overlapping repeats are quadratic), assembling a high-coverage set of traces, and memoizing then replaying each trace’s analysis as it recurs — framed as automatic trace identification, analogous to trace-based just-in-time compilation but over a task stream lacking control-flow landmarks. Implemented within the Legion runtime, Apophenia comes between 0.92 and 1.03 times the performance of manually traced programs and effectively traces previously untraced programs to yield speedups between 0.91 and 2.82 times on the Perlmutter and Eos supercomputers. No numbers beyond the paper’s own have been introduced; exact algorithm details, the trace-identification formulation, and full results should be confirmed in the paper.