PDIP: Priority Directed Instruction Prefetching

Bhargav Reddy Godala, Sankara Prasad Ramesh, Gilles A. Pokam, Jared Stark, André Seznec, Dean M. Tullsen and 1 other

Server software has grown so large that its INSTRUCTIONS no longer fit in the caches, and one measured workload loses more than half its issue slots waiting for code to arrive; decades of work attacked this by reducing instruction cache misses, but modern processors already run their branch predictor far ahead of execution and quietly prefetch almost everything it predicts, so most misses now cost nothing at all and the miss count has stopped predicting performance; this paper (Princeton, UCSD, Intel and INRIA — an ASPLOS 2024 best paper) shows the misses that still hurt are structurally identifiable, being the ones landing just after a branch mispredict has flushed the queue the prefetcher was running ahead in, and that roughly 5 percent of cache lines cause 56 percent of the damage — so it prefetches only those, triggered by the very mispredict that created the problem.

The argument in one glance

Problem

Server processors are starved of code, not data

Data centre software stacks are now many layers deep, and their INSTRUCTION footprints have outgrown the instruction cache and frequently the second-level cache as well. Measured on real hardware, the Cassandra database spends 53.6 percent of its issue slots blocked waiting on the front end and only 18.9 percent actually retiring work — nearly three lost for every one used. Across the sixteen workloads studied here, the instruction cache misses about 86 times per thousand instructions. Simply building a bigger instruction cache is not an easy answer, because it sits on a timing-critical path and costs area and power.
What people did

Predict which code will be needed and fetch it early

The natural response is an instruction prefetcher: watch the pattern of misses, learn which cache lines follow which, and pull them in before they are demanded. A substantial literature does this well, and the state of the art at the time — the Entangling Instruction Prefetcher — records how long each miss took and associates the missing line with whatever was accessed that many cycles earlier, so next time the line arrives just in time. Judged on the metric these designs were built for, reducing instruction cache misses, they succeed.
Why it fell short

Real processors already hide most misses, so the miss count stopped mattering

Modern processors implement a DECOUPLED FRONT END, in which the branch predictor runs far ahead of execution, filling a queue of upcoming fetch targets, and every address entering that queue is prefetched immediately. This hides most instruction cache misses entirely — so a prefetcher that reduces miss counts is largely spending its budget on misses that were already free. Prior work showed that the measured gains of recent prefetchers mostly VANISH once evaluated on a machine with even a modest 24-entry queue, and much of that literature was never evaluated against such a machine at all. The entangling prefetcher with a table over 200KB — six times the instruction cache — yields 1.5 percent at a practical budget, and can actively HURT when combined with a criticality-aware cache policy.
This paper's idea

Find the misses the runahead cannot hide, and trigger on what caused the gap

This paper (Princeton, UCSD, Intel and INRIA — Godala, Ramesh, Pokam, Stark, Seznec, Tullsen, August; an ASPLOS 2024 best paper) starts from a deduction rather than a heuristic. The runahead only works while the queue is full; the queue is only empty just after something flushed it, such as a branch mispredict. Therefore any miss that actually stalled the front end must have occurred shortly after such an event. That makes the harmful misses structurally identifiable, and they are few: about 10 percent of lines cause 62 percent of the stall cycles, and 5 percent cause 56 percent. It also hands over a free TRIGGER — the disrupting branch itself, which is guaranteed to exist and to arrive early enough. In 43.5KB it delivers 3.15 percent more instructions per cycle against a strong baseline, against 1.5 percent for the prior best at a comparable budget.

Why this problem is worth solving

The mechanism that makes this problem interesting is also the one that solved most of it already.

In a DECOUPLED FRONT END, the part of the processor that predicts where execution will go next is separated from the part that actually fetches instructions, with a queue between them called the FETCH TARGET QUEUE. The branch predictor runs ahead filling this queue with the addresses it expects to be needed, and crucially, every address is prefetched into the instruction cache the moment it ENTERS the queue rather than when it reaches the fetch unit. Because the predictor can generally produce addresses faster than the back end consumes instructions, the queue normally stays full, and its depth determines how far ahead the prefetching runs. That head start is usually enough to cover a full instruction cache miss and sometimes a second-level miss too. This design has been in shipping processors for over a decade, and it is very effective: adding it to the simulator used here improved performance by 27.1 percent on its own

