Replacement Without Exact LRU: Reference Bits and Clock Hands

Exact least-recently-used replacement requires knowing, at eviction time, which of the W lines in a set has the oldest last-reference. Maintaining that order is a data structure problem: on every hit the referenced line must move to the front of a list, which means updating the position of every line it passes. In a software cache that costs a pointer splice. In a hardware cache accessed every cycle, with W lines compared in parallel and the index chosen before the access even completes, there is no spare cycle to perform it. Real caches therefore approximate LRU with a small amount of per-line state and a rule that is cheap enough to run in the same cycle as the tag comparison.

What LRU is worth, and what it costs

The appeal of LRU is that it needs no knowledge of the future and still tracks the property that matters for most code: a line used recently is likely to be used again soon. Belady’s optimal policy, which evicts the line whose next reference is furthest away, requires the future and is used only as a bound. LRU’s guarantee is structural rather than competitive: a cyclic access pattern larger than the cache makes LRU miss on every reference, while a random policy would hit occasionally, so no ratio bound against the optimum exists. Belady’s anomaly — adding capacity can increase the miss count for some policies — does not affect LRU, because LRU is a stack algorithm: the set of lines resident in a smaller cache is always a subset of the set resident in a larger one. That inclusion property is what makes LRU analytically convenient, and it is the property that most approximations give up.

The hardware cost of exact LRU in a W-way set is the maintenance of an ordering over W items. Encoded as a matrix of W(W−1)/2 bits, where bit (i,j) records whether line i is more recent than line j, a hit requires setting a row and clearing a column — W bit operations in parallel, which is feasible for small W and increasingly unattractive as W grows. For eight ways that is 28 bits of state per set; for sixteen ways, 120 bits. The state is comparable to the tag storage itself, and the update logic sits on the critical path of every hit, beside the tag comparison that decides whether a hit occurred.

One bit and a hand

The classic approximation keeps a single reference bit per line and a per-set pointer. On a hit, the hardware sets the line’s reference bit. On a miss, the replacement logic scans the set from the pointer forward, clearing reference bits as it goes; the first line whose bit is already clear is the victim, and the pointer advances to the next line. This is the clock algorithm, so called because the pointer sweeps the set like a hand over a dial.

/* Clock replacement over one set. Returns the way to evict. */
int clock_pick(int *ref, int *hand, int ways)
{
    for (int scanned = 0; scanned <= ways; scanned++) {
        int w = *hand;
        *hand = (*hand + 1) % ways;
        if (!ref[w])            /* second chance exhausted: this line is cold */
            return w;
        ref[w] = 0;             /* give it a second chance, keep sweeping */
    }
    return *hand;               /* every line was referenced: evict arbitrarily */
}

The bound on the loop is what makes the mechanism work: the hand never scans more than ways + 1 entries, because after one full pass every bit has been cleared and the second pass finds a victim immediately. The first pass is the expensive case and it happens exactly when all lines have been referenced since the hand last passed — that is, when the set is genuinely hot and every line is a plausible victim. The cost of the scan is amortised across misses, not paid on hits, which is why the scheme is affordable: a hit costs one bit set, and hits are the common case.

The behaviour this produces is not LRU. A line referenced once since the hand last passed is indistinguishable from a line referenced a thousand times; both have a set bit and both get one reprieve. The policy is closer to “not recently used” than to “least recently used”, and the interval that “recently” covers is the time for the hand to make a full revolution, which is set by the miss rate. Under a high miss rate the hand turns quickly and the policy degenerates toward FIFO. Under a low miss rate it turns slowly and the policy behaves almost like LRU, because the bits accumulate enough history to discriminate.

Second-chance variants and their failure modes

The plain clock has a known pathology: a set whose lines are all referenced on every pass will be scanned in full every time, and the victim is chosen by the hand’s position rather than by age. A sweep that encounters all-set bits degrades to round-robin, which is FIFO in disguise. Workloads with a working set slightly larger than the cache produce exactly this pattern, and the resulting miss rate can exceed FIFO’s because the hand’s reprieve keeps stale lines alive while fresh ones are evicted.

