Instruction-Aware Cooperative TLB and Cache Replacement Policies

Big server programs are so large that the code itself no longer fits in the fast on-chip structures, so the processor constantly stalls waiting to fetch instructions and to translate their addresses — and an instruction-address-translation miss is especially damaging because it freezes the whole front-end of the pipeline; this work from Barcelona and Texas A&M makes the cache and the translation buffer aware of which entries hold instructions and cooperate to keep them, instead of managing the two independently, to relieve those front-end stalls.

The argument in one glance

Problem

Server code is too big for the structures that feed the pipeline

Modern server and data center applications have enormous instruction footprints — deep software stacks and huge binaries — so the hot code no longer fits in the small on-chip structures that supply the pipeline. The processor keeps missing in the instruction cache and in the instruction translation-lookaside buffer (TLB) that caches address translations for code. An instruction-TLB miss is especially damaging: until the translation resolves, no instruction can be fetched, so the whole front-end stalls and the core sits idle.
What people did

Manage the caches and the TLB with their own replacement policies

Each on-chip structure — the instruction cache, the data cache, the TLB — decides what to keep and what to evict using its own replacement policy, such as least-recently-used or a re-reference prediction scheme. These policies are well studied and each works to keep entries that seem likely to be reused.
Why it fell short

The policies ignore instructions and never cooperate

Those replacement policies treat every entry alike, without recognizing that an instruction entry — a code block or a code-page translation — is far costlier to lose than a data entry, because its miss stalls the front-end. And the TLB and the caches each run their policy in isolation, with no shared information, so they can even evict the very instruction entries the other is trying to keep. As a result, the hot instruction footprint is not protected, and front-end stalls dominate performance.
This paper's idea

Make the policies instruction-aware and cooperative

This work makes the replacement policies aware of instruction accesses, biasing them to retain the instruction cache blocks and code-page translations whose loss would be most costly, and makes the TLB and cache replacement policies cooperate — sharing information so their decisions reinforce each other rather than conflict. Together they keep the hot code resident across both the caches and the translation buffer, relieving the front-end stalls that dominate server and data center workloads with large instruction footprints.

Why this problem is worth solving

The reason instruction-side misses deserve special treatment is that they hurt in a way data misses do not.

A processor runs programs using virtual addresses, and every memory access — including fetching an instruction — must be translated from its virtual address to a physical one. The translation-lookaside buffer (TLB) is a small, fast cache of recent translations that lets this happen without walking the page tables in memory, which takes hundreds of cycles. There is a separate instruction TLB for code addresses. Now consider what happens on an instruction-TLB miss: the processor is trying to fetch the next instruction, but it cannot even find where that instruction physically lives until the translation is resolved by a page-table walk. Instruction fetch is the very front of the pipeline — it feeds everything downstream — so while that translation is pending, the front-end stalls and no new work enters the machine. The entire back-end, however capable, sits idle with nothing to execute. This is what makes an instruction-TLB miss so much more damaging than a data miss: a modern out-of-order core can keep working around a data miss by executing other independent instructions, but it cannot execute instructions it has not been able to fetch. In server and data center workloads, whose huge instruction footprints overflow the instruction TLB and cache, these front-end stalls are a dominant, well-documented source of lost performance — which is exactly why they are worth attacking.

The lever the paper reaches for is how these structures decide what to keep.

The instruction cache and the TLB are finite and set-associative: when a set is full and a new entry arrives, one existing entry must be evicted to make room. The replacement policy is the rule that chooses the victim — keep the entries most likely to be reused, evict the ones least likely. Decades of work have produced sophisticated policies, from least-recently-used to re-reference prediction to learned approaches, and a good one dramatically cuts misses by holding onto the hot working set. But two things go wrong for server code. First, standard policies are oblivious to what kind of entry they hold: they weigh a code-page translation the same as a data-page translation, even though losing the code translation triggers a front-end stall while losing the data one may be hidden by out-of-order execution. So they will happily evict a costly instruction entry to keep a cheap data one. Second, the caches and the TLB each run their replacement policy in isolation, sharing no information, so they can pull in opposite directions — the cache keeping a page’s code blocks while the TLB drops that page’s translation, or vice versa, leaving the hot code effectively unprotected. Fixing both — making the policies aware of instructions and making them cooperate — is the opportunity.