Its success is exactly what makes the remaining problem hard to see.

The runahead only protects you while the queue is FULL. A branch mispredict flushes the whole front end, the queue included, and after that flush the processor resumes from a corrected address with no runway at all — addresses now enter the queue barely ahead of when they are demanded. So a cache miss landing shortly after a mispredict is exposed in full, while an identical miss occurring during steady running costs nothing. A line is called FRONT-END CRITICAL when it retired an instruction, missed in the instruction cache, and actually produced front-end stalls as a result. The concentration is extreme: roughly 10 percent of lines are front-end critical, and they account for 62 percent of all the cycles the decoder spends starved. Narrowing to lines costing more than 10 cycles each gives 5.08 percent of lines causing 56.15 percent of the starvation, and 4.26 percent that also stall the back end causing 46.83 percent

What people did before, and where it broke

Build a bigger instruction cache. Doubling it from 32KB to 64KB helps, and the paper measures it as a reference point. But the instruction cache sits on a timing-critical path, so growth costs area, power and design difficulty, and the measured gain is smaller than a criticality-aware replacement policy achieves.
Learn which lines follow which, and fetch them early. Record-and-replay prefetchers keep a history of instruction block sequences and replay them ahead of demand. The entangling prefetcher refines this by timing: it records how long a miss took and links the missing line to whatever was accessed that many cycles before, so the prefetch lands just in time.
But they were built for a metric that stopped predicting performance. Their goal is fewer instruction cache misses, while a decoupled front end is designed to TOLERATE misses. Prior work showed most of the reported gains disappear on a machine with even a 24-entry fetch target queue, and much of this literature was never evaluated against such a machine.
And their budgets are large. The entangling prefetcher’s performance-oriented configuration uses a table over 200KB — six times the size of the instruction cache it is protecting. Constrained to a realistic budget, it delivers 1.5 percent.
They also fight the cache. A prior criticality-aware replacement policy protects front-end-critical lines in the second-level cache and beats doubling the instruction cache. Combined with the entangling prefetcher, the two can end up HURTING performance, because neither was designed with the other in mind.
The gap. Everyone was reducing misses, and every miss counted equally toward that goal. Nobody was asking which misses the machine could not already absorb — and once you ask, the answer turns out to be a small, structurally identifiable set rather than a statistical property to be learned.

How the harmful misses identify themselves

Deduce where the runahead fails, and let the failure supply its own trigger

Run the predictor ahead and prefetch what it predicts

The branch predictor fills a queue of upcoming fetch addresses, and each address is prefetched into the instruction cache as it enters. With the queue full, this covers a full instruction cache miss and often a second-level miss, so most misses cost nothing at all.
↓ →
Notice that a mispredict destroys the runway new

A branch mispredict flushes the entire front end including that queue. Execution resumes from the corrected address with no head start, so addresses now enter the queue barely before they are demanded. Misses in this window are exposed in full; identical misses during steady running are free.
↓ →
Mark the lines that actually stalled the machine new

Label a cache line front-end critical when it retired an instruction, missed in the instruction cache, and produced front-end stalls. Marking is decided at retirement, so wrong-path fetches never qualify. The same marking hardware already exists for a criticality-aware cache policy, so nothing new is needed to detect it.
↓ →
Narrow to the ones that hurt most new

Consider as prefetch candidates only the high-cost critical lines that also stalled the back end. Most lines never reach critical status at all, so the set to remember is small — which cuts storage sharply and filters out prefetches that would have been useless.
↓ →
Pair each candidate with the event that exposed it new

Since a stalling miss must follow a flush, the flushing instruction is a natural trigger. For control-flow disruptions that is the mispredicting branch or the instruction missing in the branch target buffer; for long misses that stall even a full queue, it is the last retired taken branch. Store the pair in a small table.
↓ →
On the next encounter, jump-start the queue new

