Re-Reference Interval Prediction in Shared Last-Level Caches

A last-level cache shared by many cores faces a problem the upper levels do not: it sees the residue of every core’s misses, mixed together, with no structure the hardware can rely on. Least-recently-used replacement, or any close approximation, has two well-known failures at this level. A streaming access that touches each line exactly once evicts the entire cache, because every streamed line is the most recently used until the next one arrives. And a working set slightly larger than the cache produces thrashing, because the policy keeps the newest lines and discards the ones about to be reused.

Re-reference interval prediction addresses both by changing what the replacement state means. Instead of recording when a line was last used, the policy records how soon it expects the line to be used again, and it makes that prediction at insertion time, before any evidence exists.

Two bits of prediction

Each line carries a two-bit re-reference prediction value, giving four levels from 0 to 3. The convention is that a higher value means a longer expected interval before the next reference, so the victim is the line with the highest value — 3, the “distant” prediction. A hit sets the line’s value to 0, marking it as likely to be reused immediately. On insertion, a demand fill is given the value 2, one below the maximum, so a new line is treated as distant but is not the first candidate for eviction. When the cache needs a victim it scans the set for a line with value 3 and evicts it.

The insertion value is where the scan resistance comes from. A streamed line enters at the same prediction as any other demand fill, and it is never re-referenced, so it stays at that value while lines that are hit move below it. The first streamed line to be evicted is therefore an old streamed line rather than a frequently used one. Under LRU the opposite happens: the newest line is the most recently used, so a stream evicts everything in its path. The prediction value makes the policy behave like not-recently-used for single-use lines and like LRU for lines with reuse.

The scan is bounded by the associativity. If no line in the set has the maximum value — every line has been hit since it was inserted — the policy increments all values and retries, which effectively ages the whole set. With W ways and 2 bits, at most a small number of passes is needed, and the increment can be done in parallel across the ways. The cost is a few gates per way, which is why the scheme is implementable where exact LRU is not.

/* RRIP victim selection over one set: evict the line with the longest
   predicted re-reference interval, ageing the set if all are short. */
int rrip_victim(unsigned char *rrpv, int ways)
{
    for (int pass = 0; pass < 4; pass++) {    /* 3 increments saturate 2 bits */
        for (int w = 0; w < ways; w++)
            if (rrpv[w] == RRPV_MAX)          /* 3: predicted far away */
                return w;
        for (int w = 0; w < ways; w++)        /* no far line: age the set */
            if (rrpv[w] < RRPV_MAX)
                rrpv[w]++;
    }
    return ways - 1;
}

void rrip_insert(unsigned char *rrpv, int way)
{
    rrpv[way] = RRPV_MAX - 1;                 /* distant, but not maximal */
}

Set dueling chooses a policy without measuring it

The insertion prediction is a parameter, and the right value depends on the workload. A cache where every fill is inserted as distant resists scans but reacts slowly to a phase change: a new working set takes a while to displace the old one. A cache where fills are inserted as near adapts quickly but is vulnerable to streaming.

Set dueling resolves the choice by running both policies simultaneously on disjoint parts of the cache and letting a counter decide. A small number of sets — a fraction of a percent of the total — are designated as leaders for each policy. Leader sets for policy A always use A’s insertion value; leader sets for policy B always use B’s. The remaining follower sets use whichever policy currently has the lower miss count, as tracked by saturating counters that increment on a miss in a leader set of one policy and decrement on a miss in the other.

/* Saturating counter arbitrating between two insertion policies. */
void duel_update(int *counter, int leader_policy, int missed)
{
    if (missed && leader_policy == POLICY_A && *counter <  COUNTER_MAX) (*counter)++;
    if (missed && leader_policy == POLICY_B && *counter > -COUNTER_MAX) (*counter)--;
}

int follower_insert_value(int counter)
{
    return counter >= 0 ? DISTANT : NEAR;      /* A leads: resist scans */
}

