So how do we implement the least recently used policy that
works really well?
And it works really because it exploits well locality.
The most recently used thing is likely to be used very soon afterwards.
The thing that we haven't used for a while means that there is less
reason for locality to kind of cause it to be accessed again.
Let's say we have a four way set associative cache and
let's just track what's happening in this one set.
So there is four blocks in it.
For each of these blocks we keep the tag and the valid bit.
And in order to track which block was accessed when,
we are going to also have an LRU counter for each block.
These counters take values that correspond to the size of the set.
In this case, 0 through 3 because there are four things in the set.
So let's initialize them to 0, 1, 2, and 3.
They have to all be different all the time, and
we will see how that is maintained.
So, we start like this.
When we want to replace something, we will replace the block whose count it
is currently 0 because that's going to be the least recently used block.
So, let's say we access some block, A.
And we need to put it somewhere.
We will choose the place with the 0 counter and put it there.
Now that the block is placed there, the processor accessing it
and suddenly this becomes the most recently used block.
So, it's counter now needs to be 3.
In order to make sure that all of the counters still have different values
that means that all of the other counters now need to be decremented.
So, the one that was 1 becomes 0.
2 becomes 1, and 3 becomes 2.
And now, let's say that we access sum block B.
We put it here, because the counter is 0, now, here.
When B is accessed after putting it here, that counter becomes 3.
This one becomes 2.
This one becomes 0 and this one becomes 1.
We will now put in block C here.
That becomes 3.
This becomes 2.
This becomes 1.
This becomes 0.
D, 3, 2, 1, 0.
Now we're back to this situation.
So I'm going to clean up here.
And now, if we access E,
we're going to find what was the least recently used block.
And A, at this point, is because it's been accessed the least recently.
So A will be replaced by E.
And the LRU counter here becomes 3 which brings these one notch lower.
So this is the state we have.
Now let's say that B, which is the least recently used block now, is re-accessed.
What happens then is this counter needs to become 3.
All of the other ones now need to be changed lower.
What happens if the most recently block, let's say, B is accessed again?
Then this count just stays at 3 because that indicates that this is already
the most recently accessed block.
What happens if block D, which is neither the most nor
the least recent, is accessed?
Well this counter needs to become 3 and now we have an interesting situation.
We don't just lower all the other counters a notch down.
We take the ones that were above the original value of this counter.
So we take the counter that is above 1, and
those are the ones that get a notch down.
But the ones that are below one stay the same.
That ensures that the counters still have different values.
let's do another one of those where let's say block B,
that is almost the most recently used block, is accessed.
In that case this counter needs to become 3.
All counters that were above its original value of 2 need to be
decremented.
So, this becomes 2, but these two stay the same because they're below 2.
So again, we have this situation.
So now you know how to maintain the LRU counters properly.
After every step you can verify that the counters have different values.
If they don't, then you probably made a mistake somewhere.
So as you can see maintaining LRU is relatively complicated.
For an N-way set-associative cache,
we need N counters whose size is LOG2(N).
In this case the size of the counters is 2 bit because they need to have a number
between 0 and 3 to tell us where are we in the order of access in the set.
So it's a four way set associative cache,
that means we need two bits per counter and four counters.
So for highly associative cache it's something like 32 way associated.
You would need to have 5 bit counters and 32 of them per set.
So this was the cost.
It's pretty high.
Worse, there is an energy problem.
We need to modify up to N counters on each access,
even cache hits that can happen very frequently.
So the LRU approximations try to keep fewer counters and
do fewer updates on cache hits.