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ả.
DAN GARCIA
And welcome back. Halfway point, let's do this.
Let's see a real example where we talk about a direct mapped cache and poke at it with requests and have some hits and some misses and misses with block replacement and understand the valid bit and actually put it all together with an example.
It often doesn't ground itself until this lecture. Hope with this lecture — feel free to and watch this at half speed. You'll get this. So this is an example of a direct mapped cache.
Let's do this. Okay. Boy. Guess what?
Same problem I had before, 16 kibibytes of data. That was the last lecture, we ended with that picture. 4 word blocks, again, to see the same thing.
We're going to work out the height with an area, we did this already. We already worked out those bits in the last problem.
And we're going to read four addresses, 14 in hex, 14, 1C, 34, and 8014. What happens? That's what I'm going to do. And now you'll see how to do every single thing.
We'll break it all up. We'll do this for you. And here's the memory values.
By the way, just to let you know, we're going to just put some values — whatever a is — these are word-wide, okay? These are words here we're talking about.
So a is some value of words. This doesn't mean a, the hex value. That lowercase a means some value that we're going to label a. And again, a through d is the lower side.
And then in the 30s here, in terms of the address, it's e through h. And in the 80, kind of 8-thousandy range, it's going to be i, j, k, and l.
Okay? You're going to see why we choose those values in a second. Here we go. Here's my four values, 14, 34, 1C, 8014.
Write out the 32 bits. Draw your columns. Where's your T? Where's your I?
Where's your O? How much is it? We talked about it before. There's 14 bits for my cache.
Four bits are my offset. That's 1 of 16 different bytes. 10 bits for my index, that's one of 1,024 different rows, different blocks.
And here's my 10. Here's my 4. Then how many is here in my tag? Well, if it's 32-bit wide, RISC-V 32, this is 14, that must be an 18-bit tag.
So we kind of know that from before. And by the way, notice, by the way, here, look. The tags are all 0's. That's a 0.
That's a 2. So let's remember that for the future. If the range is in the 80's, my tags are not going to be 0. The other guys are on the low side of memory.
This is on the higher side of memory. My indices are — look, okay, that's a row. That's row 1. That's row 3.
So already kind of seeing this, and we'll be poking at this in row 1 and row 3. And these are the different columns I'm getting. That's a 4.
That's a 12. That's a 4. Okay? That's a 4.
By the way, what do I know about this? All these are 0's, I'm probably reading words here.
If I'm reading words — if you remember the picture I showed you a second ago, I think I — watch. These were word-wise. This was 4 bytes wide.
So if I'm only reading load words, you know I'm going to be word-aligned in my memory accesses, which is why all these guys are 0's. That's pretty cool, okay?
So all this starts to make sense when you play it off with it. Here's my picture, beautiful. I need a valid bit. What do I set my valid bit for?
Yes, they're all 0. Temperature, here we go. What's my temperature of my cache? Freezing cold, empty, nothing there.
Valid bit's telling me nobody's ever visited this guy before. It's literally got the new cache smell. I just cracked it open — you ever open, like a tennis — I have one here.
I'm pulling this out. You ever open this guy? You open [INAUDIBLE]. [SNIFFS] Get that new tennis ball smell?
Okay, that's a little weird, but I usually do that when I open my tennis ball bags. I got my new cache smell here. Okay?
Having some fun, I'm just trying to make this fun for you guys. All right. Let's do it. We got four reads to do.
Remember, no writes yet. We're just doing reads, and it's simple. Direct mapped is the simplest kind of cache.
Still, there's complexity to it, but this is the simplest kind of cache before we add more layers to complexity. I'm reading memory address 14. I break it up.
What do I got? I got a 0, I got a 1, I got a 4.
And by the way, just so you know, because I have 4 bits here in my offset, this hexadecimal nibble is my offset instantly.
And because this is 10 — I think we said 10 bits, right, 1,000 rows? Well, 10 bits is kind of like — well, it's like this and then half of that.
So just in the future, I can almost read directly what my index is by reading kind of the 10 bits here, which are the lower two hex digits — nibbles, lower two hex nibbles, and then half of the other ones.
So just give you a little taste of that. Okay. So what happens? I first got to figure out what row I'm in.
This is why we always start with i. I think I mentioned that last lecture or two lectures ago. We start with my i. What row am I in?
I look at my index. I'm in row 1. Before I tell you what's going to happen, see if you can predict what the algorithm should be doing. What does it do next?
Can you figure it out? You're right. I look at the valid bit. We got to check that first.
This would be a great question on an exam. I like that. Is the next thing you do to look at the index the tag? No.
If the valid bit's wrong — if the valid bit's not wrong, 0, that tag could be garbage and might actually match my tag, taking me down a path of code that I wouldn't be in.
That's the wrong thing to do. Check your tag first. Check your tag. Let's go back.
Check your valid bit first. I often do this. Check your valid bit first. When it's 0, it's not valid.
So cache miss. Had to do it, just had to do this. We're going to call it — we're going to learn that this is called a compulsory miss.
I didn't want to teach that word yet. I'll teach that word in a moment. But it's like, I got to take the miss.
When I was a 0 valid bit, I got nothing to do but a miss. There's no way I can have a hit there. So I load the data in.
Well, how much — when you're going to Sacramento, you might as well get some more stuff. Folks, what kind of locality we're working with here, temporal or spatial?
Both. It's a cache. I'm remembering the guy just visited, that's the temporal part.
And I didn't just load a byte, I loaded the byte and a word — actually, another little byte and its neighbors, a word, and their neighbors, three more words.
So there is some spatial locality I'm trying to exploit here with this wider block size, okay? I set my — notice this. I've got to set my valid bit.
Don't forget to do that.
By the way, if you're implementing a cache ever in hardware and you forget to set your valid bit, you'll never have any bits, because it'll always think it's cold when it's actually warming up.
So make sure you set your valid bit. And what's last? What's the next thing you do? You got to return something.
It's a load word. Who are you returning? Well, this value of 4 says, look up here and grab the b. And I return b.
Okay? These are bytes 0 through 3, or that a encompasses this whole thing. I always draw these dotted lines. This is 4 bytes in here or a word.
If I'm loading a word, I'm going to load either this word or that word. It's got to be word-aligned, so I'm loading b.
Because in a way, I kind of ignore those bits because I'm learning words. I ignore those bits. That tells me the number starting from 0 of the word I'm grabbing.
If it's all 0's, it's a. If it's 01, it's b. So in a way, you can actually look at this, and if I'm loading words, I ignore those lower bits.
Just FYI. So I return b. So I got a cache miss, loaded the block up, and returned a b. That's the first request.
I got three more. Let's do it. Read 1C. Okay.
What do I do? Again, this is going to seem very boring once you've done a couple of these, but for now, let's go slowly. Well, divide 1C up into the bits.
What's my tag? 0. What's my index? 1.
What's my offset? 12. Okay, so think about that as we move forward here. I take the index.
I take the little orange label, I say, go to my index. Always the I first. I, T, O is actually our process. Check my index — actually, I, V, T, O, really.
Ooh, IVTO is the new mnemonic. I need a new mnemonic for IVTO. Okay, got that row, V for valid. Then I tag.
Hey, the tag matches. This means I read this block — I read somebody from this block recently. And nobody else, no other color did I read since that one.
And I don't know how long it's been there. This might be really dusty and have cobwebs. But I haven't read anybody else since I read that one. So that's pretty cool.
Tag matches, the next thing, as you know, I, V, T, the T's there, and the O. Check your offset. Offset go grab c and go grab the last word in that block.
And there's your d, return your d. So we returned a b and a d. We're doing pretty well. We had one miss, and we got a hit.
I love the caches. Already, we're saving our time. I didn't have to go to Sacramento. Because when you went to Sacramento, you brought your neighbors.
I brought a, b, c, d. You only wanted b last time. But I brought a, b, c, d. Guess what?
Now I wanted d. I love this. This is just great. All right, here we go.
This is going to be trouble now. 34, okay, let's try it. So first thing, divide the bits up. And I already can see there's some problem.
My index is a 3. I've never visited 3 before. So that's the same situation. We can go faster.
I've never seen this thing before, it's not valid. I load no valid data.
I load the guy in, load the cache block, set valid, look at my offset, return my f, and I move on.
So we've kind of seen that case before when we did the first one. Here we go. Get excited. 8014, here we go.
Let's try it. Okay. Uh-oh, 8014 key, that looks like a — [GASPS] this looks like a whole different cache number. I can tell that because the tag is different.
The tag is my cache number. So we first go check my index, IVTO. Index is the second row or index number 1. Has my valid — wait, wait.
Check data's valid. So that's the second part, V. T, check my tags. Tags don't match. And these are only reads for now.
So this is a copy, and because I'm only reading, never writing, I can just throw this away. That's the key thing.
We're going to get this more — when I reveal the hood, reveal the simplicity — we're in our little rubber room for now — once I make these writes, well, what if I've had this write and it's not the same as memory?
What do I do there? Can I throw it — I can't throw it away because the most recent data's in the cache. All those complexities, we're not even talking about now.
So for now, I just throw that away. I got to throw that away. It's a cache miss, block replacement.
I got to load in whatever that block is, whatever those 16 bits were, those four words from memory, and replace a, b, c, d — if you remember that before, it is i, j, k, l.
I've got an offset. And again, update the tag too. Don't forget. By the way, you got to make sure you update the tag.
Don't just update the valid. Make sure to update the tag. If there's a new tag, put your new tag there. Otherwise, they'll all be wrong.
That would be really bad if you didn't update your tag. It would think it's the wrong place, and that would be really inconsistent. And now go to my offset.
IVTO, what's the last guy? O. Offset is our 4. Grab my j, return j. That's not bad.
That is not bad for things. Okay, here we go. Now, okay, this is one of those cases, almost like a clicker Peer Instruction question.
What if I gave you — and my values could be a, b, c, d up to j, k, l, before, 30. Okay? And I'm going to ask you, what if you read a 1C?
So I really encourage you very strongly to pause it right now, pause the video, try to do a read of 30, of address at 30, and read at address 1C.
And we'll come back in a second.
And welcome back. See, I paused, pretended like I was — I paused. Here we go. All right, 30.
We can do it together. Here we go. Watch. I'm not even going to — I'm going to stay on this page.
I'm not even going to need any help. There's nothing on this page. I'm doing it [INAUDIBLE]. Okay, Dan said, IVTO, IVTO.
I, there's my 3. So I go here, my 3. V, valid? Yes.
T, that's a 0. Is that the same as that one? Yes. O. O, I think I return e.
I'm feeling pretty good. So this guy was return e. Okay? And I don't change anything.
I actually don't update at all. I just return e. Cache hit, best possible case. 1C, divide it up, IVTO.
Index, 1. Go back here. So we go to my 1. V, valid.
Yep, valid. Tag, 0. Oh, man. What's the tag there?
Are they the same? That's not so good, not the same. So cache miss, block replacement. I got to swap it out.
Do you remember what was in that first guy? I believe it was a, b, c, d. So then I go here. And by the way, I think I asked this before.
Maybe I did, I don't know. I want to ask — and I think it's going to be there.
This is going to be — cross it off, a, cross it off, b, cross it off, c, cross it off, d. Cross this off, write the 0 there.
And you wanted the 12. And that is — I'm counting by this guy. You wanted the 0, 1, 2, 3, the last one. And I think you return a d.
Let's see how we did. So what did I say? I think we returned an e and a d. I think that's what we did.
Let's try it. Okay, well we get — ay. I return an e, return a d. There's my values, e and d.
Huh, with the thing, isn't that perfect? Isn't it? That's it. That's not too hard.
If only there were a cache simulator that existed out there in the real world I could just play with and explore. Oh, I wish.
It's just too bad that no one has written a simulator of a cache. Well, I guess one doesn't exist out there. It's just too bad that we don't have a cache simulator.
Oh, well. We'll end a sad note. No cache simulator out there — as far as I know. See you in 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.