RPG2: Robust Profile-Guided Runtime Prefetch Generation

Software prefetching can nearly double a memory-bound program's speed or slow it by 70%, and which one you get depends on the input data and the exact processor model, so no compiler can decide correctly ahead of time; RPG2 (Penn, UC Santa Cruz, Michigan and Intel) attaches to an already-running C or C++ process, samples where its cache misses come from, rewrites the hot function with prefetch instructions built out of a backward slice, moves the live threads onto the new version mid-execution, tunes how far ahead to prefetch by watching the program's own instructions-per-cycle, and — the part no static compiler can offer — steers execution back to the untouched original when the whole thing turns out to be a loss.

Why this problem is worth solving

Out-of-order execution can hide the cost of a first-level cache miss, but not a miss that goes all the way to memory, and modern datasets are large enough that those are common.

The parameter that decides everything is how far ahead to go.

What people did before, and where it broke

• Rely on the hardware prefetchers already in the chip. They are free, they are always on, and for regular strided access they work well. Where it broke. The authors measured that modern processors handle strides well but still struggle with indirect access — one array supplying the indices into another — which is precisely the pattern in graph workloads and the one that produces the expensive misses.
• Have the programmer insert prefetch intrinsics by hand. The developer knows the access pattern better than any analysis, and the compilers expose a builtin for exactly this. Where it broke. Knowing the pattern is not the hard part. The developer must also extract the code that computes the address, place the prefetch at a point that gives the right lead time, and pick a distance — and the correct lead time depends on out-of-order execution and the memory hierarchy in ways the paper describes as almost impossible for a person to resolve.
• Static compiler passes that analyse the code and insert prefetches automatically. A large body of work does this without any programmer involvement. Where it broke. They face the same three-way trade among accuracy, coverage and timeliness, with strictly less information than the programmer had, and they still have to commit to one distance.
• Profile first, then compile — the profile-guided approach. The most recent such system profiles the program, works out the miss behaviour, and inserts prefetches accordingly, which is a genuine improvement on static analysis alone. Where it broke. It produces one binary with one fixed set of prefetches. You can re-profile and build another for a different input or a different processor, but then those binaries have to be stored, organised and selected at launch time, and given how much the behaviour varies the paper argues it is very hard to predict which one you want. Profiling is also slow — the paper notes several minutes for a benchmark in the system it compares against.
• The gap. No system could change its mind. Once the prefetches were in the binary, the program was committed, and in the cases where prefetching turned out to be harmful — which the paper finds are numerous — there was no way to recover the original performance.

How RPG2 optimises a process that is already running

The idea

Accept that the right answer is not knowable before the program runs, and stop trying to guess it. The paper spends its first pages establishing this rather than assuming it, and the evidence is the most valuable thing in it. Across dozens of real graph inputs — far more than earlier work used — the best prefetch distance for one shortest-path benchmark is 20 to 34 iterations on one graph and 1 to 2 on another. On a page-rank benchmark, moving between two Intel generations does not shift the optimum, it flips the sign: an input that gains nearly 2x on one machine loses on the other, and a second input does the opposite. On breadth-first search, most inputs lose, some of them by 50 to 70%. A profile-guided compiler can respond to all of this in principle, by producing a binary per combination, and the paper is careful to say why that is not a real answer — the binaries have to be stored, organised, and chosen at launch, and nothing can predict which one is right. Confronting the operational cost of static profile-guided optimisation rather than only its performance is the same argument made by the warehouse-scale relinking work covered elsewhere on this site, which found that the pipeline around the optimisation is as much of a constraint as the optimisation itself.

Build the prefetch so that it can be slotted into a live function and slotted back out. The mechanism that makes everything else possible is a design constraint the authors imposed on themselves: the inserted code must change no data layout at all. A backward slice from the missing load gives the instructions that compute its address; those are replayed for a future iteration, guarded by a bounds check adapted from the loop exit condition so that reading ahead cannot touch unmapped memory, and the load itself becomes a prefetch. Everything is restored afterwards. The authors tried the more natural route first, adapting an existing prefetching compiler that works at the intermediate-representation level, and abandoned it because inserting at that level perturbs register allocation throughout the function — a variable in a register in one version and on the stack in the other — which makes moving a live thread between versions intractable. Reconstructing the address computation by slicing backwards from the load that misses is the same technique as the critical-slice prefetching work covered elsewhere on this site, applied here to generate code rather than to steer a hardware structure.

The real contribution is the undo. Prefetching is described in the paper as a double-edged sword, and the framing of the whole system is not that it prefetches better but that it makes prefetching safe to attempt. Because the original function is never overwritten — the optimised copy goes somewhere else in the address space — there is always somewhere to return to, and returning is cheap. Within a few seconds of deciding that prefetching is a loss, the program is back to exactly its original code, with all the original pointers still valid. That changes what the optimisation is for: not a gamble on the average case, but a bounded experiment run against the actual workload, where the downside is a few seconds of tuning overhead rather than a persistent regression. An optimisation that is only deployable because there is a guaranteed path back to the unoptimised state is the same bargain struck by the speculative logging work for persistent memory covered elsewhere on this site, where the aggressive path is worth taking precisely because undoing it is always available.

Walking one function through RPG2

There is a real tension in choosing how long to sample. More data means better decisions; less data means the optimisation starts sooner and covers more of the run. Two seconds is the default. The paper measures the effect and finds it mild — longer sampling activates the optimisation somewhat more often, but by Amdahl reasoning it also leaves less program left to accelerate.

