ICARUS: Criticality and Reuse based Instruction Caching for Datacenter Applications

Datacenter programs have such enormous code that the CPU's front-end starves waiting for instructions, and the worst offenders are instruction misses in the L2 cache that leave the decoder with nothing to do; the best prior policy, EMISSARY, keeps the "critical" instruction lines (the ones whose miss stalls the pipeline) in L2, but this paper (IIT Bombay and University of Murcia — Vedant Kalbande, Alberto Ros, Biswabandan Panda) shows a line's criticality is not fixed — only about 28 percent of critical lines stay critical — so ICARUS uses the recent branch history as context to predict which lines will be critical this time, and also weighs how soon a line will be reused, sorting lines into criticality-and-reuse bins to beat the prior policy severalfold.

The argument in one glance

Problem

Datacenter code is so big the CPU starves waiting for its own instructions

A modern datacenter application is not a tight loop; it is a towering stack of user code, libraries, language runtimes, and operating-system layers, and its total instruction footprint is enormous and growing about 30 percent every year. That pressures the part of the CPU that fetches and decodes instructions — the front-end. Processors already hide most first-level instruction-cache misses with a decoupled front-end that prefetches instructions ahead of where the pipeline is executing, and L1 instruction caches have stopped growing because of it. But the deeper problem shows up at the second-level (L2) cache: when an instruction the CPU needs is missing from L2, the decoder runs out of work to feed the pipeline — decode starvation — the issue queue empties, and the whole CPU stalls. For these huge-footprint applications, L2 instruction misses are a primary front-end bottleneck, and the arithmetic units sit idle not because the work is hard but because the instructions have not arrived.
What people did

Keep the "critical" instruction lines in L2 (EMISSARY)

The state-of-the-art response is a smarter L2 replacement policy called EMISSARY. It identifies critical instruction lines — the ones whose miss actually causes decode starvation and empties the issue queue — and preferentially keeps those lines in L2 rather than evicting them, so the misses that hurt most are avoided. Ordinary lines are managed normally; critical ones are protected.
Why it fell short

Criticality is not a fixed property of a line, so protecting it statically misfires

EMISSARY treats criticality as a stable label attached to an instruction line, but that assumption does not hold. The authors observe that only about 28 percent of critical lines retain their criticality — a large fraction of critical instruction lines behave dynamically, being critical on some accesses and not others. The reason is control flow: the same instruction line can be reached along different paths, and whether its miss stalls the pipeline depends on the path. A policy that pins a line as critical once will keep protecting it when it no longer matters and fail to protect it when it suddenly does. And criticality alone ignores a second factor entirely — how soon a line will be needed again — so it keeps lines that will not be reused for a long time. As a result, EMISSARY captures only a sliver of the possible gain: a perfect instruction L2 would speed these applications up by nearly 20 percent, but EMISSARY delivers about 2 percent.
This paper's idea

Predict criticality from branch-history context, and factor in reuse

ICARUS is an L2 replacement policy built on two observations. First, because a line's criticality depends on the control flow that led to it, ICARUS couples the recent branch history with the instruction line's address to form a context, and uses that context to predict which lines will be critical this time rather than labeling lines statically. Second, criticality alone is not enough: the reuse behavior of critical lines differs from non-critical ones, and even among critical lines some are reused soon and some much later, so ICARUS considers both criticality and reuse. It sorts L2 lines into four bins by criticality and reuse and gives each bin its own replacement priority, allocating L2 space to maximize hits on the instruction fetches that actually matter. Across 12 datacenter applications, ICARUS beats the baseline by 5.6 percent on average and up to 51 percent, versus 2.2 percent for EMISSARY.

Why this problem is worth solving

The bottleneck has quietly shifted to the front-end, and it is getting worse.