Look the table up once per queue entry, which corresponds to one basic block. On a hit, issue a prefetch for the associated target — arriving before its address would have entered the queue at all, which is the only way to cover a miss the queue could not.

Evaluated in gem5 on a full-system Ubuntu simulation of a Golden Cove-like core, running 16 multi-threaded Java and database workloads chosen for instruction cache miss rates above 20 per thousand instructions, against a baseline extended with a faithful decoupled front end.

The idea

Ask which misses the machine cannot already absorb. The literature had a clear objective — fewer instruction cache misses — and it is the objective any reasonable person would pick. What changed underneath it is that processors acquired a mechanism specifically designed to make misses harmless, and the objective did not update. A miss during steady running is now free, because the predictor has already run far enough ahead that the line arrives before anyone wants it. Counting that miss the same as one that stalled the machine for dozens of cycles makes the metric almost uninformative, and the paper shows the consequence directly: the prior best prefetcher, given six times the instruction cache in table space, is worth 1.5 percent. The authors make the correction explicit by redefining COVERAGE for this class of design — not the fraction of all misses prefetched, but the fraction of front-end critical misses, of which they capture 67 percent. Noticing that a long-accepted objective has stopped tracking the outcome it was a proxy for is the same measure-the-true-thing lesson covered elsewhere on this site where systems accept more of the quantity everyone minimises and win on the quantity that actually matters.

A deduction, not a heuristic. The step that makes the design cheap is a piece of reasoning rather than a learned pattern. The runahead protects a miss only while the queue is full; the queue is only empty shortly after something flushed it; therefore every miss that genuinely stalled the front end occurred in the wake of a flush. This is not a correlation discovered in traces, it follows from how the mechanism works — and it yields two things at once. It tells you WHICH misses to care about, which turns out to be about 5 percent of lines. And it hands you a TRIGGER for free, because the flushing instruction is guaranteed to exist, guaranteed to be recent, and easy to identify. The measurements confirm the reasoning: 89 percent of issued prefetches are triggered by a branch mispredict. Finding that the thing causing the problem is also the signal that predicts it is the same look-again-at-the-obstacle move covered elsewhere on this site where the structural property that defeats the conventional approach turns out to mark exactly where the alternative should act.

Selectivity buys accuracy and storage at the same time. Prefetcher designs usually trade these against each other: remember more history, prefetch more aggressively, and pay in both table space and cache pollution. Restricting candidates to high-cost critical lines improves both simultaneously, because most lines never qualify, so the set to remember is small AND the prefetches issued are the ones worth issuing. The result is a table of 43.5KB against over 200KB, with 54 percent of prefetches used before eviction against 44 percent. It also makes the design self-adjusting in a way a fixed policy is not: on workloads with little criticality it issues half as many useless prefetches as the alternative, while on one with severe criticality it issues over ten times as many, because the criteria are driven by observed damage rather than a tuned aggressiveness. Filtering by what actually matters so that precision and cost improve together, rather than trading off, is the same selectivity-is-compression pattern covered elsewhere on this site where narrowing attention to the cases that carry the consequences shrinks the work instead of adding to it.

Learning one trigger, using it the next time

The paper's own walkthrough, following two visits to the same code

Blocks a through r are instructions. Block b is a branch that mispredicts; block r misses in the instruction cache.

Step 1 of 5

A mispredict empties the runway

Execution reaches block b, a branch, and the prediction turns out to be wrong. The processor discards the wrongly-fetched work and flushes the front end, including the queue of upcoming fetch addresses. Whatever head start the prefetching had is now gone.

this is the third cost of a mispredict on such a machine, on top of squashing the wrong path and refilling the pipeline
as code footprints grow, this third cost can come to dominate the other two

Why it works