The elegance is that the followers never need to know their own miss rate. The leader sets are statistically representative because they are chosen by index, so the address stream that reaches them is the same distribution as the stream reaching the followers. The counter is a comparison of two samples, and its saturation limits how fast the policy can flip, which prevents oscillation when the two policies are close.

The mechanism generalises beyond insertion. The same leader-follower structure can arbitrate between replacement policies, between prefetch aggressiveness settings, or between any two configuration bits whose effect is measurable as a miss count. The requirement is that the leaders see a representative stream and that the metric is monotone in the decision, which miss count is.

Where the scheme breaks

The first failure is phase behaviour. A prediction value records an expectation, not evidence. A line that was hot during one phase and cold during the next keeps a low value until it is evicted, and a policy that only increments on scan cannot distinguish it from a line that is about to be reused. The victim is chosen among lines the policy believes are distant, which may include lines that are merely old. The miss that results is a capacity miss the policy could not avoid without more history.

The second is that the prediction is per line, not per access pattern. Two cores sharing a line produce one value, updated by whichever core touches it. A line read by one core and written by another has a coherence story that the replacement value does not see, and a coherence-induced invalidation removes the line without the replacement policy being consulted at all. The policy’s model of reuse therefore covers only the misses that reach it, not the ones another core’s write caused.

The third is interaction with prefetching. A prefetched line inserted at the same prediction as a demand fill occupies a way and is treated as if it will be reused, which is exactly the pollution problem that prefetch distance discusses. Designs that combine the two insert prefetched lines at a more distant value, so they are the first candidates for eviction if the demand access does not arrive. This requires the fill path to distinguish a prefetch from a demand, which the cache can do because the request carries that information.

Fairness, and the shared-cache problem proper

A shared last-level cache has a second problem beyond hit rate: the distribution of hits among cores. A policy that maximises aggregate hits can starve one core. A core running a streaming workload fills the cache with lines it never reuses, and a core with a small working set loses its lines to that stream. The aggregate miss count may improve while one core’s throughput collapses.

The standard framing is the miss-rate versus fairness trade. Policies that maximise hits tend to favour cores with high locality, because their lines are the ones that generate hits. Policies that equalise misses per core sacrifice aggregate hits to give each core a share. The measurement is usually expressed as a stack distance or as a per-core allocation, and the hardware mechanisms are variants of insertion policy: a core that is over-allocated has its fills inserted at a more distant prediction, so its stream is evicted preferentially.

The difficulty is that the hardware cannot see which core is over-allocated without counting. The counter must be per core, updated on every fill, and compared against a target share; the target share is itself a policy choice. Implementations approximate by tracking the number of lines each core holds in the cache, using a sampled or set-associative estimate rather than an exact count, and adjusting the insertion value when a core exceeds its share. The estimate is noisy, and the adjustment is a feedback loop whose stability depends on the sampling rate.

There is a degenerate case worth naming: when all cores are streaming, every policy is equivalent because no line is reused and the miss rate is 100 percent regardless. When all cores have small working sets that fit, every policy is also equivalent. The interesting regime is the middle, where the aggregate working set exceeds the cache and the cores differ in locality, and that is precisely the regime where the choice of policy changes the result by a factor rather than a percent.

What the policy cannot do

No replacement policy can beat the optimal one, and the gap is a property of the workload rather than of the policy. Belady’s algorithm, which evicts the line whose next use is furthest in the future, requires knowledge the hardware does not have. The practical target is to close the gap on the patterns that matter: scans, which a prediction value handles; thrashing, which the dueling mechanism handles by flipping to the near-insertion policy; and phase changes, which no local policy handles well because the evidence arrives only after the phase has changed.

The residual is the same as in every level of the hierarchy. Replacement decides which line to lose, and the loss is a miss that costs the full latency to the next level. The way to reduce the cost is not a better policy but a better structure — more capacity, more bandwidth, or a prefetcher that turns the miss into a hit before the demand arrives. The policy’s job is to make the misses that remain the ones the program can afford, and the four prediction values are enough to do that for the patterns that general-purpose code actually exhibits.