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ả.
PROFESSOR
And welcome back. Now let's talk about some of the terminology as we start. We've seen some examples of caches. We understand direct map caches.
We think about how to think about them, how to draw them, but there's a lot of new words. Caches.
Boy, caches have probably I feel like 20 words you may have never used before or maybe used in a different context.
So let's make sure we understand what all the words that people use when they talk about different caches.
So when I read memory, sometimes it's there, sometimes it isn't, or sometimes it's there but the tags don't match. Those three cases we call a cache hit. That's the best situation.
It means I loaded it before into the cache spot into the cache block. And when I want some data, it's there! The tags match! Woo!
Best situation. Well, there's not so great a situation, which is I go there. I go to see the cache. I go to the cupboard.
The cupboard is bare, and I went to the cache. Cache wasn't there, and we call that a cache miss.
If I don't successfully get it — if I look it up and either it wasn't there because I never loaded that particular block or the block isn't there — it's going to be a miss.
So both of those cases kind of walk away unhappy is a cache miss. I probably got to go to Sacramento to memory to do that.
Now, there's a situation where what if I went there and it was loaded by somebody else? It's almost like Goldilocks. Wait! Who's in my bed?
I went to that block, and there was somebody in my — right? What do you do there? And so that's a situation where you have a cache miss with block replacement.
I went there. Someone was already loaded into that row, into that block, but it's not the one I wanted. So that's a replacement.
That's got to be replaced out, and the new one has to be loaded in there. So that's an issue. Okay? Cache is always a copy.
Now, here's an interesting thing. I made this slide.
This is a brad new slide for this year, and I wanted to add that because I've heard people who talk about caches, use these words, but we never actually formally share it with students.
So I want to share some of the — these are kind of informal words we use about the cache. Our temperatures. You can look at a cache and assign a temperature to it.
Well, what does that mean? Well, when the cache is empty, we actually call it a cold cache. It means there's nothing there.
We think of the heat as how full and successful the cache might be to be able to respond to a future request.
So as I start to chug through my — at the beginning of my for loop, it's cold. The beginning of every code, it's always cold because you don't preload your cache.
Your cache always starts empty, so it's there. By the way, you could in other situations preload a cache, but in kind of normal computer science the memory hierarchy we don't preload caches.
Then I have to warm it up, as I start exercising my for loop, and as I'm going to memory, bringing it in, and having a lot of misses.
We saw that as I'm misses. All of a sudden I'm filling it up, and maybe I'm walking across here, and maybe I'm filling the rows and blocks. Okay, got that.
Okay, here we go! It's warming up!
It's warming up, and now I'm starting to have him hits, and now I'm starting to have some of that good, warm fuzzy feeling that I'm actually getting back the reason I had a cache in the first place.
I'm actually getting some cache hits, so I love that. So when it's warm, they say the cache is now warm. When the cache is warm, it means it's doing its job.
It's filled up with — it's not going to be perfect every time, but it's filled up with probably some recent guys, and I'm hitting them. I'm hitting some fraction of them.
Now, I've also heard "hot", which means I'm stuck on a tight loop and everything has a hit.
When I'm getting to the point where basically a high percentages hit — maybe here, and then whoops. I've jumped over here, but mostly it's hits. That cache is hot.
So that kind of temperature is a way to think about it.
Really a fun way to think about how successful my cache is to be able to respond with more cache hits in the future. It always starts cold.
It warms its way up, and when if you're really lucky in a tight loop it gets really hot. Now, it doesn't mean that the silicon gets hot.
It means the idea that "hot" means a high chance of a successful hit in the future. Some more cache terms. Let's make sure we go through all of them.
As I'm getting more hits, know what a hit is obviously. A cache hit means I successfully got there.
So as I get a cache hit, there's a fraction of all the total requests I had. How many of them were hits? We call that the hit rate.
So that's just a fraction. Its a unitless number. It's a fraction of the hits that actually were successful. The fraction of my requests that were hits.
I'll say it again. The fraction of requests that were hits. The miss rate is the opposite. It's the complement of that number, so they both add to 1.
1 minus the hit rate is the miss rate. So if I have an 80% hit rate, woo! Four out of five requests are hits.
Probably a 20% miss rate because you're either a hit or miss. Okay.
XOR or inclusive or? You're either a hit, x, or a miss. You're never both. See how I mix war with the — Okay.
Miss penalty. Miss penalty is the time to replace the block. When I have a miss — you know, you've got a miss. What's your penalty?
You know, okay. You caught me with my hand in the cookie jar. What's my penalty?
It's some wallops to my butt, or I have to go — I'm on time out for — I stand in the corner. That's the penalty for having this miss.
So the time to replace a block from the lower level is my miss penalty. By the way, this is true for any cache. It's for any cache to the guys below.
Any cache that's caching the lower element at any level. This is you have this missed penalty.
How long does it take to get to the level below to bring it back into the level above? Because you always want to bring that back in.
And the hit time is what time is it to access the cache memory, so this is just great. And by the way, this counts the tag time.
I do the tag comparison, blah, blah, blah, and a lot of these are in hardware so they're fast because they're in parallel, but that's a factor as well.
You've got factor in the hit time as well. And by the way, this is an interesting thing. We actually use dollar sign for cache.
So kind of like the whole kind of — I know what this means. This means I'm hitting my hands. I don't know what this means, but kind of cache money, people.
So think of dollar sign for a Berkeley innovation. As far as I know, my predecessors invented that. They use a dollar sign for caches.
There's one more piece of information we need, which is — I mentioned this earlier.
Do we have a sentinel value that the cache can never have to know when it's — remember we need to know am I cold, am I warming up.
How do I know when it's garbage data? So do I have to write 0s to everywhere?
I can't just write 0s everywhere because you could have a tag of 0 and a data of 0, and that doesn't make any sense.
So am I going to — let's reserve a spot that can never be in the — well, that doesn't — I don't like that either.
So what we're going to do — and this is a clever design decision. You may have come up with this on your own. Have a bit.
Just call it a valid bit, and when that bit is 0 it's not valid. And when bit is 1, now it means I have good data there.
So by having a single bit, it saves me from having to kind of write to my cache to erase it, putting the sentinel value in. I just have a single bit.
Once I set those all the 0s, the cache is cold and has garbage values in there. So we're going to use what's called a valid bit to store it, which is nice.
This tells me whether that tag is valid because the tag can be anything. The tag is my cache number. That's from 0 to the maximum number of cache copies that could have in memory.
That's it. That's all I've got. So there's no bad value there, so we don't want to think about having a sentinel and borrowing one of those guys.
We want to be able to access anything.
Any part of memory should be able to — in my cache, which means any tag — however bits-wide my tag is, that could be any bit pattern.
I don't want to use up one of those bit patterns. I don't like that idea. It's not a good design. I don't like it from a computer engineering point.
From an engineer period. Forget the computer. I don't think from an engineering point of view, to waste something because I can't think of a having another bit. Now, you know, ain't no free lunch.
I need to borrow some space to store that valid bit anyway, but it's better than having to steal some memory that I can't access anymore that can never be in the cache.
I don't like that model. I like a valid bit better. So that's it. 0 is there.
When I go to request it, if it's 0, it's always going to be a miss. A cold cache has all 0s in the valid bit. It mean there's nothing there.
It has bits there, but they're garbage. All the tags are garbage. You can't trust them. I'm telling you!
Give them some money. They never return it. You can't trust it. Can't trust those tags if the valid bit is set to 0.
If it's 1, then you can trust it, and that's the idea. So here is a picture. Here's a beautiful picture! A 16 kibibyte.
How many bits wide? How many total bits for my I and my O? 16 kibi. Come on!
16 kibi. 16 14 bits. 2 to the 14 is 16 kibibytes. Okay?
So 14 bits for total amount, and I have here — look at this. Oh, look! 0 through — I'll do the numbers later. Oh, see?
Here we go. 16-byte blocks. In my head, I'm already doing 16-byte blocks. Okay.
Well, 16 kibibyte total. 16-byte blocks. That means the width is 16 bytes. How many rows?
1,000. 1,000 times 16 is 16,000. That's not that hard. Okay?
So how many bits for 1,000? 10! 10 bits of index. How many bits to tell me what byte it is for 16?
Four! Four bits. Four here, 10 there. That's 14 bits.
There's my total area. 2 to the 14 is 16 kibi. It just works, and there's my valid bit, and there's my tag.
So my valid bit is set, and we're going to reset it to make it all 0s. This looks like a real cache. I'm feeling pretty warm. I'm feeling pretty good about this.
This is a nice model. This is a picture that we might use. This the end of this lecture. I'm pretty excited.
We're already kind of half. This is it! This is the halfway point! We're downhill from here.
We're going to see a really nice, very detailed example as we play with this and expand more of the parameters of how do we expand our cache.
We're going to show you a cache and say, well, it doesn't work in this way. And we'll add this feature. Doesn't work in this way.
We'll add this feature, and we haven't talked about writes yet. We've only talked about reading bytes for now. So we'll talk about a more general thing in the cache as well.
But in conclusion, in these lectures you've learned the operation of a direct map cache, the simplest kind it comes from.
I hope you understood and appreciated the TIO and the kind of where to think about that I did in the last lecture. I hope that was useful.
We talked about a mechanism for moving data back and forth in the memory hierarchy, which is kind of neat. This address and value bindings.
From the point of view of the program, I don't even know whether there's a cache or not. It just is faster when it does have a cache, so I don't have to change anything.
Now, if I did change something, that'd be great because I could optimize for the cache, and that would be something we could talk about later.
We've got to compare our address with the tag, and we got to be able to handle the hit or miss.
That's the idea, and when it's a miss we got to load the new block, reset it, and bind it up on a miss. Okay? That's it! We're done with this lecture.
We're at the halfway point. We will see in the next set of lectures cache is part three. Take care.
Đă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.