A CPU’s front-end fetches instructions from memory and decodes them into operations for the execution engine. If the front-end cannot supply decoded instructions fast enough, the back-end — however powerful — sits idle. Datacenter applications strain the front-end because their code footprint is huge: they weave together user code, many libraries, language runtimes like a JVM, and multiple operating-system layers, and that footprint grows around 30 percent a year, far outpacing instruction-cache sizes, which have stalled (commercial server chips use 32 to 64 kilobytes of L1 instruction cache). Processors mitigate first-level instruction misses with a decoupled front-end: a fetch engine runs ahead of execution and prefetches instructions, hiding most L1 miss latency, which is why L1 instruction caches stopped growing. But the decoupled front-end cannot hide everything. When a needed instruction line misses in the L2 cache, the latency is large enough that the decoder runs dry — decode starvation — the issue queue empties, and the CPU stalls completely, waiting not on data or computation but on its own instructions. Because these misses stall the entire pipeline and the code footprint keeps growing, L2 instruction caching is a first-order performance problem for datacenter workloads, and the headroom is real: making L2 never miss on instructions would speed these applications up by nearly 20 percent on average.

The prior best policy leaves most of that headroom unclaimed because it misreads what criticality is.

Not every instruction-cache miss hurts equally. Some misses are hidden behind other work, but a critical instruction line is one whose miss actually causes decode starvation — it leaves the decoder with nothing to feed the pipeline and empties the issue queue, stalling the CPU. Identifying these critical lines and keeping them in cache is the right idea, and EMISSARY, the state-of-the-art L2 replacement policy, does exactly this: on a decode-starvation event it marks the offending line critical and preferentially preserves such lines in L2. The subtlety ICARUS uncovers is that criticality is not an intrinsic, stable property of a line. Only about 28 percent of lines that were critical stay critical; the rest are dynamic — critical on some fetches and harmless on others. The cause is control flow: in these layered applications, the same instruction line is reached along many different paths of jumps and calls, and whether its miss stalls the pipeline this time depends on which path led there and what else is in flight. So a policy that stamps a line “critical” once, context-free, will both waste L2 space protecting lines that are no longer critical and fail to protect lines that have just become critical. Getting criticality right therefore requires knowing the context — the recent control flow — not just the line’s address, which is the gap ICARUS sets out to close.

What people did before, and where it broke

Larger or smarter general cache replacement (TPLRU, DRRIP). Use a good generic replacement policy like tree-based pseudo-LRU or dynamic re-reference interval prediction across all L2 lines. Where it broke. Generic policies treat instruction and data lines alike and are blind to which instruction misses actually stall the front-end, so they leave most of the front-end headroom untapped — DRRIP improves these workloads by only about 1.6 percent.
Growing the L1 instruction cache. Add capacity so fewer instructions miss in the first place. Where it broke. With code footprints growing 30 percent a year, L1 instruction caches cannot keep up and have stopped growing; the decoupled front-end already hides most L1 misses, so the binding bottleneck moved to L2.
Preserving data over instructions or vice versa (DCLIP). Bias L2 to keep instruction lines resident over data lines. Where it broke. Prioritizing all instructions coarsely helps some applications but does not distinguish the critical instruction lines that stall the pipeline from the many that do not, so it uses L2 capacity indiscriminately.
Criticality-based preservation (EMISSARY). Detect lines whose miss causes decode starvation and keep those critical lines in L2. Where it broke. It treats criticality as static, but only about 28 percent of critical lines stay critical; without context it protects stale lines and misses newly critical ones, and it ignores reuse entirely, so it delivers only about 2.2 percent of the near-20-percent possible gain.
The gap. No policy predicted the dynamic, control-flow-dependent criticality of instruction lines from context, or combined criticality with how soon a line will be reused, to allocate scarce L2 capacity to the instruction fetches that actually stall the front-end.

How ICARUS works

Turning static criticality preservation into context-predicted, reuse-aware instruction caching

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

The idea

Criticality lives in the path, not the line, so predict it from branch history. The pivotal observation is that whether an instruction line’s miss stalls the pipeline is not a fixed attribute of that line but a consequence of how the program arrived there. In a deeply layered datacenter application, the same cache line of code is reached through countless different sequences of branches, calls, and returns across user code, libraries, the runtime, and the OS, and its criticality shifts with the path and with what else is in flight — which is why only about 28 percent of once-critical lines stay critical. EMISSARY, keying purely on the line, cannot see this and so mislabels the majority. ICARUS instead forms its context by coupling the recent branch history with the line address, and predicts criticality from that context, so the same line can be judged critical when reached one way and unimportant when reached another. Using the recent control-flow signature as the context that determines how to treat a memory access, rather than the address alone, is the same insight the critical-slice prefetching work covered elsewhere on this site is built on, recognizing that which accesses are on the critical path is a dynamic property of program behavior that has to be predicted from context, not read off a static label.

