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
We're doing great. We're about halfway through this last lecture. Now, let's take a look at a new way to measure how well we're doing with our cache.
I said, well, I want to have the fewest misses, and I want to have the maximum hits. But I also want to think about even maybe adjusting parameters of the cache.
And maybe as I adjust parameters, maybe the time there — you saw this. It was like we talked about before, there's a miss penalty.
So there's some time, there's a number of cycles that's a factor then. Where does that come in as I'm running different traces on different cache parameters?
So one of the ways to measure whether your cache is doing well is to look at — let's actually have a really nice rubric that'll tell me what we're trying to optimize for.
And really, what we're trying to optimize for in a cache design is this phrase here, the Average Memory Access Time, or AMAT. So as I said, there's a ton of parameters in my cache.
I've now taught at least a couple. Look, associativity, got this big number, N, of what's my associativity. What's my block size? Remember, I told you you can change the aspect ratio of a cache.
What's my replacement policy? What's my write policy?
There's at least four different parameters — it's like filling in a form that I have to kind of fill in all these parameters before you let me build a cache.
And so all of these elements allow me to have flexibility as a cache designer. I'm a hardware person building the fastest new whatever, a chip, a CPU, an embedded system.
I don't know what I'm doing. But I'm going to use a cache for it. I know caches are important. And I get some parameters.
So as I'm looking at the kind of standard traces, standard workload I'm going to be using my cache on, using the system on, how do I know what to choose for?
Well, design against this particular parameter, the average memory access time. And here's what it is. You've got a cache. This is the stuff in the cache, this is the stuff below.
This is the stuff at the next level of memory. So the average memory access time is the hit time. Hit time says, you hit the cache, that's great.
If you didn't hit the cache, what happened is you've got a miss rate that says when didn't you hit the cache and a miss penalty.
And the reason this is, you might have thought, why, Dan, why shouldn't this be hit rate times hit time plus miss rate times miss penalty?
Why isn't there a term in here? Why isn't this times hit rate? Hit rate. Why is it like that?
And it isn't for the following reason. How much penalty do I have to pay? When it's a hit, I pay the hit time.
When it's a miss — stay with me. How often do you have a miss? Well, miss rate tells you how often you miss it. What's the penalty for that?
Miss penalty. Even after you get that, you have to then grab it from the lower memory, put it in the cache, and almost restart and then have another hit.
So that hit time gets counted both times.
So you don't need to have the hit rate in there, because really, the miss rate captures that other time, and because you're paying the hit time either way.
If you weren't paying that time either way, you would fraction it all up. But you're paying it either way, so it's like, I didn't even care what the hit rate is.
Whether it's a hit or miss, I'm paying the hit time. It's like an overhead, right? This is, oh, you're paying this either way. Hit or miss, you're paying the hit time.
And then if you happen to then have a miss, here's how often you do it, and here's the penalty you have. So that's the reason this term as it is, okay?
Again, the illusion is really fast as the slowest, as the smallest level, the smallest, most expensive level, but the size of the larger level. How do we improve the miss penalty?
So we played with the block size as a way to play with these things. And the larger block sizes, more miss penalty. You saw them. Remember?
When I have a miss, man, I got to go to Sacramento and bring more stuff in.
So bigger block size affects the miss rate in a good way for a while, but increases your miss penalty. What's another design space we could have?
Almost like we could turn to recursion for this. So let's think about this. Today — again, when caches first became popular, the miss penalty was like 10 processor clock cycles.
So in the early, early days, a miss penalty was — if you had a good memory, there was no gap between the processor and memory speed. So there was almost no miss penalty.
And as it became to grow, well, in the early, early days, it was like 10 clock cycles. Eh, could wait 10, no big deal.
Now it's on the order of 200 or even more, okay? That's an issue, don't want to go to memory. So this is my picture. I go in to memory.
So what do I do? I introduce the cache. And the cache says, you know what? From the point of view of the processor, you're getting it from — I'm doing a load word.
It's like abstraction. I don't care — don't tell me how the data is getting here, just make it happen. Surprise me. Okay?
And now, maybe it's the cache that has it, maybe I go to Sacramento. I don't care. From the point of view of a processor, the data is ready when I want to get it.
You see this little picture? Do you see how it's kind of recursive in a little way? Processor, memory, a cache, but what if I went one more level?
Watch this. What if I added a second level cache? And this is in my triangle really what's happening. We're adding more levels of cache here.
So adding just simply one more layer of cache between memory and the processor — we'll often call it the second level cache. It's almost like this.
Someone's on a tight rope, and they might fall, and then there's a little teeny net to save them. If they fall out of that net, there's a bigger net below that.
So this is the idea of having these successive nets underneath.
So if you don't have it in the — we call it the L1 cache, that top level cache, the smallest, fastest, most expensive cache, well, try it in the L2 cache, the level 2 cache.
Maybe there's even a level 3 cache. So all these things are ways to try to catch the data to prevent me from going to Sacramento. The whole point is Sacramento is too far away.
That's the point. So here's the picture we saw before. You saw this picture. And I hid this.
Here we go. Let's what happens. There it is. So that is the reality.
Now I'm kind of revealing the onion that I've got the CPU, has its cores doing something, got registers. And then I'm going to first go to my L1 cache.
And if that fails, my L2 cache, and that fails, my L3 cache. And every time I go to a level below, the same rules apply. It's bigger, slower, and cheaper per bit.
So that's the idea. And the lower ones are always a copy of the ones below, unless I have, what? Write back.
If I have a write back write policy, they may not be a copy. They may be inconsistent or stale. The lower guys may be stale, depending if I have a write back cache.
Don't forget that. We mentioned that before. So let's see. L1, L2, L3, the parameters on my computer are about this Mac.
Here we go, system report. Here we go. Can you see this picture? What does it say?
Says I've got a level 2 cache per core. Doesn't say what my level 1 cache is, but clearly there is a level 1 cache. It just doesn't say it.
It's part of the internal CPU. It's not even showing that number. But we can look at the i7 specs to see that. But I have a level 2 cache per core.
I have a multi-core machine. I've got four cores in this laptop. It's a little bit older. And I've got 256K in my level 2 two per core.
Every core has its own level 2 cache. And certainly, every core has its own level 1 cache. But there's a shared level 3.
So we haven't talked about multi-core at all, but each of those cores shares an L3, which is big, massive compared to that, 8 megs. So 8 megs is really big.
How many bits for 8 megs, people? 8 megs, 23 bits. 256k is how many? 18 bits for L2 cache.
So kind of neat that I've got — and at the bottom in my hierarchy, at the bottom, I got 16 gigs for overall RAM.
So kind of neat to be able to see this and look at a particular setup for a particular computer. Now let's analyze this. Well, you think you're so fancy?
What's the benefit of this? Well, let's look at what the equations are first for my AMAT. How does AMAT change if I have a level 2 cache?
Remember, before, AMAT is hit time — L1 hit time — plus L1 miss rate times L1 miss penalty. But now, what's the L1 miss penalty?
The L1 miss penalty is — well, if it's in L2, it's just L2's hit time — plus — remember, I'm paying the L2 anyway.
Plus the L2 miss rate times the L2 miss penalty.
So if I look at this, it's almost like it's a recursive — you can imagine it's L3, and L4, L5, in a recursive way like this.
So these equations kind of nest in this beautiful way.
So AMAT overall is L1 hit time times L1 miss rate times the quantity L2 hit time plus L2 miss rate times L2 miss penalty.
Complicated, just write it down, you'll have it. And, in fact, let's do an example, very simple example. Hit time is one cycle, miss rate is 5%. 1 out of every 20 is a miss.
And the penalty is 20 cycles. What's the AMAT? Well, it's 1, you're paying the 1 all the time — plus 1/20 times 20. That's 1.
1 plus 1 cycles is 2 cycles for that. That's very simple for the L1 situation. So, ways to reduce the miss rate. Make a larger cache.
Just have a larger cache that catches more things. We love that. The hit time of the first level cache is less than the cycle time. So that's great.
The first level cache is less than a cycle, meaning I can get to the first level cache at a fraction of a clock cycle, but much slower for other larger caches.
More places to put it, so change your associativity. My goodness, think about associativity handling some of those conflicts we used to have for the conflict misses. Fully associative, you saw the block anywhere.
N-way goes a particular place. In general, the typical scale these things, I've kind of showed you before, L1 is in the scale of KB — kibibytes. Miss rate is 1% to 5%.
That's great. Hit time I talked about being in one cycle. Miss rate is probably, what? Miss rate is 5%.
Even that's — come on, 1 out of every 20 is the miss rate? I'm hitting a lot of hits. I love that. That's just great.
L2, we showed you my number. I think it was 256K.
Hit time, a couple of clock cycles. There's a different technology used for that. You might use SRAM for that or something. Usually, L1 is on chip.
L2 might be on chip, might be — depending on the older system — might be an SRAM. Miss rate is now much larger.
And you might ask, why is the fraction of L1 — why is the miss rate so high for L2? It's so small for L1. Why's it so high for L2?
Partly because L1 got all the good stuff. All the really good temporal coherence happened in L1, and L2 just kind of said, well, whatever other access pattern you have is L2.
So in fact, L2 does pretty well. Miss rate is not that bad. I mean, miss rate is only 1/5 or so. But it's not 1/20.
It's because L1 got all the good stuff. That's really what happens. Let's look at example with an L2 cache. Let's do our AMAT with an L2 cache.
We have all these parameters. I got five terms now we got to think about. So let's do this together.
If I have an L2 cache, how much is — okay, L1, hit time, we'll make one cycle. Miss rate is 5%. L2 hit time is 5 cycles. L2 miss rate is 15%.
Let's just do this, percentage of L1's that miss but are missed in L2 also. And L2 miss penalty, 200 cycles. So this is these terms.
I plug them into the equation I showed you three slides ago. And I get average memory — so the L1 miss penalty, what's the L1 miss penalty?
Well, it's the L2 hit time plus the L2 miss rate times the L2 miss penalty. That's what that means. So that's 5 plus 15 times 200 is 35.
Okay? So that's the L2, L1 miss penalty. If you miss L1, you're paying 35. You used to pay 200.
Look at this. L2 miss penalty means if you have to go to Sacramento, it's 200. Now I'm only paying 35. Are you kidding me?
I'd rather pay 35 than 200 to Sacramento. Average memory access times, 1 plus — what is the L1 miss rate? 1/20. What is the L1 miss penalty?
Remember, I saved from having to go to Sacramento with this great L2 guy that caught me.
It's almost like I'm driving to Sacramento and somebody — I don't know, I don't have an example of — in, I don't know, Richmond or something, say, hey, by the way, I got your paper here.
Wait, really? You saved me from going all the way to Sacramento? Great. Grab it from L2, go back.
So I still need to get in my car and drive 35 versus 1, but it was much better than taking the 200 to go to Sacramento. That's the idea.
So the average member access has only 2.75 cycles. Are you kidding me? Average memory access time for those numbers, 2.75 cycles. Compare this without the L2.
Again, one cycle L1 hit time, L1 miss rate is 5%. Again, if I have to go to Sacramento, it's 200 cycles. So 1 plus 1/20 times 200, that's 10.
1 plus 10 is 11 cycles. So compare that. 2.75 cycles for AMAT, Average Memory Access Time. I've got a load, I've got a store.
That's a memory access. What's the average memory access time? I'm only paying at most kind of three cycles if I have an L2. I'm paying 11 if I don't.
I mean, worst case, for one particular guy, it's 200. But on average, there's a lot of hits. So that averages and brings the average down from 200. But I don't get past 11.
11 is terrible for an average memory access time. Average memory, every load is 10 cycles. I'm just sitting idle for 10 seconds? Crazy.
I add an L2, it's only about three cycles. So I love that. So L2's are really great for performance, and that's why we add them. See you next time.
Đă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.