And we want to go find our data. Hm.
So, how do we, how do we go about doing that?
What's interesting here is, when we did this, we only had to check one tag
location. Well, for a cache like this.
The index is going to tell us which of the two sets it's in.
But, it can either be in either of the two ways of, of these sets.
So, we actually need to do a tag check against this tag and that tag, and check
the two valid bits. Many caches can do this in parallel, but
that's how you can figure out, and it's possible that it's in neither of those two
and we have to just say, that, it's a cache-miss.
Okay. So, let's, let's talk about, when you need
to go taking things out of the cache. So, let's talk about block replacements.
We need to figure out what to go, kick out of the cache, when you take cache missing,
it will bring, bring some new data in. So, an important point here is in direct
mapped cache, this question makes no sense cuz in direct mapped cache, it can only go
to one location. In set associative or fully associative
caches, we need to make a decision. And hopefully, we only need to make this
decision when a set becomes full. Because, otherwise, we'll just choose the
empty location in that set. So, if you have a two-way set associative
cache. And one of the ways is full of data, and
the other one is just empty. The valid bit is empty.
We probably shouldn't even be looking at, sort of different choices on how to
replace things, because, there's an open spot to go put the data, we should go put
the data there. Okay.
Som what are, what are some, good block replacement policies, or good cache
replacement policies? First one, is random.
You can just choose randomly out of a hat. Actually, it doesn't work so bad.
It's, it's, it's, you know, it's easy to implement, you just like, have some random
unique feedback shift register, or sometimes you just sort of choose some
random number and, and you replace it. Not so, not so bad.
Well, well, now, now we start thinking about put, put our thinking caps on, we
can start thinking about some better, better ways to go do this.
When we need to think about least recently used, hm.
So, the idea behind this strategy is that you are trying to preserve temporal
locality. So, if you've used some data recently,
there's a heuristic here, that it's likely to be used again in a not too distant time
axis. So, if you look back to that sort of time
versus address block that we had, in the time axis we think that, you know,
temporal locality is something that happens relatively often.
So, one, one really good strategy is to try to look at the least recently used as
the block to get rid of. So, if something has not been used
recently we kick that out of cash. Now, some problems with this is, this gets
really hard to do. Well, there's two problems.
One, to implement appropriate lease recently used, every single load or store
that happens to the cache, needs to update the information.
Well, that's not great for power. But it's also not great because you
basically need to have sort of a very fine during tracking information on each cache
line on every single cycle that does a load or a store.
So, you know, you need, you need some cache data that needs to be updated pretty
often. Plenty of people do that, though.
There's, you know, if you have a least recently used, piece of information where
you have extra bit on each cache line, you can think about just sort of flipping that
back and forth and having one bit for that information and every single load and
store actually sets that bit and lots of processors do that.
So, what, what starts to get hard here is when you try to go above 2-way caches.
So, 2-way you have sort of one bit that can decide where, which is the most least
recently used. If you start to have, let's say, an 8-way
associative cache, you want to do true, least recently used, you've got to somehow
keep like timing stamps for each different way.
You have to say, oh, well, this one was just recently accessed and, you know, you
can time stamp it. You can try to sort of reorganize a list
of numbers in order. And these are the things that start to get
harder to do in hardware and especially, you know, on the critical path of your
processor. So, lot of times what people do is they
have pseudo list recently used for higher associative caches where you'll try to
sort of keep maybe accurate information of the last two most recently used lines and
the other ones you do random or something like that.
Or there's some more complex things which we'll talk later in the class about.
Another one, first in, first out. So, whatever gets brought into the cache
first, sits in the cache for some period of time and then gets kicked out in the
future. So, you're sort of guaranteed that some
piece of data that you bring in will sit in your cache for some period of time, and
this is a lot easier to implement in highly associative caches.
But it's certainly not implementing least recently used because if you sort of bring
in a cache line. Let's say, you have a four-way set
associative cache. Four axises later, it's sort of the top of
the list to get kicked out. But what's nice about this is you're
guaranteed it'll sit in your cache for some period of time and won't just get
sort of randomly kicked out, which like random, has problems with.
Finally here, another, another acronym here, not most recently used.
Well, let's think about that one for a second.
So, we're going to kick out something, that is not the most recently used block.
So, if we can sort of keep track and say that we and we have some index into our
cache, if we have a four-way cache, we can think of having sort of two bits that
says, well, this line was the most recently used and the rest of them was
sort of random. And we know we are not going to be kicking
out the most recently used cache. So, write strategies, you're going to do a
store, you've got to know where you put the data.
