algorithm LRU, how many bits needed for implement this algorithm?

Question

I have a little question about the algorithm LRU. If you have a cache with four blocs , how many bits do you need to implement this algorithm ?

Solution 1

There is a good slide-deck at http://www.powershow.com/view/95163-NzkyO/4_4_Page_replacement_algorithms_powerpoint_ppt_presentation that talks about various page replacement schemes. It also explains the LRU implementation using mxm matrix really well.

Solution 2

Assuming you mean a 4-way set-associative cache:
A "perfect" LRU would essentially be assigning each line an exact index in the order of usage. You can also think of that as an "age". So each of the 4 elements would require an index of 2 bits (since we need to count 4 distinct ages) stating its location in the LRU order - this means 2 bits * 4 ways, per each set of the cache.
In the general case of n ways, you'd need log2(n) bits per line, or n*log2(n) bits per set.

By the way, there are cheaper ways to reach an almost-LRU behavior, see for e.g. Pseudo LRU which would only require 3 bits for the entire set in your case (or in general: #ways - 1)

Solution 3

The minimum number of per-set bits is ceiling(log2(N!)) where N is the number of ways.

This can be seen easily for four-way associativity by noting that the MRU block (A) can be any of four blocks, the almost MRU block can be any of the three remaining blocks (B ∈ {0,1,2,3} and B ≠ A), the almost LRU block can only be one of the two remaining blocks (C ∈ {0,1,2,3} and C ≠ A and C ≠ B), and for the LRU block only one block is available. Therefore the number of possible states in total is the product of the number of these independent states, i.e., 4! (or for the general case N!).

B bits can encode 2^B states, so B must be greater than or equal to log2(the_number_of_states). For the 24 states of four-way associativity, five bits are needed.

(Increasing the number of bits may simplify the state machine used to manage this information, so the minimum number of bits required might not match the actual number of bits used in a real-world implementation.)

As Leeor's answer noted, tree pseudo-LRU (which maintains a tree of single-bit/two-way LRU choices) only requires N-1 bits. This pLRU is relatively simple to implement, so even at 4-way associativity (where only two bits of storage are saved — 3 bits vs. 5 bits) this form of pLRU can be attractive.

(At 8-way associativity, true LRU requires 16 bits of state, compared to only 7 bits for tree pLRU. Clearly at higher associativities, true LRU becomes more expensive, but it may still be worthwhile in simplifying worst-case execution time analysis and it has been chosen as a replacement policy for some fully associative TLBs.)