What people did before, and where it broke

Instruction-oblivious replacement (LRU, re-reference prediction). Manage each cache and TLB with a general-purpose policy that keeps entries likely to be reused. Where it broke. These policies treat instruction and data entries identically, so they evict costly code blocks and code-page translations to retain cheaper data entries, ignoring that instruction misses stall the whole front-end.
Independent per-structure management. Let the instruction cache, data cache, and TLB each run its own policy in isolation. Where it broke. With no shared information, the structures can undermine each other — one evicting the very code entries another is trying to hold — so the hot instruction footprint is not kept resident anywhere consistently.
Bigger caches and TLBs, or huge pages. Throw more capacity or larger page mappings at the front-end problem. Where it broke. Server instruction footprints are large and growing, so added capacity helps only so far, and these approaches do not change the fundamental blindness of the replacement decisions to instruction cost.
The gap. No approach both prioritized the instruction entries whose loss is most damaging and coordinated the TLB and caches so they reinforce each other. Making the replacement policies instruction-aware and cooperative is what this work contributes.

How the approach works

From oblivious, independent policies to instruction-aware cooperation

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

The idea

Spend scarce capacity on the entries whose loss is costliest. Not every miss is equal: losing an instruction entry stalls the front-end and starves the core, while losing a data entry can be worked around, so the policies preferentially keep the instruction blocks and code-page translations. Directing a limited, expensive resource toward exactly the cases where a miss does the most damage, rather than treating every case the same, is the same discipline the page-table replication work covered elsewhere on this site follows, applying its costly mechanism only where the access pattern shows it will pay off instead of spending it uniformly everywhere.

Make two independent controllers cooperate toward a shared goal. The TLB and the caches manage the same hot code but had been deciding what to keep in isolation, sometimes at cross purposes; sharing information lets each reinforce the other so the working set stays resident in both. Turning independent controllers that could work against each other into cooperating ones that pursue a common objective through shared information is exactly the move the multi-tenant storage work covered elsewhere on this site makes, coordinating per-tenant agents with a shared signal so they reinforce overall efficiency instead of each optimizing in isolation.

Aim the memory hierarchy at the translation bottleneck. The dominant cost is front-end stalls from instruction fetch and address translation, so the approach targets the instruction TLB and cache directly rather than a part that is no longer the constraint. Co-designing the memory system to attack the address-translation bottleneck that generic caching leaves in place is the same strategy the direct-memory-translation work covered elsewhere on this site pursues, building its mechanism squarely around the translation cost that ordinary caches and prefetchers could not eliminate.

Following an instruction fetch through the approach

Avoiding a front-end stall on hot server code

Tracing one instruction fetch shows the instruction-aware, cooperative policy at work.

Step 1 of 5

A large-footprint server workload runs hot code

The application executes a big body of hot code that overflows both the instruction cache and the instruction TLB, so the front-end keeps missing as it fetches instructions across many code pages.

The instruction footprint far exceeds the small on-chip structures.

Why it works

Instruction-TLB misses are the costliest. An instruction-TLB miss blocks instruction fetch → so it stalls the whole front-end and starves the back-end, unlike a data miss the core can work around → so keeping instruction translations resident avoids the most damaging stalls.
Not all entries are worth the same. Losing an instruction entry hurts far more than losing a data entry → so a policy that knows which entries hold instructions can retain the ones whose miss is costliest → so limited cache and TLB capacity is spent where it matters.
The TLB and cache serve the same hot code. Both structures are managing the same working set of instructions → so letting their policies share information keeps them aligned on that code → so a fetch that hits in one is more likely to hit in the other.
Cooperation removes cross-purposes. Independent policies can evict the very instruction entries the other is trying to keep → but coordination eliminates that conflict → so the two structures reinforce rather than undermine each other.
It attacks the real bottleneck. Server workloads are dominated by front-end stalls from huge instruction footprints → so relieving those stalls targets the actual performance limiter → so it helps where general-purpose, instruction-oblivious policies could not.