Criticality is necessary but not sufficient; you also have to know when a line comes back. ICARUS’s second insight is that preserving critical lines blindly still wastes L2, because criticality says nothing about reuse. Some critical lines are re-fetched almost immediately and are clearly worth keeping; others are critical but will not be touched again for a very long time, so holding them evicts more useful lines in the meantime. And the reuse profile of critical lines genuinely differs from that of non-critical ones, so a policy that ranks lines by criticality alone is optimizing one axis of a two-axis problem. ICARUS therefore measures reuse and combines it with criticality, sorting lines into four bins — critical or not, crossed with short or long reuse — and giving each bin its own replacement priority, then dividing L2 capacity among the bins to maximize hits on the fetches that stall the front-end. Recognizing that a good cache-replacement decision for instructions must weigh both which lines matter to the front-end and how soon they will be reused, rather than a single heuristic, is the same multi-signal discipline the instruction-aware cooperative cache-replacement work covered elsewhere on this site applies, treating instruction caching as its own problem with its own signals rather than reusing a generic data-cache policy.

Attack the L2 instruction miss, the stall the decoupled front-end cannot hide. ICARUS is precise about where in the machine the problem is. The decoupled front-end, with its fetch-directed prefetching, already absorbs most first-level instruction-cache misses, which is why L1 instruction caches have stopped growing and why simply enlarging them is not the answer. What it cannot hide is an L2 instruction miss, whose latency is long enough to drain the decoder and empty the issue queue. So ICARUS puts its effort exactly there — the L2 replacement policy — where a saved miss directly prevents a decode-starvation stall, and it does so in a way that complements rather than duplicates the prefetcher (remaining effective in the prefetcher’s presence). Targeting the specific level of the instruction-supply pipeline where the front-end actually stalls, rather than throwing capacity at the level that is already handled, is the same focused approach the priority-directed instruction-prefetching work covered elsewhere on this site takes, concentrating on delivering the instruction lines whose absence would otherwise starve the decoder. ICARUS complements that supply from the retention side, keeping the right lines resident so fewer of those costly L2 misses happen at all.

Following an instruction fetch through ICARUS

Deciding what to keep in L2 when a datacenter app fetches an instruction line

A trace, drawn from the paper's design, of how ICARUS predicts criticality from context and manages L2 by criticality and reuse.

Step 1 of 5

A fetch arrives after a specific path of branches

The front-end fetches an instruction line, having reached it through a particular recent sequence of branches and calls — perhaps deep in a library called from user code. Whether a miss on this line will starve the decoder depends on this path and on what else is in the pipeline.

The same line reached along a different path might not be critical at all, which is why the path matters.

Why it works

Branch-history context tracks criticality that a line label cannot. Only about 28 percent of critical lines stay critical, because criticality depends on the control-flow path → but coupling branch history with the line address predicts criticality per path → so ICARUS protects lines when they are actually about to be critical, not when they were once.
Combining reuse with criticality spends L2 where it pays. A critical line with distant reuse wastes space while a soon-reused line is evicted → but ICARUS ranks by criticality and reuse together → so capacity goes to lines that are both important and imminent, raising useful L2 hits.
Binning lets each class get the policy it needs. One priority ordering cannot serve lines with opposite reuse behavior → but four criticality-and-reuse bins each get their own priority chain → so critical-and-soon lines are guarded while critical-but-distant and non-critical lines are managed appropriately.
Targeting L2 hits the stall the front-end cannot otherwise hide. The decoupled front-end already hides L1 misses, so enlarging L1 is futile → but a saved L2 instruction miss directly prevents decode starvation → so effort at the L2 replacement policy converts into real front-end throughput.
Correcting the criticality signal closes the gap to the ceiling. A perfect instruction L2 is worth nearly 20 percent, yet static criticality captures about 2 percent → but predicting criticality dynamically and weighing reuse recovers much more → so ICARUS reaches 5.6 percent on average and up to 51 percent over the baseline.

