Hierarchical Prefetching: A Software-Hardware Instruction Prefetcher for Server Applications

Server programs are so large that the processor's front-end keeps stalling because the next instructions are not in the fast cache, and even smart prefetchers that record and replay past instruction sequences go wrong whenever the real control flow diverges from the recorded one; this work from Tsinghua and Edinburgh proposes Hierarchical Prefetching, which groups server code offline into big coarse blocks called Bundles — tens to hundreds of kilobytes each — and prefetches a whole bundle at once with lightweight hardware, staying accurate despite fine-grained control-flow noise and using under 2 kilobytes of on-chip storage, for a 6.6 percent average speedup over the state-of-the-art front-end prefetcher.

The argument in one glance

Problem

Server code is too big, so the front-end starves the core

A processor's front-end fetches the instructions the core is about to run. Large server applications have a huge instruction footprint that overflows the fast instruction cache and the branch predictor's tables, so the core repeatedly stalls waiting for the next instructions to arrive — a major bottleneck even on high-performance chips.
What people did

Prefetch ahead, and record-and-replay hot sequences

High-performance cores use fetch-directed instruction prefetching, running the branch predictor ahead to fetch down the predicted path. Server-specific prefetchers go further, recording the repetitive instruction streams servers run and replaying them to bring code in early.
Why it fell short

Replaying an exact stream breaks on control-flow divergence

Record-and-replay assumes the future will match a recorded, predicted instruction sequence. But real control flow often diverges — a different branch, a different path — and then the replay fetches the wrong instructions or arrives too late. The result is lost coverage (misses it fails to prevent) and lost timeliness (prefetches that come too late to help).
This paper's idea

Prefetch whole coarse functionality blocks (Bundles)

Hierarchical Prefetching identifies common coarse-grained functionality blocks in server code, called Bundles, each tens to hundreds of kilobytes, and prefetches a whole bundle at once. Because a bundle is large, small control-flow differences inside it do not change which bundle is needed, so the prefetch stays accurate. Simple software forms the bundles offline; lightweight hardware does the record-and-replay, keeping most metadata in main memory and under 2 kilobytes on-chip. The result is a 6.6 percent average gain over fetch-directed prefetching.

Why this problem is worth solving

The instruction supply, not arithmetic, is often what limits a server core.

A processor is split into a front-end, which fetches and decodes the instructions to run, and a back-end, which executes them. For the back-end to stay busy, the front-end must keep feeding it a steady stream of instructions. That stream comes from the instruction cache, a small fast memory holding recently-used code, steered by the branch predictor, which guesses where control will go next. This works well when a program’s hot code is small enough to sit in the cache and the predictor’s tables. Large server applications break that assumption. A database, a web server, or a key-value store executes an enormous amount of distinct code — deep software stacks, many libraries, large functions — so its instruction footprint vastly exceeds the fast on-chip structures. The needed instructions are frequently not in the cache, and each such instruction-cache miss stalls the front-end while the code is fetched from a slower level of memory. Because the back-end then has nothing to run, these front-end stalls directly waste the core, and on server workloads they are a well-documented, first-order performance problem — one that persists even on the highest-performance cores. Reducing them is worth real effort, because the instruction supply is the ceiling on how fast such applications can run.

Existing prefetchers help, but the strongest ones are fragile.

A prefetcher tries to bring instructions into the cache before the core needs them, so the miss is hidden. The baseline in high-performance cores is fetch-directed instruction prefetching, where the branch predictor is run ahead of execution to discover the upcoming instruction addresses and fetch them early. This helps, but on huge server footprints it still leaves many stalls, so researchers built prefetchers specifically for servers. These exploit a real property of server code: it is highly repetitive, running the same sequences of instructions over and over across requests. Such prefetchers record the stream of instruction addresses seen during one execution and, on recognizing the same starting point later, replay that recorded stream to fetch the code ahead of time. The weakness is that the recorded stream is a single predicted path, and real control flow does not always follow it. When the actual execution diverges — a branch resolves the other way, an unusual input takes a different path — the replay is fetching instructions from the wrong path. Two things go wrong at once. Coverage falls, because the misses on the real path were never prefetched. And timeliness falls, because the prefetcher, following the wrong trail, brings the right code in too late to matter. The paper’s goal is a prefetcher that keeps working when control flow diverges, instead of breaking on it.