What it costs (trade-offs and scope)

It helps most when the front-end is the bottleneck. The gains come from relieving instruction-fetch and translation stalls; workloads that are not front-end-bound, or whose instruction footprint already fits on-chip, have little to gain.
Favoring instructions can cost data. Biasing replacement toward instruction entries retains them at the expense of data entries, so the policy must balance the two carefully or it could hurt data-intensive phases.
Cooperation adds coordination machinery. Sharing information between the TLB and cache replacement policies is extra hardware and logic that must be cheap enough not to erase the benefit it provides.
It changes on-chip replacement policies. The approach modifies how the caches and TLBs choose victims, which is intrusive microarchitecture that must be integrated into the existing memory hierarchy.
The benefit depends on the workloads and the hierarchy. How much it helps varies with the instruction footprint, the cache and TLB sizes, and the specific applications, so different systems would need their own evaluation.
It targets instruction supply, not the whole pipeline. Other limits — data-side misses, branch mispredictions, execution bottlenecks — are separate concerns that still apply.

The evaluation

Three ways to manage on-chip structures for large-footprint code

Property	Oblivious independent policies	Instruction-aware only
Distinguishes instruction entries		Yes
TLB and cache coordinate		No, independent
What stays resident	Whatever a generic policy keeps	Hot instruction entries
Front-end stalls	Frequent	Fewer

