LRU cache algorithm

I need an LRU algorithm for a 4-way associative cache having additional 5 bits per set to indicate which line should be evicted.

       -------------------------------------
Set x: | line_0 | line_1 | line_2 | line_3 |
       -------------------------------------

      -----------------------------------------
      | bit_4 | bit_3 | bit_2 | bit_1 | bit_0 |
      -----------------------------------------

At first, I tried to divide my problem into smaller ones. Having only two lines, I would fire bit corresponding to currently used line at the same time setting other one to 0.

The victim would be the line with bit set to 0 (provided that set is full).

I thought I could use this in a 4-way cache having bits bit_4, bit_3, bit_1, bit_0 corresponding to line_0, line_1, line_2, line_3 and a middle bit to indicate which side was used most recently. Quickly I realised that it is not precise enough. I.e. after a sequence line_0, line_2, line_3, line_1 the bits would be: 10101, that would indicate that the left side was referenced most recently (which is true) but this does not necessarily mean that side wasn't referenced least recently.

I would be very grateful for any hints.

Solution

In order to consistently find the least recently used item, you need to keep track of the order in which the 4 cache lines have been most recently used.

There are 4! possible orderings. 4! is 24 possibilities, and there are 32 possible configurations of your extra 5 bits, so you have enough bits (yay!). You don't have a lot of extra bits, though, so you can't really expect the encoding of the order to be super easy to work with.

Off the top of my head, I think I would do it like this:

2 bits for the least recently used item: 0-3. This is the one to evict if you need to.
2 bits for the 2nd least recently used item: 0-3
1 bit for the 3rd least recently used item. There are only two possibilities, because the other two are already used. 0 means the remaining cache line with the smaller number.
0 bits for the most recently use (4th least recently used). There's only one left, so you don't need to store anything to know which one it is.