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ả.
INSTRUCTOR
Hey, welcome back. Now we're going to reveal some layers of the onion. We're living in a rubber room for a while.
Now we're going to realize that it's a little sharper, and there's some more details behind this. So let's think about how to handle writes. Up to now, we've only been reading.
We were reading words more than just bytes. In the beginning, we're just reading bytes. Now we're reading words. Now about writes?
What happens there? What about block sizes? And what happens when we have misses? Let's talk about all those elements near and now and get some more details.
So this is a beautiful picture of a multiword-block.
So it's a block that's more than just one word. Direct-mapped cache. I've got here — let's actually make four words a block.
So block size is going to be, like before, four words of block. The cache size is going to be 4K words. This is the same as before. We saw this exact speech before.
4K words or 16K bytes. All that's the same. We saw the way we can think about our T, I, and O and divide them up. And we saw the picture here in the cache.
And the data is on the right side. You've got a valid and a tag. And I've got 1,024 different rows. So here is what happens.
We start by looking at the index. Index tells which row I'm in. The row first. I check my valid, and I check my tag.
As the tag comes out of it, my valid bit comes out of there. So when I am valid, and when my tag equal is equal, I grab that particular word out of this.
And let's actually look at some details here. As I look at this, here's what's actually quite interesting. I only have a hit — when do I have a hit?
You have a hit when — you can think of the logic already — when the valid bit is on — there's a 1 there — and the tag matches.
So I take my 18 bits of the tag compared with the 18 bits of the tag that's stored in that row and that block. Well, this is the block, but in that row.
And I do a comparison. There's an equal sign there. So that means they just compare. If they're the same, there's a 1 at the output of that box.
If they're not the same, that's a 0. And only when I am that with the valid bit, so only when it's valid and they're equal do I have a hit.
So that's already interesting. Each of the data words is going to be fed into a MUX. Here's my MUX. Now, what am I selecting from?
I'm selecting from which particular one I wanted. Remember we mentioned it before. These are all words I'm grabbing. I ignore these last two bits.
Those two bits are the byte offset. That's where I am. But I'm reading only word to line values.
So every single request ever, those two are 0s because I'm only reading words, and words all my words are going to be word aligned. So that byte offset I ignore.
These are all 0s. 0 and 0. That's what they are. These two bits are the bits which are my block offset.
Taken together, those four bits are my byte offset. But I'm reading words. And if I'm word aligned, I'm only ever having it be those four guys.
If I look at that nibble describing this thing, that nibble is either 0, 4, 8, or C, which means I want that byte, that by word, that byte 8, or C. Each 0, 4, 8, C had two bits in the lower side at our 0s.
So I actually only use the upper bits. And the upper two bits are 0, 1, 2, 3. What's the upper two bits of C? 1,1.
Upper two bits of eight? 1,0. What's the upper two bits of 4? 0,1.
Upper two bits to 0? 0. So this number is telling me which of those words is the MUX going to be sending out. And the MUX sends the data out, and I'm done.
That's a beautiful picture. So this picture is actually describing what's happening in hardware. And these are all happening at the same time. It's not like, well, do this first.
Computer scientists always think, well, sequentially, first, check this. And then you've got to go and check the tag because if you're going into software, you'll be doing it in steps.
Not so in hardware, folks. All these things are happening at the same time. Same time, same time, same time, same time, all this coming out here. Okay?
And by the way, if this is not a hit, you ignore what this is. I don't care what data is coming on those lines.
I'm not going to pay attention to it because it's the wrong one. Either it's not valid, or the tags don't match. So I'm going to ignore my data.
So all those things happen at the same time. But at the end of the day, I check this hit first. And if that's good, then I'll use the data.
Otherwise, I'll ignore that data. Now, I ask you what kind of locality are we taking advantage of here? And I'll just pause, as you think to yourself, before I give the answer.
The answer is both, both temporal locality and spatial locality. Probably the person who wrote this slide — I inherited the slide deck from other 61C instructors.
Probably they wanted you to say spatial locality because your block size is more than just one byte or one word.
So they want you to say spatial locality because they're talking about the block size. But it's a cache. All caches have temporal locality, unless they don't remember the most recent guys.
But this one cache does, and so they do that. So it's taking advantage of both temporal and spatial locality. We haven't at all though talked about writes. Let's just be honest.
Let's be clear. Writes are part of the world. I do some SWs, SBs, SHs as well. So what do we do on writes?
Okay, I have some data. I'm going to store it in the cache. The cache may have different data than I have I'm going to be writing to that area.
As I'm clobbering the cache, as I'm writing something to memory, I'm writing to memory, I'm going to write into the cache too so that it stores that as well.
Now, I could either just treat them all as always consistent. And that's the easier case. The much easier case is what's called a write-through.
So I'm taking my data from the processor, and I'm pushing it out to the cache, update the cache. And you know what? Go to Sacramento anyway. Push it all the way through to Sacramento.
Done. Now my life is so much easier. Thank you so much for doing it write-through because they're always the same.
I don't have to worry about any of the details of what happens when they're inconsistent or in a way corrupted. And maybe corruption is part of the design.
That's what the second one is about. So write-back says if you're just reading and writing to a value, why don't you just stay in the cache? I'm going to read from an array value.
And then I get it. That's fine. Or maybe it wasn't loaded, so I load it up. Now it's there.
And now same array value, same array address. I'm going to write a different value. Well, do I have to go to Sacramento? I just I just came from Sacramento.
Why couldn't you have them being consistent as the design? Because watch. I write it. And then the next line, I read it again.
Hey, wait. If I just read it again, I write a different value. I read it again, a different value. Why do I ever need it to tell memory?
I feel like I can live with my cache. And I mentioned this over and over. It's always a local copy.
But in this world of write-back, I can save a ton of trips to Sacramento. I can save a ton of trips to Sacramento if I just don't have to update Sacramento all the time.
I'll let you know whenever I remove it from that. So we'll talk about that. What do I need to actually tell Sacramento? What do I need to actually write it to memory?
But I get a big performance win if I'm reading and writing in the same spot to not have to go to Sacramento with every write.
If you say write-through, I'm going to Sacramento in memory every single time. But if I'm just going to read, write, read, write of the same location, boy, write-back as way faster than write-through.
Are you kidding me? It's 1,000 cycles or more to go to Sacramento every time I'm doing that write. So if I can save that, I love it. So people really appreciate write-backs.
But you end up having more complexity. What does this slide say? [CLEARS THROAT] Memory, when it's inconsistent — there's a word for it. We call it being stale.
Stale is like stale bread. It's smelly and old and maybe moldy. So it means that memory was old. Stale means it's got older.
The most recent copy, the freshest copy, the single source is almost — there's no more single source of truth, by the way. But the answer is in the cache, not in memory.
Memory is no longer the reverential place where stuff is. It's in the cache. So there's a little bit of a way to have to think about that. Memory is no longer the last word.
Cache is the last word actually if it's ever stale. It also means I need to tell the system, you know what?
If I'm going to go with write-back, I need to let the system know that this is now inconsistent. I won't say corrupted because corrupt usually means a negative thing.
I'm designing this into this. So write-back isn't corrupted. It's that when I let memory be stale, I got to let it know that way that really it's the cache that has the referential value.
And that means I need to add another bit.
I had a bit for valid to say when I initialize the cache, I need to know whether that tag is — I can trust it or not. So I had a valid bit.
We do the same thing here. It's similar. I have a bit called the dirty bit.
And that dirty bit on a write-back cache says that cache block is not the same as the block in the — whatever that happens to be in the same place, align that, the same block there in memory, that's not the same.
The cache has a different value even if, by the way, when I write it, it happens to write the same value that was there before. That's a little bit of a subtlety.
What if it's all 0s, and I happen to write all 0s? Well, I'm doing a write in this write-back.
It doesn't check them all and then say, well, if they're the same, don't let — nope. Even though I'm writing the same value, it'll still make it stale.
It'll still say, nope, dirty bit's set high. This guy is stale even though they're actually the same value. So there's a little bit of a subtlety. Maybe you can optimize it in read.
Who wants to do that? Because remember, often, block sizes are really wide. Who wants to spend time cycling through comparing the old guy with the new guy I'm going to write?
And when they're the same, you often write a change. And so you don't do that.
So the point is, even if I'm writing the same block as was in memory, I still say memory is now stale, and dirty bit for that block is now 1.
They're inconsistent. And when the block is replaced, that's when you need to revert to memory. So eventually, memory gets updated, but only when the block has replaced it.
Or it's also replaced if — you don't know about the operating system yet. When the operating system has an input output activity, it often flushes the cache.
And when you flush the cache, you have to then correct it, put back in memory.
Because when you flush the cache, you don't want too — remember, cache is now the truth, and you don't want to just throw it away when you flush the cache.
If cache is only a copy, I can just erase it all. How do you erase the cache? [ROLLS TONGUE] Set them all invalid.
But if some of them had the dirty bit set high, you'd better put those back to Sacramento to make sure that you update memory before I set the dirty bit and erase the cache, if you will.
Remember, you never go out — [ROLLS TONGUE] you never do that. You just set the dirty bit to erase the cache.
So when you flush it or erase the cache, you set the valid bit to 0. But all the dirty bits that were 1, you've got to make sure you write those back to Sacramento.
Okay? And then you can play with the conversation and performance trade offs. When does one win? When does the other win?
Can you come up with a scenario where each one of them looks bad? If you can — by the way, we can. And you should think about that.
That's why we don't just say, here's how we do it. By the way, remember how we talked about direct map cache? And I even alluded to how would you find which block it was.
Maybe you use a linear search. I was just making stuff up. Nobody does that. We just immediately go there.
It's a constant time to figure out what exactly what row I have to go to by looking at the bits for my index. We know how to do that now.
There's no log search for these things. So in the same way, because I'm still talking about two of these guys, that must mean that there's some scenario where this is better.
Some performance from some usage, some characteristics of a cache with the usage pattern that makes write-through be better.
And might be some characteristic with usage pattern that makes write-back be better, which is the decision of why we still talk about two ways of doing things so that there isn't a clear winner and we just say, no, it's lost to history.
1's compliment lost to 2's compliment. I'm sorry, 1's compliment. You lost. 2's complement is better.
I don't want to two 0s. So 1's complement is a kind of a historical footnote. But both write-through and write-back aren't historical footnotes.
These are both reasonable designs in a particular cache for a particular system. So thinking about that. Is it still a conversation for that particular instance? By the way, caches aren't always about memory hierarchy.
You have caches for the web page. I got a web page cache. Cache is in many — I have a cache for my recents of my phone call list.
So there are caches in all these places.
And any one of those situations, the design might be, well, this one should be write-through, that one should be write-back depending on how long was it to Sacramento.
Maybe not too long, all those kind Maybe the complexity means that it is longer, but it's not that big a pain, so I'll do that because the code to write the write-back is whatever, harder.
Okay? Now let's talk about block sizes. We started by starting — the first picture of a cache I had a 1 by block size. The width was 1.
And I said, well, make it 2. And then we actually now have seen 16 byte wide blocks. What are the benefits of that? Well, the benefits are spatial locality.
Screaming for spatial locality. If you're going to Sacramento, if you go to the refrigerator, get me some food, okay? I came back. Here.
Here's this, and here's that. If you go in there anyway, once you're going to the long distance path, while you're there, grab some stuff and then bring more of it back.
So you can stream it back as you're coming back with some data.
So this is very applicable for stored program concept model because we often have sequential arrays, and you typically sweep through an array.
So if I'm going to go there, I'm going to go and grab the whole block of that. And that's going to be some fraction of the array.
And now as I'm walking through, it's there. It's a miss, but then the rest of it are hits. That's the idea of a larger block size. What's the drawback?
We talked a little bit before — two slides ago I believe, two lectures ago — on hit rate, miss rate, miss penalty.
When you have a miss, how much pain do you have to suffer to go to Sacramento or go even farther for that? So a larger block size means your miss penalty goes up.
It means you can reasonably — rather than go and grab one byte, I got to grab — really? I got to go to Sacramento and grab 16 bytes?
What if I'm literally — how about this — randomly hitting memory just randomly, literally, and making it as bad — what if I'm looking at how you did what you did, how you design your cache, and making you do the most work possible?
It's a robot, and I'm making you literally move to every corner. It's like talking to the Roomba. Go to that corner and then that corner and then that corner.
And then it's not just letting it sweep a room. It's literally like sending it random spaces as far away as it can.
So you can make this look really bad because of the missed penalty by hitting it randomly. And therefore, there's no spatial locality. Spatial locality isn't being exploited.
You're grabbing its neighbors but never visiting its neighbors. I'm going to grab this block, and it's a lot. Maybe it's really wide. And then guess what?
I'm never going to see it again. I'm going to grab another guy. In fact, to make it even worse, I'm going to grab another guy that happens at the same index.
And, boop, it's in the same spot. Oh, my god. Really? I went to get this huge amount, and that has replaced the same guy again?
And every single one is going to be a cache missed block replacement? Yes. How do you do that? You make a stride.
The stride is exactly the same as — because I want to have an array, an array, an array — has to be the same spot every — so if your stride — memory access is plus cache size.
Cache size means — remember the picture I drew before? I drew this picture here with the cache size. Here's access 1.
The next access is exactly the same spot in the next cache down. That means this tag is I, and this tag is I plus 1 and I plus 2.
If you stride by cache size, you typically have the worst possible performance because you're not making use at all of the fact that you loaded this whole block.
You're not using the neighbors. You're going around and replacing the same guy that you — if this is really wide, imagine how — I'm making this really wide.
You're having to go to Sacramento and grab all the neighbors, and you're never using them. Can you please just the next memory access go plus 1 minus 1 so you can use some neighbors?
No, sorry. Stride plus cache size. Worst possible performance ever. In fact, I encourage you look up your system's cache size and write a four line program that reads a byte.
I don't care what you do. Read a word. Read a word from it. Make a huge array.
Make a huge array invalid. Huge array.
Find out what your cache size is and literally have a loop that reads it and then jumps by — the next memory axis is exactly the next cache size.
So that will be the worst possible situation. You're never going to exploit at all the cache at all. Forget even spatial locality. You're just never visiting the same spot.
You're just jumping in array that's really big. And you're jumping, you're striding by cache size. Worst possible performance. By the way, do that, and run 10 of them.
Take your computer, find all your cache, what your block size is, and run 20 of them. Just run a little thing. Make a little terminal. Make 10 terminals and run them all.
You're going to be hitting this cache like — I mean, you're hitting the memory. Every single one. Not a single memory access is hitting — it's really funny to do this.
This is more fun in VM, by the way, because in VM, you're moving data from the disk to the disk. So it's worse. This is a fun story to do.
I'll find you that lecture.
But that's a situation where you can make VM look really bad by always striding by the thing that's going to be the unit of data because it's the worst possible — same idea in VM.
You have these unit we have here of blocks and cache sizes. We'll talk about pages there. If you stride by page size, it's really bad.
So that was an aside to make your system look really bad. You want to make it really bad, stride by the cache size. Then you'll never take advantage of temporal or spatial locality.
Okay.
So if you make a few blocks — all that aside was if you have a large block size, you're going to have a big missed penalty because when you're going to Sacramento, you have to bring more back with you.
That's the idea. And by the way, here's the funny blip. So if the block size is too big relative to the cache size, there are too few blocks, and the miss rate goes up.
So in the extreme case where you just make it — remember I told you can take your cache.
And for the same area, you can make — in any — how do I say this?
If I said, I want you to make a fence where the area inside the fence is fixed, well, it could be this way or twice as tall and half as wide or twice as wide and half as tall.
Same area, right? I have this flexibility of aspect ratio of the cache. That's the aspect ratio.
When you make it the degenerate case, which is one high by total number of bytes equal to the cache — so one high and total equal to that — in a way, that's pretty good.
You just grab the huge range from that.
But here's the funny — if you're making a copy, if I'm copying two line pieces of code, the copy is from this part of memory to that part of memory.
So I go from here, and I read a bit. And then I go to here. Well, this is a different part.
So I have to now bring — and let's say that they're far enough away that they don't all fit together. I have to bring this guy in, put that long thing around there.
Remember, always draw your memory — same with this cache. I'll draw memory really wide. So I'm reading from here memory to here.
I'm just copying from here to there, A to B, A to B, A to B, little loop. Well, read this. Miss. Then I read this one.
Well, that's not there because I only have one cache. It's only one row. So that's a miss too. I'm trying to write that value.
And I read this one. Read the next guy over here. Okay.
That's a miss too. (LAUGHING) And you have this crazy — you're just loading in and out, just never have a cache hit because you're always reading and writing from different places.
But there's only one row to store stuff. So that's terrible. Even if I had two, that'd be better.
But then you had this issue of this too in the direct map that could have had the same index, which means they wrote the same.
The best situation is when they end up having two different rows and I can read from here. Ooh, read and write, read, write from here. This is great.
Look how fast this is if they both can fit in the cache at the same time.
So even two different rows can save me that, if I happen to have a direct mapped cache that happens to have the same index or they end up in the same row.
Phew. Long story short, one big row is really bad.
And you often have this ping pong effect where I'm continually kicking out these two guys and then forcing them out because they happen to have only one row, and they both can't fit.
So this is a really nice graph of a block sized trade off. If I look at block size versus missed penalty, how bad is your penalty, your time for larger block size?
It just goes up. And if you're going to Sacramento — it's a linear relationship. If I'm going to Sacramento to fetch one thing, it's there.
If we're going to fetch double, it's a bit more. If I fetch four times, it's more there. It's kind of a linear relationship. There's probably some overhead of going to Sacramento period.
But then every kind of extra thing I'm grabbing is slower to grab, put in my arms, and walk it across. So missed penalty goes up linearly with block size.
How does miss rate relate to block size? That's the interesting thing. Normally, block size is helping a little bit with that because all of a sudden, spatial locality is coming in here.
So if you look at this, spatial locality means that miss rate — remember, I don't have misses. I want this to be as low as possible. I don't want any misses, okay?
I want my hit rate to go up. So my miss rate is high. But then as I make my block size better, spatial locality is like, hey, you went there already.
And now my neighbors have got it for me. So that's kind of neat.
But what happens is at the end of it — we just talked about this — [CLEARS THROAT] we lose temporal locality.
I end up having too few blocks to hold all the things I normally do when it starts to go up in there. And that's a problem.
And if you remember — well, I don't think I showed this yet. Average access time — we're going to see this again — is a product of those guys.
So we multiply them together. And the fact that this guy goes up here, the fact that this guy goes up amplifies this a little bit more if you see that.
And so this goes up here. And what we typically say is we look for the knee in the curve.
We look in a place with a curve drop down, otherwise known as the local minimum. And so there is a sweet spot for the block size.
It isn't like, well, just make it as big as possible. It's always a win.
If we only looked at this missed penalty, make it as small as possible if you just look at one number. If I want to reduce missed penalty, make it as small as possible.
Well, but then the miss rate goes up.
And the fact that average access time is a product of both of those means that I have to think about the knee in the curve for that. Now, let's talk about this.
When we're talking about misses, what kind of misses do I have?
The first is a compulsory miss. These misses are misses because it's a cold cache. Cache starts, and nothing there. All the valid bits are off.
Nothing's valid. So I got to take the hit. Compulsory means you just got to do it. You've got to take the hit.
You've got to — sorry. You've got to take the fall. You need to take the miss on every road that hasn't been visited before.
That valid bit is off, and you need to pay that penalty. There's no way around that. So every block is going to have at least one compulsory miss.
Okay? Every block of memory will have at least one compulsory miss.
How about conflict misses? Well, conflict is because you've got two — remember the first picture of the cache. The two blues map to the same — I guess it was here.
The two blues map to the same blue over there. So that's a shame. Oh, it's such a shame we couldn't fix that.
In fact, in later lectures, we're going to tell you how to fix that. So two blocks happen to map to the same thing. And that's the problem with direct map caches.
I mentioned before if I'm ping ponging here, if I could even have a cache with two rows, I still might have those guys be the same spot.
This huge block and this huge block end up being the same because of the way that the index works. They happen to be the same row. Oh, that's annoying.
So that's an issue with direct map caches that maybe we can exploit and think about relaxing that. And maybe direct map caches aren't the only game in town.
We'll explore that in later lecture. So that's fun. So conflict misses, you could either make the cache bigger. And maybe the smart thing is could multiple distinct blocks fit in the same index?
What would that even mean to have two blocks, two blues end up being in the same blue area? We'll actually explore that in the next lecture. We'll see you there.
Đă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.