The runahead only covers a miss while the queue is full, and only a flush empties the queue → every stalling miss must follow a flush → so the harmful misses are structurally identifiable rather than statistically learned.
The flushing instruction necessarily precedes the exposed miss → it is guaranteed to exist and to be recent enough to act on → giving a trigger with no search, no timing model, and no learned distance, and 89 percent of prefetches come from mispredicts.
Only about 5 percent of lines are high-cost critical → the set worth remembering is small → so the table needs 43.5KB against over 200KB for the prior design, while issuing more accurate prefetches, 54 percent used against 44.
Candidates are chosen by observed damage rather than tuned aggressiveness → the prefetcher issues few prefetches where little is at stake and many where much is → half as many useless prefetches on low-pressure workloads and over ten times as many on the most critical one.
The criticality marking already exists for a criticality-aware cache policy → one detection mechanism serves both cache and prefetcher → so the two compose instead of colliding, reaching 3.7 percent together and 72.5 percent of the idealised ceiling.

What it costs (trade-offs and scope)

The gains are single-digit percentages. 3.15 percent on average and 5.1 percent at best, rising to 3.7 percent with a criticality-aware cache. Real for a data centre at scale, but this is a refinement of an already-effective mechanism, not a transformation.
The benefit shrinks as branch prediction improves. With a 4K-entry branch target buffer the gain is 4.32 percent, at 8K entries 3.15 percent, and with a 64K-entry buffer of 945KB still above 1.0 percent. Fewer mispredicts means fewer exposed misses to rescue.
Combining with the criticality-aware cache can lose ground. Protecting instruction lines in the second-level cache takes space from data, and on three workloads measured here that raised data misses enough to make the combination slightly worse than the prefetcher alone.
Compiler layout can defeat the table. One workload built with a layout-optimising toolchain has unusually long basic blocks that fit the table structure poorly, and was the only benchmark not to improve as the table grew.
Two plausible refinements did not pay. Tracking instruction address translation misses as trigger events produced no gain, and adding the last three branches as path context was not worth its complexity — both reported rather than quietly dropped.

The evaluation

The measurements were made in gem5 with full-system simulation of a real Ubuntu kernel, running multi-threaded Java and database workloads on an out-of-order core modelled after Golden Cove, with wrong-path execution modelled. The baseline is itself a contribution: the authors extended the simulator with a faithful decoupled front end, added an indirect branch predictor, enlarged the branch target buffer to 8K entries and fixed several bugs, producing a baseline 27.1 percent faster than the stock model. Sixteen workloads with instruction cache miss rates above 20 per thousand instructions were used. To keep full-system runs repeatable they drove the operating system scheduler by retired instruction count rather than cycles, holding run-to-run divergence below 0.2 percent.

Reducing front-end stalls on a processor that already prefetches

Property	Double the instruction cache	Entangling prefetcher	Prefetch only critical misses
What it targets
Storage added
Prefetches used before eviction
Critical stalls removed
With a criticality-aware cache

Average instructions-per-cycle gain over the decoupled-front-end baseline was 3.15 percent at 43.5KB, up to 5.1 percent on Cassandra, against 1.5 percent for the entangling prefetcher at a comparable budget — and it matches that prefetcher's unconstrained 200KB configuration using five times less storage. Total front-end stalls fell 16 percent against 8 percent. Cost was 0.62 percent more core energy and 0.96 percent more area. Spending the same storage on a larger branch target buffer is always the worse trade: matching this design at a 32K-entry buffer would need 111KB of extra buffer against 44KB here.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Keep the scale in view: these are single-digit percentages — 3.15 percent on average, 5.1 percent at best, 3.7 percent with a criticality-aware cache — which matter at data centre scale but represent a refinement of a mechanism that already works well, not a transformation. The benefit also shrinks as the rest of the front end improves, since fewer mispredicts mean fewer exposed misses to rescue: 4.32 percent with a 4K-entry branch target buffer, 3.15 at 8K, and above 1.0 percent even with a 945KB buffer. The composition with a criticality-aware cache is not free either — protecting instruction lines in the second-level cache takes room from data, and on three workloads that raised data misses enough that the combination trailed the prefetcher alone. Compiler decisions interact too: the one workload built with a layout-optimising toolchain has unusually long basic blocks that fit the table structure poorly, and alone among the sixteen did not improve as the table grew. Two refinements the authors tried and report as failures deserve credit — using address-translation misses as trigger events gave no gain, and adding three branches of path context was not worth its complexity. The strongest methodological point is the baseline itself: because prior prefetchers were largely evaluated against machines lacking a decoupled front end, the authors rebuilt one faithfully, making their own comparison harder to win and their conclusion about the older metric much harder to dismiss.

