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. In this finest series of lectures, let's learn a little bit about initially what a set-associative cache is.
It's the cache that lives somewhere in the middle between a fully associative cache, where you can sit anywhere, and a direct map cache, where you have a ticket for your seat and you sit exactly there.
So somewhere in the middle where you might sit in first class, business class, and coach, within those areas, you might sit anywhere, but you're kind of set into a set.
That's the idea. So an n-way set associative cache means, n means the number of blocks that are in a set. So you have a tag as before, you have an offset as before.
Offset is what column you're in, what byte or what word you're getting. The index now points to the correct, what we call, quote unquote, row or a set.
So that set has n items, so it's two ways, two way set associative would mean there's exactly two blocks that live in that set. That's the idea.
Each set contains multiple blocks, once we're in that set, they're fully associative within a set, and we have to then check all the tags in some kind of parallel comparator to do that.
But at small scale, that's doable. At a large scale, that's hard to do, hard to build. So the overall size of a cache is the number of rows.
What's the rows now? The number of rows is the number of sets.
So the indexed bits tells you the number of sets, and then times n, where n is the number of blocks per set. You multiply sets times blocks per set, you get blocks.
That's the number of rows total. The number of blocks. That times the width, which is the offset bits, two to the offset bits, and that's your cache size.
So very similar to before, but just now each rather than directly going to a spot, you're going to a set, and you're fully associative within that set.
So here's a 2-way set associative cache example. Notice we have here red and green and 0, 1, 2, 3, 4, there.
And now if you watch, any red can go to any one of the two red positions. And this is a perfect example.
The whole ping pong effect, in the direct map example, when I copied from 0 to 4. If you remember, 0 and 4 — I'll grab my pen here.
If you remember, 0 and 4 used to be the same color. It was blue. So if I were copying, if I only had, let's say, a set that had one block.
If I were copying from 0 to 4, I wouldn't be taking advantage of my cache at all because I'd be kicking it out.
Here's 0 and then here's 4, and then here's 0 and 4. And I wouldn't ever be kind of making use of it if I were walking along.
Let's say, if it's a really long block, a really wide block, so my cache is small but wide.
The aspect ratio was like that, and I were kind of streaming across copying from one to the other, very common piece of code. Duplicate an array, very common thing to do.
I'd be killed if I weren't able to somehow capture both the red areas. If both of them were blue, I wouldn't be able to have both blue in my cache at the same time.
If you imagine a really big one, that's terrible. Here, even a 2-way set associative solves that problem. So two sets, two blocks in the set, we're really happy to see.
I didn't even say it and this picture doesn't say how wide, what the block size is, but we don't care. We're just talking about how it works.
The basic idea, again, cache is direct map with respect to the sets. The index tells me exactly what set I'm in.
Within that, I'm fully associative within the n blocks in that set for an n-way set of associative cache. So again, let's do it.
Find a correct set using the index value, compare the tags with everybody in there, because now I'm pretending to be fully associative. I'm in here. If a match occurs, great.
Otherwise, I have a miss. And finally, as always, grab the offset bits to figure out what word or what byte I'm requesting. Easy. So it's great.
I think I kind of mentioned this. Even a 2-way set associative handles all those conflict misses that copying from a blue to a blue is great.
Now, in the earlier case, coming from a red to red or green or green, I can fit both reds or both greens there, so that kind of copy from one to the other really help.
Even 2-way, even just moderately allowing for 2-way, just a little dribble. Here's direct mapped, one step over is 2-way. By the way, n almost universally is a power of 2.
It's 4-way, 8-way, 16-way in general, okay? And again, hardware isn't that bad, only need N comparative, so two comparatives, which is great. SIRI ON WATCH: Sorry, I couldn't hear what you said.
PROFESSOR
Thank you so much, Siri. Well, what I'm saying is if it's direct, it's a 1-way set associative. Just make sure I tell you that.
So here's this knob, and this knob says, if I turn the knob all the way for M blocks. Let's say I have M blocks. Total M blocks.
Well, 1-way, if I say I'm 1-way set associative, that really means direct mapped. So 1-way set associative is direct mapped. And M-way means that M blocks can occur in M slots.
That's fully associative. So that knob really goes, if total height of my cache is M, when the knob goes this way, it's one, and therefore, I'm direct mapped.
If it goes all the other way, it's now M. I'm now fully associative. That makes sense. And so these are both special cases of the more general case, which is this.
So this is actually a more general case, which is kind of nice. And this is the dynamic slide. This is the last slide on this lecture. I love this slide.
Let's do it together. Let's walk it through together. I think I did this earlier, but this is great for a 4-way set associative cache. Here's how it works.
How do we start? I don't know how to start. Divide it up into the fields, tag, index, offset, TO — now remember, TO dan. Grab my index and tell me what set I'm in.
Not what row I'm in. Not what block I'm in. What set I'm in.
Here I've drawn, rather than kind of draw a red, red, green, green, whatever I do this way, I draw them across. So this here, these four guys, there is my set.
That's my four in my set. And now, this happens in parallel. Watch what happens. Well, let's do our same thing.
We've seen this before. We've seen our tag and valid bit comparison. All that's done, and this is what's really fun about this. I think I can even do this.
I can even zoom in. I can even zoom in — look at on — on this. And let's see what's happening at the bottom here. This is fun.
So what's happening at the bottom is each of these is did it match? So that each of those are comparators. Did it match? Does a tag match and is it valid?
Remember, don't forget the valid bit. You could have garbage there that happens to match the tag. That would be really uncool. Now do I have a hit?
Sure. It's an or of all four of those lines. So that makes sense. Now here's the interesting thing.
This is — let me zoom back a little bit. This is the actual data.
If you remember, the data used to go through a mux being chosen by whatever bits of the offset were being used to grab the particular word.
I think it was the word I was grabbing at the time. Do you remember that?
So that was there, it was a mux that chose those two bits to choose what word I was grabbing.
Here, this data is coming through, and it goes to a 4 to 1 mux but rather than being driven by two signals, it's going to be driven by four signals.
And those four signals, we're going to call — let me zoom back fully. We're going to call that One Hot. And One Hot is exactly as you might imagine.
It's a set of lines and lines in which I promise you the spec is on this One Hot system only one of those will ever be one at a time.
They'll all be 0's by default, and when you want to drive the second one, then this would go high, but everyone else would go quiet.
So only one is ever hot or one ever, and if that's the case — and by the way, I really encourage you to think about how you might wire a 4 to 1 comparator if I did this.
So rather than having two bits that select that.
I have this One Hot model in which whenever one of those lines goes hot, which means it is both valid and the tags matched, that's what chooses.
So let's say it's the right most one. This one here. Well, when that goes high, it says, whoa, where did that line came from? That came from the right most guy.
That means that matched. Well, then that means this would get passed through to the output. And similarly for the other four.
So the idea of a One Hot signal line for my mux is just another way to drive the mux.
And I do encourage you to be able to sit back — how about it might be on a final exam — where you might have a situation I want to show you.
Tell me how to build a One Hot signal line for 2 to 1 mux or 4 to 1 mux or 8 to 1 mux.
Think about how you do that if I have — by the way, just in general, if I have a One Hot line, I have to have the number of signal lines at the control lines equal to the number of input lines.
So notice I have four here, 4 to 1, and I have four of these because only one of them is going to be hot and that one drives the guy that ends up driving the bridge.
We always talk about this being a bridge, and it's like four roads converging on one bridge because the bridge is out or they're repairing a side of it.
So that's the idea. So that's N-way set associative in this particular example of it with the hardware, the actual circuits block diagrams of a 4-way set associative.
We'll talk about other set associativity and other components of cache in the next lectures. 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.