I have read that true LRU page replacement requires significant hardware support, so only approximation of LRU is implemented for page replacement.

So I wanted to contrast LRU that is implemented for cache, and that for page replacement. Like - Is LRU properly implemented for cache?


LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each set.)

For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier to analyze for worst-case execution time. Binary tree pLRU is relatively simple to implement because an access to a given way will always merely set/clear specific bits.

For associativities higher than eight, FIFO, random, and Not Recently Used have been used. E.g., the Itanium 2 6M used NRU that is similar to the clock page replacement algorithm in that a bit is set when accessed and all the bits are cleared when they have all been set.

An interesting exception is the use of true LRU in the 32-entry fully-associative L1 TLBs for several Itanium implementations. For a fully associative TLB, true LRU is less expensive because there is only one set, so storage and control logic can be bundled together.

It should also be remembered that LRU is really just an estimate of relative reuse distance; approximation of a conceptually-derived heuristic can be roughly as effective as the ideal heuristic. (Even reuse distance may not be ideal for replacement because not all entries have the same cost/benefit.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.