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ả.
Hey, welcome back. Now, let's work on a problem. Let's work on an actual problem where we learn about direct-mapped caches with some actual numbers and some actual problems.
So here we go. I got 8 bytes of data in a direct-mapped cache with 2-byte blocks, okay. Ooh, 8 bytes of data, overall area. Other problems, we might have seen this before there.
8 bytes of my total guy, 2-byte blocks. Okay, 2 bytes across. I got that. Okay, now we're going to ask you some questions?
How big is the tag, index and offset fields if we're doing a 32-bit architecture? Okay, so that's usually the setup. So let's figure out the offset first. Let's figure out the offset first.
Well, the offset is the number of total bits I need to — if I'm looking at how am I dividing up that set of bits, here's 32-bit address.
Some of those 32 bits has got to be the T, the I and the O. So let's do the O first.
Well, the O tells me which column I'm in, that's the first thing we do. So how many columns do I have?
How many bytes — it's always in bytes — how many bytes do I have in a block? I figured it out. It says it. It says 2-byte blocks.
Well, so 2 to the what? 2 to the number of bits is that total number of bytes in that block. Well, 2 to the blank is 2, so blank is 1.
So I need 1 bit for my — and that's what we saw before, 1 bit to determine my offset. What's my index? Well, it's the same idea.
I just did this before, kind of when I was talking about the larger cache problem. Here we go. Total cache is, what's the area? Well, I told you 8, 2 to the 3.
What's a block? A block is 2 to the 1 bytes. 2 to the 3 over 2 to the 1 is 3 minus 2 is 1, therefore, 2 to the 2 blocks per cache.
Therefore, I need 2 bits to specify that number of blocks. So then I go to my tag. Tag is everybody else. That basically said 3 bits are needed to access a cache.
By the way, I could have told you the tag size already, because you told me the cache size. You told me the cache has 8 bytes.
That's 3 bits to access 8 bytes, so therefore, 3 can be borrowed for whatever.
Even if I'm confused — some of them are index, some of them are offset, I don't know which is which — I do know that three of them are to tell me about the — place it inside the cache.
Well, if three are for there, The rest of them, 29, are my tag. And that's it.
So I need a 29-bit tag and 3 bits to tell me which row the left 2 bits of that. The left 2 bits are the index.
That tells me what row, and 1 bit is my offset, which is what column. That's it. Again, why not the first full 32 bits for the tag? Well, why waste?
Those rightmost 3 bits are never used. They're always going to be redundant, so we don't want to have them in that system. So let's do this.
Now, a big picture, this is a really big picture idea. Taking a computer without a cache and then adding a cache changes the process. It doesn't change the value.
It doesn't change the program. I told you, you should take the same code with or without cache. It does does the same thing.
Now, it may be faster if you knew that they were cached there, but the same thing should happen effectively. So I want to load a word. I got some memory.
t1 is a pointer into memory. I want to load that in store it into t0. I clobber whatever t0 was and put that memory in there. And let's say t1 contains 1022.
1022 is the pointer. And what's in that address? 99. So what happens?
Let's do the steps without a cache. These are the days without a cache, back in the days, the simple halcyon days before caches. Processor issues an address, 1022, to memory.
It says, I want to get — what is lw t0, 0(t1) where t1 is 1022? It says, look, can you please go to memory at address 1022 and get something there?
Yeah, sure, I can get you that. How much are you asking for? Oh, it's lw. It's a word.
All right, please, I'll carry it back for you. No problem. Ch, ch, ch, ch, ch, ch. Okay.
Here is 99. The memory reads it, returns 99. Remember, he sends it back to the processor, and the processor then loads that into the register.
And by the way, at this point, you know how the whole thing works.
You know how the data — I could ask you for a datapath of what lights up and how it actually does it.
And you could even show me the control lines to make it work. At this stage in the course, you can explain everything about how a load word works.
It's really very powerful to understand how that whole thing works to run on a RISC-V machine. This lights up. This goes there, the index, the offset. There's a 0 immediate there.
That 0 gets added to that memory location, doesn't change. It's still 1022. So that's an immediate, had to be extended. All those things how to do.
And you know how to route it. You know what turns on. You know what muxes turn on, what the signal lines that go to the mux.
It's really very cool, at this point, your understanding of the whole system, very powerful. I hope you walked a little bit taller now that you understand how that works.
But again, this is without a cache. What happens with a cache? What's the algorithm with a cache? Again, I got my same load word, and t1 contains the same thing.
Well, with the cache, it's similar to what a hash function does. It says, well, I could save time if it's in my cache than going to memory.
So the first thing I do is I have to see if it has a copy. Do you have a copy of that data at — is that 99 somehow copied in?
Because remember, I'm only reading for now. I'm never writing. I'm only reading for now. Okay, so is that 99 somewhere in my cache?
So if it is, I say it's a hit. We got it, woo! And I return that 99. I never had to go to Sacramento.
Sacramento was really far away. Is it in my room? Is that 99 somewhere in my room? Well, I got to check it if it is.
If not, oh, man, well, then I got to go to memory. And then here's what I have to do. Here's the step 4. I have to — memory reads 99 to the address.
Memory sends it back to the cache. So the cache is in there. When it wasn't there, the cache has to still store it for the next time.
So it doesn't — well, I don't have it. Sorry, I'm going to sleep. Don't go to sleep. You've got to store it for the next time.
That's the whole purpose of the cache is if you can't have it the first time, you'll have it for the next time I ask for it.
It replaces the spot, that word, with 99, and then it sends the 99 back to it. So it still has to do with storage and update itself, and then it sends it back.
And from the processor's point of view, it didn't know. It just asked for it. And if it was there, it was a much faster return value.
If it's not, magic things happen behind the scenes as it moves to the right place and updates, updates, updates. And then, finally, I just get my 99, and I work with it.
And it sets it to t0. So in some sense, it's the same thing from the processor's point of view. Abstractly, I don't know what happened below the hood.
And now the cache is moving around and putting it here and buh, buh, buh, and doing its thing so that it does the right thing.
This is the last slide on this particular mini-lecture, but I wanted to talk more about how to think about it.
I created this because I realized as I was working with many students in office hours, they weren't visualizing it right. And I'm the visual guy. I got my PhD in graphics.
So pictures always helped me learn. And maybe others are like that. So I wanted to show you how to solve cache problems in general.
We always, as I mentioned before, draw our memory the same width as the cache, always the same.
However many — whatever that block size is of my cache, draw your memory the same size, the width of it, at least.
And now, as I have my T, I, and O, and I have a value, all zeros. Where is all zeros in cache? Well, I always start in the upper right.
There it is. Where is it in memory? Same spot. These are like mirrors.
It's almost like a mirror.
There's this wonderful Marx brothers where they're kind of like — the two brothers are pretending to be — he walks in, and he thinks he's looking at a mirror, but it's actually his brother.
And his brother goes like this. Maybe if I can grab a copy, I'll show you this over here. But does the hand and the hand, and it's a mirror.
That's what's happening. As I'm asking for the memory, the cache is exactly the same spot. So wherever you see this arrow pointing to memory, it's literally the same spot in that cache.
Okay? Next one, a mix of interest. Uh-oh. I just increment that guy.
I increment my binary number by 1, which means all I'm going to do is change my offset. I move my offset by 1, what am I doing? I just move over by 1.
It's the next one over. So it's like I'm starting from the top right and read across to the left. I'm just increasing the bytes that I'm going to ask for.
As I'm asking for my address to change by 1, I'm getting the next byte, then the next byte, then the next byte. And for now, we're just doing load bytes.
We're just moving by 1. Okay? The next interesting thing, the next significant number is when it gets to all 1's.
I want you to draw — think, before I give you the answer, where is that all — where is that thing?
If I say all 000's, all 0's in my tag, all 0's in my index, but all 1's in my offset, where is that in the picture of memory?
Circle it. Circle the box — actually, I'm going to make it an exam question. Circle the box where it is in memory in there. I'll tell you where it is.
It means I got to the last spot before I wrapped into the next index. So it is in the top left. Okay? Got that?
So as I read across, offset continues to move across until I get to all 1's, then it's the top left. Then what happens? Then it wraps to make the index up by 1.
And where is that? It's the next row. It's still in cache 0. This is tag 0, or cache number 0.
And so, again, that's here. That's the next row down. So start to think about and kind of visualize where this thing is. Now, the next thing is, what happens when that maxes out?
When that maxes out and offset maxes out, where am I? You probably can guess where I'm going to be. You're exactly right. It is in the bottom left of the memory.
The bottom left of your cache and your bottom left of memory, same exact idea. I hope this is helpful, by the way. When that wraps, what happens next?
Well, as you might imagine, I now go back to the top right of my cache, but now the tag has changed.
Now I'm in the next cache. The cache went bloop. And because this is the next box, this is the next box.
This tells me my cache number, so my tag is now a 1 there. So 1 in all 0's is in the top right of the next cache size down in memory.
Or if I'm a cache, I just go back to the top right. Because I basically go across, go across, go zig-zag, and then I just jump back up there.
That's what happens. So I've jumped back up there when I had all 0's. Because, again, in this, I only am looking at these to tell me where I am in here.
And I'm using this one to tell me which one of these guys I go to. That's all this is. It really isn't that bad. The next thing that's most important is all 1's.
Whoa, that's the biggest memory location of all time. Where is it? You're exactly right. It's the bottom left of here.
And because this maps to that, it'd be the bottom left of that cache with tag number, whatever the maximum value is. That's it. That's the big idea of how to solve cache problems.
Take your T, I, and O, Theoden. Gracias, Theoden. Thanks, Theoden, for teaching me this.
The idea is you are going to be able to — I could just tell by — I give you some bits, and they look complicated. No, make your columns.
There's my T, there's my I, there's my O. If you're really fancy, have three different colors, red, green, and blue, like I use here.
And then start to make use of this — I don't know, this kind of visual way to think about this as you start to have problems.
And as I start to have some — so here's a piece of code I might give you. What's happening in this loop? Oh, maybe it's just — look at this.
Maybe the loop is just — let me go back. Maybe this loop is just in the cache, maybe just reading this. Oh, okay. So I can think about that.
That means it's really here. Maybe this keeps going. It just goes on here, right? On the right, okay.
I don't know what my stride is. Maybe I read this memory address and then jump another. If it's memory address, not the neighbor. If I'm reading by 1's, I'm reading across, I'm reading across.
But what if I jump by some stride? I read this memory, and then I jump to the next one. How big is your stride? Well, what if your stride is exactly a block size?
Well, that means I start someplace. And I'm going down here, because I'm jumping by a block. I jump by a whole block, which means I go to the next block.
What if my stride is the cache size? Whatever memory address I have, I jump by cache — what happens if it's not even on the edge? Here's my first access here.
And I stride by my cache size. What's your next location? There it is. Because I moved by a cache size.
And by the way, if that's the first one, where's the second one? Same spot. Because if I jump by the cache size, it doesn't move in the cache, right?
This is just a copy of what that looks like.
That's not to say the whole thing is a copy of that whole thing, but I'm just saying the location in the cache is parallel to where it is in that box moved over.
So I can stride, I can make a memory access and then stride by some amount. And if I stride by a byte, I move across the top.
If I stride by a block size, I move down wherever I start with. And wherever I start with, I'm moving down that same row.
If I stride by a cache size wherever I start with, and I'm jumping to the next guy the same spot, okay? So these are common strides. We might have an example.
What if I stride by a little less than a block? Oh, let's play with that. Here we go, a little less than a block. Then I'm here.
A little less than a block means I'm actually going to go this way, a little less than a block. [GASPS] What if it's a little more than a block?
Well, then I'm going to go this way, okay? What if I'm going what if I'm not exactly a cache but a little more than a cache? Well, what happens?
Here and I move over a little bit, and I move over a little bit. What if I'm a little less than a cache size?
I'm here in the same spot but a little in here. [GASPS] What if I'm not just a little less than a cache is?
What if I'm a whole block size less than a cache size? It's starting to hurt. Here's my memory, exactly one block size less than a cache size.
If I start with this M, that means the next one is up one and up one. It means I'm going up on — I'm kind of not completely getting there.
What if my stride is — and by the way, play this slow and rewind this to make sure you understand this. What if my stride is cache size plus a block?
Well, I started in this M. And the next time would be the same M but down one, and the next M but down two. Okay?
So think about as we give you some code and maybe have a stride, as I'm assessing not just continuous region of memory, but a stride and then another one and another one, how you're moving through this space to understand, as you're solving these problems, how many hits do you get?
How many times do you get it? How many times did you miss it? All those things in terms of performance of a problem. Okay.
Phew. I hope this is useful. I really visually always go here. You give me any problem.
I say, excuse me. Give me time. Hold on. I draw my picture.
Okay, now let me read the problem. And I label it. I draw my picture, I draw my this. And then I say, okay, what's the width of the cache?
What's the block size? That's the width of both cache and memory, because I draw them the same. And now I start — here's my T. I draw my T's out, my TIO.
And I draw them out. And I understand that. And then blah and blah. That's I do it.
So basically, just sit down, take your time on these problems, and draw the pictures, and you will get them right. Okay? 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.