Why it works

• The measurement is taken from the program itself, at the moment it matters. Instructions per cycle is observed on the real input on the real machine → no model of memory latency, loop speed or reordering is needed, and none would have been accurate anyway → the search converges on a distance that is right for conditions no compiler could have anticipated.
• The inserted code changes nothing but timing. The prefetch sequence spills and restores its scratch register and leaves data layout untouched → a live thread can be moved between the two versions without any map from variables to storage locations → on-stack replacement becomes feasible in a language that has no runtime support for it.
• The original is kept rather than overwritten. The optimised function is placed at a new address → every existing code pointer stays valid and the unoptimised version remains executable → rolling back is a matter of patching call sites and translating program counters, not of reconstructing anything.
• Only the edits need a pause. Sampling, slicing and rewriting run concurrently with the target → the stop-the-world portions are a 3 to 4 millisecond insertion and a roughly 1 millisecond edit per trial → the tuning search is visible in a live trace as a shallow dip rather than a stall.
• Cost is proportional to benefit, and stops when the benefit does. Once a distance is installed RPG2 detaches entirely → the only ongoing cost is the prefetch code itself, and if prefetching was rolled back there is no ongoing cost at all → the authors rejected an alternative design that pre-pads hot loops with placeholder instructions precisely because it cost up to 5% even when unused.

What it costs (trade-offs and scope)

• Instructions per cycle is not always telling the truth. The paper gives its own failure: on one shortest-path input, a low-IPC program phase during profiling followed by a higher-IPC phase later causes RPG2 to credit prefetching for an improvement that was really a phase change, so it keeps a configuration that is actually a slowdown. The authors state the conclusion plainly, that IPC alone is not always a good performance indicator.
• The search assumes the landscape is smooth, and sometimes it is not. On the random-access benchmark, distances that are multiples of eight perform far better than everything else. A gradient-then-binary search glides straight past that, and the paper reports a sizeable gap to both the manual and the offline-optimal configurations there.
• All prefetch sites must share one distance. Searching them independently scales exponentially in the number of sites, so RPG2 forces them equal. One benchmark has two prefetchable loads, and the paper shows cases where asymmetric distances are better — sometimes symmetric is the worst configuration of all.
• The pattern coverage is narrow by design. Three access categories are supported, all built around arrays and loop induction variables. Pure pointer chasing without arrays is left to future work, and the slicing cannot follow dependencies through general memory or through conditional control flow with multiple reaching definitions.
• The benchmarks were modified to make this work. Each was extended to run at least a minute, and each was hand-annotated to signal the end of its initialisation phase so that RPG2 would not profile a phase unrepresentative of the rest. Detecting phases automatically is named as future work. Programs are also assumed to have one or two small hot loops, the same assumption prior prefetching compilers make.
• The comparison baseline is missing on three of the seven benchmarks. The profile-guided compiler RPG2 compares against would not reliably generate prefetch instructions for shortest-path, breadth-first search or random-access after the running times were extended, and consulting its authors did not resolve it — so on those benchmarks there is no static-compiler comparison at all.
• The prefetch code is not free in instruction count. Half the inputs see under a 15% increase in dynamic instructions and the worst case is 37%. Those costs are inside the reported speedups, but they are the reason a prefetch that fails to hit anything is actively harmful.
• The evidence that it works is indirect. The authors validate against last-level miss rates and find the relationship between miss reduction and speedup is not especially strong. They tried using miss rate as the tuning signal instead of IPC and could not find good distances with it, attributing the remainder to misses elsewhere in the hierarchy and to bandwidth effects.

The evaluation

Check yourself

Sources

The paper is “RPG2: Robust Profile-Guided Runtime Prefetch Generation” by Yuxuan Zhang, Nathan Sobotka, Soyoon Park, Saba Jamilan, Tanvir Ahmed Khan, Baris Kasikci, Gilles A. Pokam, Heiner Litz and Joseph Devietti, published at ASPLOS 2024 Volume 2, pages 999-1013, DOI 10.1145/3620665.3640396. The authors are at the University of Pennsylvania, the University of California Santa Cruz, Columbia University, the University of Washington and Intel.

This explainer is written from the full text, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 4: the input-sensitivity study on the shortest-path benchmark with its 20-to-34 and 1-to-2 optimal ranges; the microarchitecture-sensitivity study on page rank where two inputs swap which processor favours them; the breadth-first search results with their 50 to 70% slowdowns; the four-phase design with precise event sampling filtered at a tenth of a function misses and a two-second default; the backward slicing rules and their stated limits around non-stack memory and conditional control flow; the prefetch kernel structure with its scratch-register spill, its inverted bounds check and its no-op correctness criterion; the account of why the intermediate-representation approach was abandoned and why the placeholder-instruction alternative was rejected at up to 5% cost; the on-stack replacement mechanism using the rewriter address translation table, including single-stepping a thread out of the prefetch kernel during rollback; the three-stage distance search with its random start in 1 to 100, its cap at 200 and its 0.3-second IPC measurements; the latency table with roughly 8 seconds of total attachment, 26 to 32 milliseconds of rewriting, 3 to 4 milliseconds of insertion and 1.1 to 1.4 milliseconds per distance edit over 8.8 to 12.7 edits; the distance-accuracy histogram over 120 single-optimum inputs; the instruction-count histogram with half under 15% and a 37% worst case; the phase-transition failure on one shortest-path input; the multiple-of-eight behaviour on random access; and the classification table showing that fewer than half of inputs have the easy asymptotic shape.