Background

When the metric stops tracking the outcome, and the disruption becomes the signal

This paper sits in the site’s memory systems and microarchitecture clusters and rhymes with several ideas covered elsewhere on this site. Its central argument is the sharpest instance yet of a pattern this site keeps meeting: an objective everyone accepted — instruction cache miss count — stopped predicting the outcome once processors gained a mechanism that tolerates misses, exactly as network traffic stopped predicting time on the graph-mining page, memory traffic stopped predicting throughput on the recommendation-inference page, and wave count stopped predicting runtime on the dynamic-shape compilation page. Here the authors go further than the others by redefining the metric explicitly, measuring coverage of stall-causing misses rather than of all misses. The extreme concentration they exploit, where 5 percent of lines cause 56 percent of the damage, is the same power-law shape the quantum optimisation, recommendation and graph-mining pages each build on. Its trigger mechanism is a clean instance of the obstacle marking the solution — the mispredict that destroys the prefetch runway is precisely the signal announcing that a rescue is needed — the same reframe the operating-system bug-finding page makes when functions with no visible caller become the natural place to start. And its selectivity, where attending only to the damaging cases shrinks storage and improves accuracy together rather than trading one for the other, is the same narrowing-is-compression result that page reaches when merging provably identical variables makes its analysis cheaper rather than dearer.

If you remember only three things

1. Server software now misses in the instruction cache about 86 times per thousand instructions, and one measured workload loses 53.6 percent of its issue slots to the front end against 18.9 percent retiring. But modern processors run the branch predictor far ahead of execution and prefetch every address entering the resulting queue, which hides most of those misses completely. So the metric the prefetching literature optimised — miss count — stopped predicting performance, and the prior best design, given a table six times the size of the instruction cache, is worth 1.5 percent.
2. The misses that still hurt can be DEDUCED rather than learned. The runahead protects a miss only while the queue is full, and only a flush empties the queue, so every miss that genuinely stalled the machine occurred just after a branch mispredict or similar disruption. That identifies them — roughly 10 percent of lines cause 62 percent of stall cycles, and 5 percent cause 56 — and simultaneously supplies a trigger, since the flushing instruction is guaranteed to exist and to arrive early enough. In practice 89 percent of prefetches are triggered by a mispredict.
3. Restricting attention to those lines improves storage and accuracy together instead of trading them: 43.5KB against over 200KB, with 54 percent of prefetches used before eviction against 44, removing 42 percent of critical stalls against 19. The result is 3.15 percent more instructions per cycle on average and 3.7 percent alongside a criticality-aware cache that shares the same detection hardware, for 0.62 percent more energy and 0.96 percent more area. Notably the authors rebuilt the baseline to include the decoupled front end that prior work often omitted, making their own result harder to obtain and their argument about the old metric harder to dispute.

Check yourself

Check your understanding

1. Instruction prefetchers that measurably reduce cache misses deliver little benefit on modern processors. Predict why reducing misses stopped translating into speed.
2. Rather than learning from traces which misses will be costly, this design deduces it. Predict the reasoning that identifies harmful misses and supplies a trigger at once.
3. On one workload this prefetcher issues over ten times as many prefetches as the alternative, and on others it issues half as many useless ones. Predict why the same design does both.
4. A branch target buffer holds branch destinations, and a bigger one means fewer mispredicts and so fewer exposed misses. Predict why spending 44KB on this prefetcher beats spending it on the buffer.

Sources

PDIP: Priority Directed Instruction Prefetching (author PDF, Princeton Liberty Research Group) — ASPLOS 2024; the full 16-page paper, read in full for this explainer. One of six best paper awards at ASPLOS 2024.
ACM Digital Library (DOI 10.1145/3620665.3640394) — published version.
Artifact (Zenodo) — the authors’ released evaluation artifact.