What people did before, and where it broke

Fetch-directed instruction prefetching (FDIP). Run the branch predictor ahead of the fetch stage to discover and prefetch upcoming instruction addresses. Where it broke. It is the strong baseline, but on the very large instruction footprints of server applications it still leaves substantial front-end stalls, because the predictor and its reach cannot cover such a working set alone.
Record-and-replay server prefetchers. Record the repetitive instruction streams a server runs and replay them to fetch code early. Where it broke. They replay a single recorded, predicted path, so when the actual control flow diverges from it the replay fetches wrong-path code, losing both coverage (real misses left unprevented) and timeliness (right code fetched too late).
Larger on-chip prefetch metadata. Store more recorded history on-chip to cover more of the code. Where it broke. Server footprints are so large that comprehensive on-chip metadata is expensive in silicon area, a poor trade for the front-end.
The gap. No prefetcher combined robustness to fine-grained control-flow divergence with a small on-chip footprint on large server code. Achieving both by prefetching whole coarse functionality blocks, formed in software and replayed by lightweight hardware, is what Hierarchical Prefetching proposes.

How Hierarchical Prefetching works

From fragile exact-stream replay to robust whole-bundle prefetch

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Prefetch a coarse whole, not a fragile exact sequence. The failure of prior server prefetchers is that they commit to one precise predicted instruction stream, which any control-flow divergence invalidates. Hierarchical Prefetching steps up a level of granularity: it prefetches a whole functionality block — a bundle of tens to hundreds of kilobytes — so that the many fine-grained branch decisions inside that region no longer matter to the prefetch, because all of the region’s code is brought in regardless of which internal path executes. Choosing a coarse, robust unit over a precise but brittle one, and accepting that it may bring in a little more than strictly needed in exchange for staying correct under noise, is the same trade the copy-on-write correctness work covered elsewhere on this site makes, using a single conservative flag that occasionally errs toward extra work rather than a precise tracking scheme that is fragile and error-prone.

Split the work between offline software and lightweight hardware. Deciding which code forms a coherent bundle is analysis that does not need to happen at nanosecond speed, so Hierarchical Prefetching does it in software, ahead of time, examining the server code to form the bundles. The runtime job — noticing which bundle has been entered and issuing the prefetches — is simple and repetitive, so it is handed to small, cheap hardware. Putting the heavier analysis in an offline software step and keeping the on-the-fly hardware minimal is the same division of labor the manycore work-stealing work covered elsewhere on this site relies on, pairing software that decides how work should be arranged with a small hardware assist that handles the fast, repetitive runtime action.

Keep almost nothing on-chip, and the rest in main memory. On-chip storage is scarce and expensive, and a server’s code is far too large to describe fully in silicon. Because bundles are large and coarse, only a tiny index of them needs to live on-chip — under two kilobytes — while the bulk of the bundle metadata sits in plentiful main memory, fetched as needed. Holding a small hot summary on-chip in front of a large backing store kept in cheaper memory is the same layering the voxel-caching work covered elsewhere on this site uses, keeping a compact cache close to the processor in front of the big spatial structure that lives in main memory.

Following a bundle through the prefetcher

Prefetching a whole functionality block

A high-level trace of the approach; internal mechanism details are beyond the abstract this page is based on.

Step 1 of 5

Software finds a bundle

Offline, the software analysis scans the server program and identifies a common coarse-grained functionality block — a bundle of tens to hundreds of kilobytes of code that tends to be executed together as a unit.

Bundles are far larger than a typical prefetch target of a few cache lines.

Why it works

Server code overflows the front-end. Because server applications execute an enormous amount of distinct code that far exceeds the fast on-chip structures → the needed instructions are frequently not cached and the front-end stalls → so instruction supply, not compute, becomes the ceiling on performance.
Fetch-directed prefetching alone is not enough. Because fetch-directed prefetching follows only the branch predictor’s reach down the predicted path → on such huge footprints it still leaves many front-end stalls → so a dedicated server prefetcher is layered on top.
Exact-stream replay is fragile. Because record-and-replay commits to one precise recorded instruction sequence → any divergence between actual and predicted control flow throws the replay onto wrong-path code → so it loses coverage and arrives too late to help.
Coarse bundles absorb the divergence. Because a bundle is a large functionality block brought in whole → the many fine-grained branch decisions inside it do not change which bundle is needed → so the prefetch stays accurate exactly where exact-stream replay would fail.
Most metadata lives in cheap memory. Because bundles are large and their descriptions are kept in main memory → only a tiny index needs to sit on-chip, under two kilobytes → so the technique adds negligible silicon area while still covering a large working set.