Two refinements are common. The first adds a second bit, giving four states per line: not referenced, referenced once, referenced more than once, and a “recently referenced” flag that survives one sweep. The enhanced second-chance scheme used in some operating system page reclaim classifies pages into four categories by the pair (referenced, modified) and evicts in the order (0,0), (0,1), (1,0), (1,1) — preferring clean unreferenced pages because evicting them costs nothing. The same idea applies in a cache: a dirty line costs a write-back, so a clean line of equal age is the better victim.

The second refinement replaces the linear scan with a tree. A pseudo-LRU policy for a W-way set stores W−1 bits in a binary tree over the ways, each bit recording which subtree was accessed more recently. A hit updates the log2(W) bits on the path from the leaf to the root; the victim is found by walking from the root toward the less-recently-used subtree. For eight ways that is seven bits per set instead of 28, and the update touches three bits instead of eight. The information is coarser: the tree distinguishes the least-recently-used half-set at every level but not the exact order within a leaf pair, so two lines in the same pair are indistinguishable.

/* Tree pseudo-LRU for 8 ways: bit i records which half of node i was used last. */
int plru_victim(unsigned *tree)
{
    int node = 0;
    for (int depth = 0; depth < 3; depth++)
        node = 2 * node + 1 + ((*tree >> node) & 1);   /* follow the stale side */
    return node - 7;                                    /* leaves are nodes 7..14 */
}

void plru_touch(unsigned *tree, int way)
{
    int node = 7 + way;                       /* leaf index for this way */
    while (node > 0) {
        int parent = (node - 1) / 2;
        /* Left child is odd, right child even. The bit points away from the
           child just touched: 0 walks left next, 1 walks right. */
        unsigned away = (unsigned)(node & 1);
        *tree = (*tree & ~(1u << parent)) | (away << parent);
        node = parent;
    }
}

Tree pseudo-LRU is the common choice for moderately associative L1 and L2 caches because it is cheap and has no pathological scan. Its weakness is visible in a specific pattern: a program cycling through three lines in a four-way set will evict one of them on every pass, because the tree only knows which half was used last and cannot tell that the fourth line is the one that is truly cold. The miss rate in that case is one per reference, the same as a fully associative cache with the same cycle.

Why not just use the address

A different family of policies ignores recency and uses the address. Random replacement needs no state beyond a pseudo-random number generator, has no pathological patterns, and performs within a few percent of LRU on many traces — which is why some last-level caches use it, since it also spreads victims across sets in a way that helps with shared-cache fairness. Not-recently-used, the policy family behind the RRIP designs, goes further: each line carries a small re-reference prediction value, new lines enter at a distant value, a hit resets the value toward near, and the victim is the line with the most distant prediction. That makes the policy resistant to scans, which LRU handles badly — a streaming access that touches each line once evicts the entire cache under LRU, while a policy that gives single-use lines the highest eviction priority leaves them untouched.

The choice between these families is not about which is closer to LRU. It is about which failure mode the workload can tolerate. LRU and its approximations fail on cyclic patterns and on scans. Random fails by occasionally evicting a hot line for no reason, which costs a small uniform penalty. RRIP fails when the prediction is wrong about a line’s future, which happens with phase changes. Hardware tends to pick the policy whose worst case is bounded, which is why approximate schemes with a small fixed state dominate over exact LRU despite LRU’s better average.

A final constraint binds all of them: the policy must be implementable without a stall. Whatever state it keeps must be updatable from the hit path, in parallel with the tag comparison, without lengthening the pipeline. That requirement, more than any hit-rate consideration, is why a cache has a handful of bits per line for replacement and a few hundred for the tag, and never a linked list. It is also why the prediction-value schemes in re-reference interval prediction fit where a list cannot: two bits per line, updated in the hit path, no ordering to maintain.