What it costs (trade-offs and scope)

Prediction from context is imperfect. ICARUS predicts criticality from branch-history context rather than knowing it, so it can mispredict — protecting a line the path suggests is critical when it is not this time, or missing a newly critical one; its gains come from being right far more often than a static label, not from perfection.
It adds hardware state and mechanism. Coupling branch history with line addresses, tracking reuse, and maintaining four bins with separate priority chains costs storage and logic in the L2 controller (on the order of tens of kilobytes of overhead); this is modest but nonzero, and more complex than a generic replacement policy.
The benefit is workload- and configuration-dependent. The average gain is 5.6 percent but the range runs to 51 percent, so a few applications drive much of the benefit while others gain little; the value depends on how much of an application’s front-end stall is due to dynamically-critical L2 instruction misses.
It targets the L2 instruction bottleneck specifically. ICARUS addresses front-end stalls from L2 instruction misses in huge-code-footprint datacenter workloads; applications without large code footprints, or whose bottlenecks lie in the back-end or in data caching, are outside its intended benefit.
Evidence is simulation on a benchmark set. The results come from a gem5 simulation across 12 datacenter applications against specific baselines (TPLRU, DRRIP, DCLIP, EMISSARY); the near-20-percent ceiling and the reported speedups are for that setup, and behavior on other cores, applications, or real silicon is inferred rather than directly measured.

The evaluation

Managing L2 instruction lines for a huge-code-footprint datacenter workload

Property	Generic replacement (DRRIP)	Static criticality (EMISSARY)	ICARUS
Distinguishes critical instruction lines
Handles dynamic criticality
Considers reuse of critical lines
Works with the decoupled front-end and prefetchers
Speedup over TPLRU baseline

A comparison drawn from the paper. ICARUS is evaluated with the gem5 simulator across 12 datacenter applications against TPLRU, DRRIP, DCLIP, and EMISSARY; the 5.6-percent-average and up-to-51-percent figures are the paper's reported speedups over the TPLRU baseline, whose perfect-instruction-L2 ceiling is about 19.8 percent.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The full paper text was available (the authors’ own copy from the group’s publications page), so this account of the mechanism — the L2 instruction-miss front-end bottleneck and decode starvation, the decoupled front-end that hides L1 misses, EMISSARY’s static criticality preservation and its limitation that only about 28 percent of critical lines stay critical, ICARUS’s branch-history-coupled context for dynamic criticality prediction, and its combination of criticality and reuse into four bins with per-bin replacement priorities — follows the paper’s own description. The headline numbers are the paper’s reported results: across 12 datacenter applications ICARUS outperforms the tree-based pseudo-LRU baseline by 5.6 percent on average and up to 51 percent, versus 2.2 percent for EMISSARY and 1.6 percent for DRRIP, against a perfect-instruction-L2 ceiling of about 19.8 percent, with roughly tens of kilobytes of storage overhead and robustness across cache sizes and with prefetchers. Those figures come from gem5 simulation on a specific benchmark set and baselines; results vary by application and configuration. Exact per-application numbers, the context and bin mechanisms, and the storage accounting should be read from the paper itself.

Background

Why the front-end became the datacenter's bottleneck

It is worth stepping back to see why instruction supply, of all things, is where datacenter performance now leaks. For decades, computer architects worried mostly about data — cache misses on the values a program computes over — while instructions were assumed to fit comfortably in small, fast caches because programs were relatively compact. Datacenter software broke that assumption. A single request now traverses an immense stack: application logic, dozens of libraries, serialization and RPC layers, a managed-language runtime, and the operating system, so the sheer volume of distinct code executed to serve one request is enormous, and it grows every year as software accretes layers. That turns the instruction stream itself into a working set too large for the caches, and the front-end — which must fetch and decode all of it — becomes the limiter, with the powerful back-end idling for want of instructions. This is why a whole line of research now targets the front-end specifically, from prefetching instructions to laying out code better to, as here, caching instructions more cleverly. That concern with taming the front-end cost of sprawling warehouse-scale code is the same problem the profile-guided code-relinking work covered elsewhere on this site attacks from the compiler side, rearranging a binary’s code so the hot instructions pack together and stress the front-end less. ICARUS attacks it from the microarchitecture side, deciding which instruction lines are worth keeping close.