What it costs (trade-offs and scope)

It may bring in more code than strictly used. Prefetching a whole bundle of tens to hundreds of kilobytes is coarse by design, so some of the fetched code on any given execution will not be needed; the bet is that the robustness this buys outweighs the extra bandwidth.
It relies on software analysis and bundle stability. Forming good bundles is an offline software step, so the approach depends on the server code having stable, recurring coarse structure to capture; code that lacks such structure offers less to bundle.
It targets server workloads specifically. The design exploits the large-footprint, repetitive nature of server applications. Programs with small instruction footprints, where the front-end is not a bottleneck, would gain little.
It is a front-end technique, not a whole-core redesign. The 6.6 percent average gain over fetch-directed prefetching is a front-end improvement layered on an already strong baseline; it addresses instruction supply, not back-end execution limits.
A small hardware and metadata cost remains. Even at under two kilobytes on-chip, the approach adds hardware for record-and-replay and consumes some memory bandwidth to fetch bundle metadata and code, a modest but real cost.
This page is written from the abstract. The full text was not available when this explainer was written, so the internal mechanism (how bundles are formed and triggered, and the exact evaluation) is summarized at the level the abstract states, without invented specifics.

The evaluation

Three ways to supply instructions to a server core

Property	Fetch-directed prefetching	Record-and-replay prefetchers
Prefetch granularity
Robust to control-flow divergence	Limited
On-chip storage	Predictor and fetch queue	On-chip history tables
Coverage and timeliness on huge code	Leaves stalls	Lost on divergence
Performance versus fetch-directed prefetching	Baseline	Not the baseline here

Three ways to keep a server core's front-end fed, as described in the paper's abstract. Fetch-directed prefetching runs the branch predictor ahead but still stalls on the very large instruction footprints of server code. Record-and-replay prefetchers replay a recorded instruction stream and lose coverage and timeliness when the real control flow diverges from the recorded one. Hierarchical Prefetching instead identifies coarse functionality blocks called Bundles, each tens to hundreds of kilobytes, and prefetches a whole bundle at once, combining offline software bundle formation with lightweight record-and-replay hardware that keeps under 2 kilobytes on-chip and the rest of its metadata in main memory. Across 11 popular server workloads, the abstract reports improved miss coverage and timeliness over prior techniques and a 6.6 percent average performance gain over fetch-directed prefetching. These are the figures stated in the abstract; the full paper was not available for this explainer.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is written from the paper’s abstract, because the full text was not available when it was prepared, so it stays at the level the abstract supports and adds only standard, well-known background about the processor front-end. What is clear and worth taking away is the shape of the idea. Large server applications stall the front-end because their instruction footprint overwhelms the fast on-chip structures, and the strongest prior prefetchers, which record and replay exact instruction streams, break whenever the real control flow diverges from the recorded prediction, losing coverage and timeliness. Hierarchical Prefetching’s response is to raise the granularity: it groups code into large coarse Bundles of tens to hundreds of kilobytes and prefetches a whole bundle at once, so the many fine-grained branch decisions inside a bundle no longer disturb the prefetch. It splits the work between an offline software analysis that forms the bundles and lightweight hardware that does the record-and-replay, and it keeps under two kilobytes on-chip by holding most bundle metadata in main memory. The abstract reports a 6.6 percent average gain over fetch-directed prefetching across eleven server workloads. Treat the internal details — how bundles are formed and triggered, and the full evaluation — as beyond what this summary can responsibly claim. The durable idea is that when precise prediction is unreliable, a coarser, more robust unit of prefetching can win.

Background

Why coarse and robust can beat fine and precise

