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. We last left our hero when we were thinking about, could, possibly, two different memory requests that were blue end up being together?
Rather than only one of them, there's only one blue spot, maybe there could be two blue spots or more. So the extreme idea is a fully associative cache.
Might as well go all the way. It's almost like you're overcompensating. One says, I know exactly where you go. And the fully associative says, maybe you go anywhere.
It's like, rather than give you an assigned seat, sit anywhere! Go crazy! That's kind of what fully associative caches are like. So let's see what that means.
So a fully associative cache, what I mean is, you can literally go anywhere. So tag was before. The offset's the same as before. But there's no index.
The index would tell me exactly what row to go to. I'm telling you, there's no rows. There's no idea of rows. Any block goes anywhere.
Sit anywhere you want. Go crazy. And you have to compare all the tags in the entire cache to see the data is there.
Which now means, because there's no — remember, the tag width is a function of I and O. I is nothing. There's no more I anymore.
So now there's only an O, which means the tag got bigger. So remember that the tag has to get bigger when you have a fully associative cache to factor that in.
So here's an example, a 32 byte block. That's 5 bits to specify 2 to the 5, or 32 different bytes, I want there.
Well, 32 bits wide is my total address. If 5 is here, that means 27 is my tag. So remember, that tag would have grown.
If I had had an index there, then my tag would have grown. Okay, think about that. So I've got my tag, my valid bits, my cache data, like that.
And the key here is, I'm going to try to — it was hardware. I'm going to try to compare my tags in parallel. That's amazing.
If I can do that, if I can build circuitry — I'll have to show you a picture in a second — then that's great.
It means I can compare tags in parallel and figure out whether I've got it or not if they match. Benefits. One of the huge benefits — are you kidding me?
No more conflict misses. The whole idea that the two blues, only one of the two — there's not enough room in this whole cache for the two of us.
That's what that model is. Only one of those blues can exist in that blue spot. This is, anybody puts their stuff anywhere. Just find a seat.
That's what they're saying. The drawbacks of that. Again, the drawbacks are just in the hardware point of view, which is not algorithmic. It is, it's hard to build hardware comparators for every single entry.
If I have it for two, we can do that. It's not that bad. But If I have 16,000 comparators, which is just too hard to do this in a normal cache.
So these are hard to do. A software fully associated cache, I love. But a hardware one is hard to build. So that's the key here.
The third kind of miss is called a capacity miss. And this means, this is a miss that, if I could have just grown my cache bigger, I wouldn't have had that miss.
That's what a capacity miss is. Capacity miss is one that wouldn't have occurred if I would have had a bigger cache. This is kind of a soft idea.
I'm going to show you an action algorithm for that. And by the way, this is the kind of misses you get with fully associative caches.
You obviously take a compulsory miss for every time you ever visit a piece of memory. Every block of memory, I'm going to take a compulsory miss because I never visited it before.
But even if I visit the same one that's one cache above you, fully associative can handle that. I'll take another compulsory miss to grab it for the first time it's in there.
And the next kind of misses I get once I'm using these guys is a capacity one.
Which means, I want to fit more guys in here, but I only have a certain space for my fully associative cache, and I can't fit anymore.
So a capacity miss is what the other set of misses you're going to see. Long term, steady state, once, let's say, you've exhausted, visited everybody, at least once?
Well, it's the capacity miss that really gets you. Because you've already taken the compulsory hit from every single cache block, every single memory block.
But it's the capacity miss that will — if I had memory, if I had an infinite memory, I wouldn't have had those capacity — If my cache were infinitely big, I wouldn't have taken those capacity misses.
I would've load them all in. If I could somehow — this is a crazy world — store all my memory in my cache, well, once I'm there, it's there.
Like, literally, it would be — I don't want to say a copy. But it would be a reordered copy of memory, literally.
If I had, think, a fully associative cache that were 34 gibibytes — 2 the 32, or more — I'll just say more.
But if it were exactly that, once all the — [TRILLS LIPS] I swept through all the memory. I can hit it randomly, I could hit it in order.
Once I've loaded them all in, they'd be in my cache. And I wouldn't have any more misses, because they're all there.
So a capacity miss is the miss that you get because your cache can't be any bigger, and there's some fixed costs that you have.
So here, this is a great algorithm to think about how to categorize these misses. Okay, so first, consider the craziest — almost like what I was telling you now a second ago.
Consider the most insanely sized cache you could ever. Infinite size, all fully associative. For every miss that occurs, it's going to be a compulsory miss.
Because it's never about a capacity, because the infinite size. It's never about conflict, because it's fully associative. So therefore, all those misses that I have in that world are compulsory misses.
Now, consider, I have a finite-sized cache.
And now, let's start actually having a workload. As a first line, it says, run an address trace against a set of caches. So I have a particular cache I'm comparing to their neighbors.
That's the idea. I'm comparing this design against those designs. Wow, that's kind of interesting, to have 20 designs and see what happens.
But I have an address trace, which means I have a list or stream — could be infinite — of address requests.
And maybe you want to have reads and writes in there to play with that as well, to play with as a write back, as a write through, all those things.
I've got this address trace. And I hit — [TRILLS LIPS] I hit my cache with that trace. And I hit the neighbor cache with that trace. And I hit that.
And I'm comparing them all. So when I'm comparing them, I'm now looking at a reasonable, a finite-sized cache. And particularly, one with all the parameters. And now, I hit it with this trace.
All the misses that are not in the first category, compulsory, I count these as capacity misses.
Meaning, the only thing I change from step one to step two is, change it from infinite size to finite size.
Therefore, the new misses I get must be capacity misses, must be because of the change. Logically, makes sense. And now, here's the piece of it. So it's finite, but still fully associative.
What if I take it fully associative, and I shrink it down less associative, and make it not fully associative? Right now, you only know of direct mapped. There's something in the middle.
I'll mention it [INAUDIBLE]. I'll mention a second. All the remaining misses that — sorry. Yes, finite associativity.
So I took away — first of all, it was infinite. Took away that. It's like, I take away your powers, Superman. Oh, I can't use the eye beams anymore.
I can't fly. Okay, I took away from it being infinite size, made it finite. Now I take away your fully associativity and reduce it in some way.
Either I reduce it all the way to direct mapped, or somewhere in the middle. And I'll tell you that in a second, what that is.
As I do that, what are the remaining misses I have? Those are conflict misses. Those are misses that I wouldn't have had if you were fully associative. That's the idea.
So that's a really nice algorithm to think about how to think about, is it a compulsory miss, a capacity miss, or a conflict miss?
Run this set of traces on that to see what would happen. And those three cases will be flagged. There's even, by the way, a fourth miss.
We're going to tell you in about a month-ish, when we're talking about parallelism. So remember, in your back of your head, say, oh, there's a fourth miss. What is it?
I'm not going to tell you yet. I'll tell you later. In conclusion, this is the end of the third out of the fourth lecture on caches. We're almost done.
We still haven't talked about what the thing between fully associative and direct map is, somewhere in the middle. That's what we're going to talk about the next lecture.
And we'll show an example in demo 2. So step — here's my algorithm. Let me make sure you understand the algorithm. I have a memory request.
Now, we know it can be a write also. But for now, let's do a read, okay? Divide into the T I O bits. Go to index I, check if it's valid.
If 0, it means it's a compulsory miss. Set the valid bits, I said that. Compulsory miss.
And use the offset [INAUDIBLE] to return the right chunk, figure out what column I'm in, return the right chunk. If it's 1, that means that somebody's there.
But like Goldilocks, it could be somebody that fits exactly in my clothes, or somebody that's wrong. Oh, you're not the same tag. You're the wrong person. So check tags, okay?
If it's a match, hit! Woo! And I use my offset to figure out which column I want by word, or whatever I want from that.
If it's low double, I grab two words from that. If not, then I have a conflict miss. I got to take that old block out.
And here's a part of this that's not written there. If I have a write through, I do nothing. I kicked the whole guy out. If it's write back, I check the dirty bit.
If the dirty bit is set, oh, man. I got to write that guy out, send that guy back to memory. Now the memory is consistent.
And now I read the correct guy in, load the tag, turn the dirty bit off. And we're back in business. And return the value, return the right chunk.
So I didn't mention the dirty bit in here. You now know what the dirty bit is. That factors into this algorithm as well. And that's the picture.
So next lecture, cache series 4, we're going to see an example, a demo, and talk about, what is that associativity called that's not fully associative and not direct mapped?
Who lives in that flyover? Who lives in the flyover area here? There's California and the East Coast. Who lives in the flyover area that's somewhere between fully associative and direct mapped?
We'll 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.