Three ways to manage the on-chip caches and TLB for large-instruction-footprint code. General-purpose replacement policies treat instruction and data entries alike and manage each structure independently, leaving the hot code unprotected and the front-end stalling. Making the policies instruction-aware retains the costly instruction entries, and making the TLB and caches cooperate keeps the hot code resident across both at once — together relieving the front-end stalls that dominate server and data center performance. (This explainer is drawn from the paper's abstract and standard background on TLBs and cache replacement; the full text, including the specific policy designs and their measured performance gains, was not available.)Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This work targets a real and well-documented problem: server and data center applications have huge instruction footprints that overflow the on-chip structures feeding the pipeline, and instruction-side misses — especially instruction-TLB misses, which stall the whole front-end — are a dominant source of lost performance that general-purpose, instruction-oblivious replacement policies do not address. Its two ideas are sensible and complementary: make the cache and TLB replacement policies aware that instruction entries are costlier to lose, so they are retained, and make the TLB and caches cooperate rather than manage the same hot code in isolation, so they reinforce each other. Read it with its scope. The benefit is concentrated on front-end-bound workloads with large instruction footprints; code that fits on-chip has little to gain. Favoring instructions trades against data, cooperation adds coordination hardware, and the approach modifies intrusive on-chip replacement policies that must integrate with the existing hierarchy. Crucially, this page is written from the paper’s brief abstract and standard background on virtual memory and cache replacement, because the full text was behind a closed paywall with no accessible copy; the specific instruction-aware and cooperative policy designs, the exact mechanisms, and the quantitative performance gains are described in the paper and are not reproduced here. The durable lesson is that a replacement policy that ignores the cost of what it evicts, and structures that manage a shared working set in isolation, leave performance on the table — and that making eviction cost-aware and cooperative recovers it.

Background

Why feeding the pipeline, not the pipeline itself, is the modern bottleneck

It helps to place this work against a shift in where performance is actually lost. For much of computing history the intuition was that a faster core meant more arithmetic throughput, but on the server workloads that dominate data centers the back-end is rarely the constraint — the machine is starved for instructions, stalling at the front-end because the code and its address translations do not fit in the small, fast structures that supply the pipeline. The bottleneck has moved from doing the work to being able to fetch the work to do. The retrospective on deep-learning accelerators covered elsewhere on this site makes the same argument in a different domain, that the ceiling is no longer raw compute but the memory and data movement needed to keep the fast units fed, so the useful engineering is increasingly in the supply path rather than the execution units. The broad lesson is that as programs and their instruction footprints grow, keeping the pipeline supplied — with instructions, with translations, with the right entries resident in the right small structures — becomes the decisive problem, and the wins come from managing those scarce on-chip resources with awareness of what each miss actually costs.

If you remember only three things

1. Modern server and data center applications have enormous instruction footprints, so the hot code overflows the small on-chip structures that feed the pipeline, causing frequent instruction cache and instruction-TLB misses. An instruction-TLB miss is especially harmful: until the code address is translated, no instruction can be fetched, so the entire front-end stalls and the whole core sits idle — unlike a data miss, which an out-of-order core can often hide. These front-end stalls are a dominant performance limiter for server workloads, yet the caches and the TLB each choose what to evict with a general-purpose replacement policy that neither distinguishes costly instruction entries from data entries nor coordinates with the other structures.
2. This work makes the replacement policies instruction-aware — biasing them to retain the instruction cache blocks and code-page translations whose loss would trigger a front-end stall — and cooperative — letting the TLB and cache replacement policies share information so their decisions reinforce rather than conflict, keeping the hot instruction footprint resident across both the caches and the translation buffer at the same time. Together, prioritizing the entries whose miss is costliest and aligning the two structures on the same hot code relieves the instruction-fetch and address-translation stalls that oblivious, independent policies leave in place.
3. Its scope: the benefit is concentrated on front-end-bound workloads with large instruction footprints (code that fits on-chip gains little); favoring instructions trades against data; the cooperation adds coordination hardware; and it modifies intrusive on-chip replacement policies that must integrate with the existing memory hierarchy, targeting instruction supply rather than the whole pipeline. This explainer is written from the paper's brief abstract and standard background on TLBs and cache replacement, because the full text was unavailable — the specific policy designs, mechanisms, and measured performance gains are in the paper and are not reproduced here.

Check yourself

Check your understanding

1. Why is an instruction-TLB miss especially harmful to performance?
2. What two shortcomings of standard replacement policies does this work address?
3. How do the "instruction-aware" and "cooperative" ideas work together?
4. Which statement best reflects the scope and limitations of this work?

Sources

The paper is “Instruction-Aware Cooperative TLB and Cache Replacement Policies” by Dimitrios Chasapis, Georgios Vavouliotis, Daniel A. Jimenez, and Marc Casas, published at ASPLOS 2025, DOI 10.1145/3669940.3707247. The authors are at the Barcelona Supercomputing Center and Texas A&M University.

This explainer is marked as a draft because the full text was not accessible: the paper is closed access on the ACM Digital Library, that page was protected by an anti-bot challenge that blocked automated retrieval, and no arXiv preprint, author-hosted copy, or open repository version could be found; only a brief abstract was available. The account above is written from that abstract together with standard, well-established background on computer architecture — virtual memory and address translation, the translation-lookaside buffer and why an instruction-TLB miss stalls the front-end of the pipeline, cache and TLB set-associativity and replacement policies (least-recently-used, re-reference prediction, and cost-aware approaches), and the well-documented front-end bottleneck of large-instruction-footprint server and data center workloads. The specific claims attributed to the paper — that modern server and data center applications have large instruction footprints causing frequent instruction cache and TLB misses, that instruction-TLB misses are particularly problematic because they cause pipeline stalls that significantly harm performance, and that the work proposes instruction-aware and cooperative TLB and cache replacement policies — come from the abstract and title. The description of how the instruction-aware and cooperative policies work (prioritizing costly instruction entries and coordinating the TLB and caches so they keep the same hot code resident) is a faithful reading of the title and abstract, but the specific policy designs, the exact coordination mechanisms, and the quantitative performance gains are detailed in the full paper and are not reproduced or invented here; they should be confirmed against the paper itself.