It helps to place Hierarchical Prefetching in a wider setting, that of feeding a fast core with instructions on code too large to fit near it. The instruction-front-end optimization work covered elsewhere on this site tackles a neighboring corner of the same problem, arranging the instruction translation and cache structures so the costly entries are kept and cooperate rather than thrash. What Hierarchical Prefetching adds is a lesson about granularity: when the thing you are trying to predict — the exact instruction path — is inherently noisy, betting everything on a precise prediction is fragile, and a coarser prediction that is right about the neighborhood even when it is wrong about the details can deliver more in practice. This is a recurring pattern across systems. A precise scheme that is often slightly wrong can lose to a coarse scheme that is usually roughly right, because the coarse scheme degrades gracefully under the noise that wrecks the precise one. The broad point is that matching the granularity of a mechanism to how predictable the underlying behavior actually is, rather than always reaching for the finest possible resolution, is a design choice worth making deliberately — and on the deeply unpredictable control flow of large server code, coarse and robust is the bet this work makes.

If you remember only three things

1. On large server applications the processor front-end is a major bottleneck: the instruction footprint is so big it overflows the fast instruction cache and branch predictor, so the core stalls waiting for code even on high-performance chips with fetch-directed instruction prefetching. Server prefetchers exploit the repetitiveness of server code by recording an instruction stream and replaying it, but this is fragile — when actual control flow diverges from the recorded, predicted path, the replay fetches wrong-path code, losing coverage (misses left unprevented) and timeliness (code fetched too late).
2. Hierarchical Prefetching prefetches at a coarser granularity to tolerate that divergence. A simple offline software analysis groups server code into common coarse-grained functionality blocks called Bundles, each tens to hundreds of kilobytes, far larger than a typical prefetch target. Lightweight hardware then records which bundle execution enters and replays by prefetching the whole bundle as a unit, so the many fine-grained branch decisions inside a bundle no longer disturb the prefetch. Because bundles are large and coarse, most metadata is kept in main memory and under 2 kilobytes stays on-chip, so the hardware cost is small.
3. Across 11 popular server workloads, the abstract reports that Hierarchical Prefetching improves miss coverage and timeliness over prior techniques and achieves a 6.6 percent average performance gain over fetch-directed prefetching. The trade-offs: a coarse bundle may bring in more code than is used on a given execution, the approach depends on stable recurring code structure to bundle and on offline software analysis, and it targets large-footprint server workloads specifically. Note: this explainer is written from the paper's abstract, as the full text was not available, so internal mechanism and evaluation details are summarized only at the level the abstract states.

Check yourself

Check your understanding

1. Why is the front-end a bottleneck specifically on large server applications?
2. Why do record-and-replay instruction prefetchers lose coverage and timeliness?
3. What is a "Bundle," and why does prefetching whole bundles help?
4. How does Hierarchical Prefetching keep its on-chip hardware cost small (under 2 kilobytes)?

Sources

The paper is “Hierarchical Prefetching: A Software-Hardware Instruction Prefetcher for Server Applications” by Tingji Zhang, Boris Grot, Wenjian He, Yashuai Lv, Peng Qu, Fang Su, Wenxin Wang, Guowei Zhang, Xuefeng Zhang, and Youhui Zhang, published at ASPLOS 2025, DOI 10.1145/3676641.3716260. The authors are affiliated with Tsinghua University and the University of Edinburgh, among others.

This explainer is written from the paper’s abstract, because the full text was not available at the time of writing: the publisher’s version and the University of Edinburgh open-access copy were both behind automated-access protection, and no preprint was available. The problem statement (the front-end bottleneck of large server applications, fetch-directed instruction prefetching as the baseline, and the record-and-replay approach with its loss of coverage and timeliness when control flow diverges) and the description of the approach (identifying coarse-grained functionality blocks called Bundles of tens to hundreds of kilobytes and prefetching them whole, combining offline software bundle formation with lightweight record-and-replay hardware, and keeping under 2 kilobytes on-chip with most metadata in main memory) come directly from the abstract, as do the headline results (experiments with 11 popular server workloads, improved miss coverage and timeliness over prior techniques, and a 6.6 percent average performance gain over fetch-directed prefetching). The remaining explanation of the processor front-end, instruction caches, the branch predictor, and why server instruction footprints stress them is standard, widely-known background provided to make the abstract’s claims understandable, and is not specific to this paper. Internal mechanism details and the full evaluation are not reproduced here because they were not available.