If you remember only three things

1. Datacenter applications have huge, fast-growing code footprints (about 30 percent a year) from deep system stacks, so even with a decoupled front-end that prefetches instructions and hides most L1 misses, the CPU front-end bottlenecks — chiefly on L2 instruction misses, which starve the decoder, empty the issue queue, and stall the whole CPU. A perfect instruction L2 would speed these apps up nearly 20 percent, but the prior best policy, EMISSARY, captures only about 2 percent because it treats a line's criticality (whether its miss causes decode starvation) as a fixed label, whereas only about 28 percent of critical lines stay critical.
2. ICARUS is an L2 replacement policy built on two insights: a line's criticality is dynamic and depends on the control-flow path that reached it, so ICARUS couples the recent branch history with the line address to form a context and predicts criticality per path rather than per line; and criticality alone is insufficient because critical and non-critical lines differ in reuse and even critical lines vary from soon-reused to distant, so ICARUS combines criticality and reuse, sorting L2 lines into four bins with their own replacement priorities and apportioning L2 capacity to maximize hits on the instruction fetches that actually stall the front-end.
3. Across 12 datacenter applications in gem5, ICARUS outperforms the tree-based pseudo-LRU baseline by 5.6 percent on average and up to 51 percent, versus 2.2 percent for EMISSARY and 1.6 percent for DRRIP, with roughly tens of kilobytes of overhead and robustness across L1 and L2 sizes and in the presence of prefetchers. Its gains depend on the workload having dynamically-critical L2 instruction misses, it adds hardware state for context and binning, and the results are from simulation on a specific benchmark set.

Check yourself

Check your understanding

1. Why do datacenter applications suffer a front-end bottleneck even with a decoupled front-end, and where is the key problem?
2. What is the flaw in EMISSARY's approach that ICARUS identifies?
3. How does ICARUS improve on static criticality detection?
4. What are ICARUS's main results and the conditions on its benefit?

Sources

The paper is “ICARUS: Criticality and Reuse based Instruction Caching for Datacenter Applications” by Vedant Kalbande, Hrishikesh Jedhe Deshmukh, and Biswabandan Panda (Indian Institute of Technology Bombay) and Alberto Ros (University of Murcia, Spain), published at ASPLOS 2026, DOI 10.1145/3779212.3790175. It is licensed CC BY.

This explainer is based on the paper’s full text, obtained from the authors’ copy on the group’s publications page. The account of the mechanism — the front-end bottleneck in huge-code-footprint datacenter applications, the decoupled front-end that hides most L1 instruction misses, the L2 instruction miss that causes decode starvation and stalls the CPU, EMISSARY’s static criticality-based preservation and its limitation that only about 28.32 percent of critical lines retain criticality, ICARUS’s branch-history-coupled context (BHC) for dynamic criticality prediction, the observation that reuse distance varies with the branch history that led to a fetch, and the combination of criticality and reuse into four bins with per-bin replacement priorities (the bin-based reuse-and-criticality mechanism) — follows the paper’s own description. The reported results cited here are the paper’s own: across 12 datacenter applications evaluated with the gem5 simulator, ICARUS outperforms tree-based pseudo-LRU (TPLRU) by 5.6 percent on average and up to 51 percent, versus 2.2 percent for EMISSARY and 1.6 percent for DRRIP, against a perfect-instruction-L2 ceiling of about 19.80 percent (15.7 percent geomean excluding an outlier), with modest storage overhead (on the order of tens of kilobytes) and robustness across L1 and L2 cache sizes and with hardware prefetchers. Exact per-application numbers, the context and bin mechanisms, and the storage accounting should be read from the paper itself.