0

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.

Improve this question
2
  • Maybe this help: www3.ntu.edu.sg/home/smitha/ParaCache/ParaCache/sa4.html Commented May 28, 2020 at 1:00
  • I do appreciate your help, this application provides great caching simulation but it's not necessarily solving my problem. I do understand how it works but I seem to get stuck on how to use 5 bits to indicate least recently used line. Commented May 28, 2020 at 1:14

1 Answer 1

Reset to default
1

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.
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This is really helpful! Trying to reimplement my algorithm I thought "Ok but what happens if one of those lines used is 0? How do I know whether it's actually been accessed or not?" And I realised I can use a number of dirty bits that are set to 1 (correct me if I'm wrong) to indicate how many of those lines were actually modified!
Why not just store the permutation index? No need to fiddle with bits.
True, my solution would be very inefficient. So the other idea would be to create something like table where I would associate a number from 1-24 with particular permutation (not actually implementing it). In case when not all lines in my set are valid I guess it would be ok to chose a random permutation that stores the right order of recently accessed lines (i.e. when accessing line_0 then line_3 any xx30 permutation would fit since first two lines are equally least recently accessed. So what I would do is describe steps for each possible transition. Is there a more efficient way to do this?
@Dialecticus It doesn't make much difference, but it might be nice to minimize the number of lookup tables required in the implementation.
@wkkuna yes, the ordering of invalid lines just doesn't matter, as long as you use them first. Implementation will require 2 transition functions. HIT: State, Line -> State, that you use to get the next state after a cache hit, and one MISS: State -> State, Line, that you use to get the new state and line to evict after a cache miss.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.