Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
And welcome back. Now let's take a look at what block replacement might mean and actually see an example of thinking about who might get kicked out when things get full.
So, block replacement policy. What do we know about caches? We have a knob.
That knob can either go to — if it's M total blocks in the cache and it's N-way set associative when N is one direct-mapped.
When N is M fully associative and now is the middle, like 2 or 4 or 8, I'm N-way set associative. So when N is 1 and I'm direct-mapped, it's clear what we do.
If I have to replace a block, it's the block that used to be there, because everybody, every color blue, blue, blue, blue maps to the blue guy.
And if this is the one that's supposed to be there and there's somebody else whose tag doesn't match, get that guy out. Easy.
Both N-way set associative and fully associative are N-way within its set and fully for the whole cache — fully associative within either the set or the whole cache, respectively.
So it means that — what happens? Well, if I have a choice, where do we write the incoming block when we're fully associative? Well, first of all, let's find a blank spot.
I mean blank is weird, because there's bits everywhere.
But let's first check the valid bits, see if there's any rows, any blocks that are invalid, blocks that are garbage, and they're cold in some sense, that that block is empty.
Put it in that spot. Don't do any work. Don't have to kick anybody out. But what happens when they're all full?
What happens when they're all valid but none of the tags match and we got to bring somebody else in? Well, folks, ain't no free lunch. Somebody's got to go.
This one has to go in, somebody has to go out. We can't do anything else. So how do we decide?
And that's called the block replacement policy, the replacement policy when we replace a block because we're in a fully associated window, either within a set or within the whole cache — if it's fully associative in the whole cache.
How do we kick out some guy if they're all full but none of them are the same tag as the one I want to bring in?
So the most common thing we do is the Least Recently Used. Most recently means I just touched it, freshest, hottest, right there. Least recently, it's the one with cobwebs.
Least recently means the one that hasn't been used at all. So who got back in the early days of yesteryear and hasn't been touched since?
And somehow, we have to remember — let's talk about this. Let's just talk about why we even do this. Why would we do LRU?
Because temporal locality, temporal locality says if I access a particular memory location, chances are pretty high that, all things being equal, I'm going to access that same thing again.
I'm probably going through an array or maybe I'm doing a sum.
Maybe I'm adding to one element of the array is the sum, and I keep taking all the elements putting it in this element.
And the first element is going to be the sum as I add up all these guys, keep stuff in this guy. Well, that guy gets hit a lot.
So that's what LRU is about.
LRU says if you visited before, I need to kick out the oldest one that I'm probably not using and keep the ones that I am using — again, exploiting temporal locality.
The downside is I now have to keep track of the relative order of things. I've got four sets — let's say four-way set associative. I'm only talking about them with a set now.
And let's say I touch them this guy first, then this guy, then this guy, then this guy, load them all in. Everything's happy. Cache is very warm. I'm going brr.
I'm just reading through these guys. Now all of a sudden, I read a fifth guy. Well, and who's the oldest one? Well, I read one, two, three, four.
This is the most recent. I touched one, that was the oldest one. Then I touched that one, then this one, then this one. That's the newest one.
That's the oldest. Well, I'll kick this guy out. So now this is the newest one.
But now this is the newest, but now that's the second, and this is the third, and that's the fourth. Okay, now we load the thumb in. Who does it — well, it's the fourth.
Then this guy has to go out. And now this is the newest, that's the second, that's the third.
So you can imagine, I've got to keep 4 factorial kind of combinations of — permutations, really — of what the ordering is.
And so four things, the ordering of that is 4 factorial, that's 24 things. I now need 5 bits. Go ahead.
Have some fun trying to come up with the logic for how to update that. It's almost like you're keeping a record, a scratch book, which is easy to do in software.
If I had this software cache, really easy. I can just do this all in software, have a set and ordering and give it a number and then update.
I up the numbers, easy. Harder, much, much harder to do in hardware. So that's not easy to do. Even four-way is very hard to do.
Imagine eight-way. Crazy, right? 8 factorial. [MAKES EXPLOSION SOUND] But two-way is really easy.
LRU says if I grab — here's two rows. I grab this one. Well, that's the one I haven't grabbed recently.
So give this a bit called the LRU bit, points there, points to 0 or 1. This means if I just touched this one, that's the least recently used.
Very easy. So you can use a single bit for a two-way. Love that. So actually, we get to see an example in about two minutes to think about this.
FIFO. What does FIFO mean? You hear FIFO in computer science, you think a queue, right? First in, first in, first out, like waiting in the line for checkout of a grocery store.
And that says I'm going to ignore the accesses. Okay, yeah, load it into the cache and you're chugging through and you're waiting. And maybe other things are being filled up around you.
That's fine. You're enjoying your time. Maybe people are accessing you. But being accessed doesn't bump you to the front of the line.
This whole example I was doing here is whenever you get touched, you get bumped to the front of the line, you get reordered like that.
In a FIFO model, you just say, no, when you got loaded in, that's the order. And then you're the first one out.
It feels fair in a way, but it kind of ignores the temporal locality. It ignores the fact that I keep hitting this guy.
Even though it was there — well, no, eventually, even though I'm hitting it every time, sorry, you get out. But I'm hitting it every time or every other time.
Nope. This one and then somebody new in, and this one and somebody new, and this was one and somebody — well, keep this guy in. This guy is obviously interesting.
Nope, sorry. Whatever. You're next in line for being kicked out. Aw, that's a bummer, I was really being used a lot.
Right? That's not so happy. Or random. Random says, you know what?
Let's just kick out a random person, and maybe we luck out.
And it turns out that you could run a trace — we talked about how to run traces on this thing — and set up a cache that has random policy, and it actually may do better than all of these.
That's what's fun about these.
Whenever we're still talking about parameters or settings of caches, if we're still talking about it, then there might be still some application where that makes more sense to do it that way.
I mean, think about random. You have to code the ordering, even in software, hardware. You have to code the ordering, don't have to worry about the queue.
You just pick somebody else random, kick him out. And so maybe you have some not too bad performance with random.
So these are still three active — random's certainly less used than LRU, and which LRU is the most common. [LAUGHS] It's kind of least, but it's most common.
But random is still out there. And so random is still a design choice as you're making your own caches. So let's actually look at an example.
This will ground it once we actually work on this. So we have a same two-way set associative cache, 4 byte total, so 4 bytes, very small.
1-byte blocks — since we're talking about bytes now. We're back to these load bytes. But here's the idea, it's two-way. So that means two of those guys — so let's look here.
Here's the picture. So that means two of them — and by the way, all the reds are the even numbers.
If you remember a slide or two ago, it was like red, green, red, green, red, green. And that mapped to two reds up top and two greens.
So it basically says all the even guys are going to be in red and all the odd guys are going to be in green. And what's going to happen, we're going to redraw this.
So these are both the red. All the even guys, all the even memory accesses are going to go in the top set. And all the odd memory accesses are going to go there.
That's the idea, and we'll see what happens. So we're going to do very simple, 0, 2, 0, 1, 4, 0. And by the way, here's the fun thing.
This is a great exam question. I give you a cache and I say, give me the access pattern to make it look really good. Well, just hit the same one all the time, right?
0, 0, 0, 0, 0. I load it in, and now I've got it. But maybe you do something else and random kicks it out.
So if I tell you to construct the access pattern, think about what that access pattern might be make it look really good or really bad. So you can do that.
That's a great question I might ask on an exam. So here's my cache. Remember, the top row is for even memory accesses, and the bottom row is for odd.
So I ask for 0. This cache is cold, stone cold. So I got to bring that in. And I don't care, I'll just bring it into location 0.
And what this 0 is really saying, it's the data at location 0. I'm not bringing literally the 0 in.
This representation, this picture says, bring the memory — it's really MEM of 0 is being put in. Whatever was in MEM of 0, that goes there. I'm just making sure you understand.
I'm not bringing the number 0 in. It's MEM of 0. But I'm showing it as 0 just to make it easy here. I've got to set the LRU bit.
Which is the one that's least recently used? It's the other guy. Because this location 0 is more recently used than location 1.
So even though there's nothing there and the valid bit is turned off there, I'm going set LRU there just to remind you that that's the LRU side. Now I copy that down.
So I'm kind of showing you the time views of that. And now I ask for 2. 2 is also an even number. And 2's not loaded in.
I could check the tags to verify 2 is not there. So I bring 2 — I first check — in parallel, I'm checking the two locations in parallel of 2.
I know it's a miss because location 1 has its valid bit off and location 0 has a different tag. The tag is for the 0, not for 2.
So I am going to — brink. I'm going to bring it in. And now I'm going to set location — this is, by the way, a great example.
If I were copying back and forth from 0 to 2, they could both live there. Both of those memory locations could live there, and I could copy back and forth from 0 to 2.
This is, again, one of the benefits of even a two-way set associative guy.
So because I touched 2 last, I'm going to make over and say, if you have to kick somebody out and set 0, kick out the 0, because 2 is the freshest one and 0 is the most stale, kind of smelly a little bit too.
Let's ask for 0 again. Aw, see? Well, let's flip it again. It's a hit.
Yay. 0 and 2 are both there. That's a hit. We're going to move the LRU a bit over.
And now 2 is the oldest one, because I most recently touched this. Here we go, 1. Well, I have yet to have an odd number, so I haven't even touched that 1 yet.
So let's bring that into a set. Really, that whole set was cold. So let's bring it into location 0 and set our LRU a bit over.
All this is hopefully making sense as we're working with this. Now I've got — just copy that down again. And now the last one — second to last one, I got a 4.
Now, here's an issue. This is exactly why I was keeping track of my LRU bit. I look at both of those locations. Any valid bits off, any blank spots, really?
Nope, they're both valid. All right. Well, boy, I wish I had a way to figure out what a block replacement policy is. I have one.
4 is not in there. So the tags don't match.
And they're both valid, which means that's exactly the case of kicking somebody old out and bringing my new 4 in there — or MEM of 4 in there.
Where do I put it? I put it in the LRU spot. That single bit told me that's the guy you're going to do.
That's the one who's the dustiest, oldest, most stank piece of memory, the most stank data from whatever piece of memory you have.
So bring in MEM of 4 there and set the LRU bit over to the 0. Keep going. Now I'm going to ask for a 0. Yay, the 0 didn't get kicked out.
I mean, there was a little bit of an LRU bit question over there, but 0 is still there. Again, 0 is another hit. So that's awesome.
If you remember, let's go back to the day of the first lecture I ever gave you, the first — like, second lecture where I had a very simple blue, red — I forget the colors.
But it was a 4-byte cache, direct-mapped, 4-byte direct-mapped cache, and it was blue. So 0 would have gone to the 0 spot. 2 goes here. 0 is a hit.
1's a miss. 4 would have been a miss. It was. And because — and now I ask for 0 again.
0 and 4 are both blue. They would have pointed to the same spot. This was better. All it would have been the same.
It would be exactly the same. 0, miss, 2, miss, 0, hit. All that would have been the same so far. 1 miss, 4 miss.
In the olden days, it would have said 0, miss. Because 4 and 0 would have lived in the same blue row.
But because 0 and 4 can both be here together, this is a hit.
So that particular example was the same all up until that last 0, in which I'd had direct-mapped, the 0 would have been a miss.
Here, it's a hit because 0 and 4 — both blew in the first picture that I showed you — can both coexist happily.
And I could very happily copy between 0 and 4 in this guy. I couldn't have in a direct-mapped cache. That's kind of the example we got there. And now I set the LRU bit.
Now, what's really wonderful is there's a simulator. Whoo. I didn't write it. Someone at UMass wrote this.
Koren, I believe, at UMass wrote this amazing — Professor Koren, I'm sure — I should give credit.
I don't actually know who wrote this, but I know the user ID is Koren — wrote this wonderful simulator. And you can set the parameters of your cache.
And I just adjusted the parameters to be exactly this problem. And then you can go in and set up the sequence, the request. Show me the list of requests, memory requests.
So I put in 0, 2, 0, 1, 4, 0. And what this does is — look what it does. It color-codes them as compulsory miss, which means — we talked about them before.
You got to take the loss anyway. It's cold. You got to take that miss anyway. Capacity miss, that means if you only had more space, you wouldn't have had that issue.
And conflict misses say, well, that would be nice, but two guys are at the same spot. Watch this. Blue, 0 — the first 0, that was a compulsory miss.
Then the next one, 2 was a compulsory miss. 0 was a hit in this guy. You saw that. That 0 was a hit.
1 was a compulsory miss. 4 — again, 4 was a conflict miss in this particular case. And I kicked out the 2. There wasn't room to hold 0, 2, and 4 in this cache.
That's a conflict miss. So kick out 2. And this even shows — look — kicked out the 2. And then bring back the 0, and 0 is a hit again.
So it even color-codes in these categories what this is. It'll tell you, I've got six queries, four of them were misses.
So it tells you the miss ratio — the hit-miss rate, sorry, the hit rate, really nice simulator. So you can practice and make sure that you understand this.
And you can say, here's a particular cache parameter. Can you ever get to 80% misses? Can you play with that? Can you predict what you'll get?
How about this? I can imagine I give you this setup. I give you this sequence, and I say, fill in this table.
You should be able to run the traces in your head or on paper, like I just did, and get those values. So I love this cache simulator.
Please feel free to help you learn what caches are and how they work. We'll see you at the next lecture.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.