Replacement picks the eviction victim when every way of a set is valid. The policy only affects conflict and capacity victims, never compulsory misses.
True LRU tracks exact age per line. Cheaper approximations trade accuracy for fewer bits and faster decisions.
Policy | State per set | Weakness |
|---|---|---|
True LRU | Age per line | Bit cost and update energy grow with ways |
Tree pseudo-LRU | One bit per tree node | Skews under bursty reuse, evicts the wrong branch |
Random or not-recently-used | Almost none | Evicts hot lines by chance |
Adaptive insertion (BIP, DIP, RRIP) | Insertion priority plus small counters | Needs telemetry and a fallback |
A cyclic working set one line larger than the cache defeats LRU completely. Every access evicts a line that is needed again almost immediately.
Belady optimal replacement sets the bound. It evicts the line used farthest in the future, which needs perfect knowledge and serves only as a reference.
4-way set, cyclic trace A B C D E repeated twice (10 references)
LRU: fills A B C D (4 misses), then every reference evicts its own reuse
LRU misses = 10 of 10
optimal: fill A B C D (4 misses); E evicts D (used farthest ahead);
A B C hit; D evicts A (never reused); E hits
optimal misses = 6 of 10 (A B C D E D)
gap: 4 avoidable misses per 10 references bound what insertion can winReference | 1-4 | 5 (E) | 6-8 (A-C) | 9 (D) | 10 (E) |
|---|---|---|---|---|---|
LRU | 4 misses | Miss, evict A | 3 misses | Miss | Miss |
Optimal | 4 misses | Miss, evict D | 3 hits | Miss, evict A | Hit |
Insertion policy decides where a new line lands in the age order. Bimodal insertion usually places newcomers as almost-evictable, so streaming fills drain without flushing hot lines.
Reuse distance guides the choice. A histogram of distances past the associativity marks thrash, and dead-on-fill lines confirm pollution rather than a capacity shortfall.
Fix | Idea | Watch out for |
|---|---|---|
Bimodal insertion | Most fills insert near LRU, a few near MRU | Too few MRU inserts starve real reuse |
Dynamic insertion | Set duel picks LRU or bimodal per phase | Duel sets must mirror the workload |
Re-reference interval prediction | Two-bit priority per line, hit resets it | Counter width and scan order need review |
New policy. The lines almost fit, so insertion keeps the reusable fraction without new SRAM.
Prefetch admission, not replacement. Dead arrivals pollute regardless of victim choice.