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 finally do it. Let's teach you how the basics of the simplest kind of cache we can come up with, the direct map cache.
So in a direct map cache, each memory address — one of the questions we were asking of a cache is how do you know, when I go to memory, where it lives in the cache?
Okay. Where does it go? Do I put it anywhere and then search for it linearly, or log? We never do that.
We know exactly where it is. And where it's going to be is a very clear location. We'll talk about it when we show an example.
The idea is every memory address is associated with exactly one block. It's a new word you haven't heard before — block.
That block is the amount of data that you move in and out of caches. So that's it. If I'm talking about a hard drive, I talk about files.
What's the unit of data — files. If it's registers, it's a word — move things in and out in a word.
In a cache, the thing you move in and out is called a block. That's the unit of transfer. So which block it's going to be in is always defined, okay, and very clearly defined.
It's not a search. There's no search needed to find it. I know exactly by what the bits happen to be. Let's actually look at an example to see what they look like — there.
Here's your first cache. One of the abstractions of memory is to think of it as, basically, infinite. We know it's 2 to the 32.
It starts at 0 and moves to 2 to the 32 minus 1 possible bytes I could write. And here — we're showing it here — each memory addresses a byte wide.
So we're showing that — we're drawing this memory as a byte wide. And by the way, you can draw this picture of memory different ways.
Memory is — I can draw it a byte wide and 32 — 2 to the 32, or 4 billion. And actually, we now know the word for it, don't we?
4 gibi — look at this — 432 is 4 gibi, remember that? So I can draw it 4 gibi rows where each row is 1 byte wide.
Or I could draw it a word wide, so 4 bytes wide and only 1 gibi high. So 4 times 1 — 1 gibi times 4 is 4 gibi total.
Or 1 byte times 4 gibi is 4 gibi total. So I can draw the memory and change the aspect ratio thinking of different ways.
So it's the same memory, I'm just drawing in different ways and thinking of different ways.
And in fact, I'm going to encourage you from now on — from now — from this point on, if you ever draw memory slowly — I'm going to say this very slowly so we get it all — draw memory so that it's the same width as your cache.
That's all we got to do. From now on when you're thinking about one of these cache problems, oh, turn the page on the final exam, it's a cache problem.
Cache says, the block — remember, the block is the unit of transfer, that's the width of the cache — is some amount, okay? Whatever that amount is draw your memory the exact same width.
The memory is going to be more rows because the memory is bigger than the cache. But always draw — in fact, I always draw them right above each other.
Here's the cache, here's memory. So the same width is like there — width of cache, width of memory, okay? So do that.
I'm drawing them here two separate pictures — not like this but — same width. See, I did it, same width, okay? Okay. So here we go.
First problem, notice the color coding. Before I even tell you what's happening, the color coding tells you the answer, which is every four elements knows exactly where to go.
If you look at this picture, all the blues go to the blue area. So this is a 4 byte cache. I'm starting to use some words that now it might make some sense.
What's our block size? What's the unit of transfer? It's a byte. And that's the width.
So this is the block size, and it's only 1 byte. So I'm drawing memory 1 byte wide. So how high is it?
4 gibi, 32 to the 32 total bytes I have access to, okay? And by the way, sometimes we draw memory from 0 in the bottom to 0 on the top.
I actually prefer to draw it top down.
But the lowest number here, increasing number there, but sometimes the picture we flip it for convenience sake, like when we talked about the picture of — if you remember a picture where stuff lives in code, 0 is the code, and then above is the static, and above it is the heap, and above it there's a stack at the higher level.
So we actually flip when we talk about what the code does. When we actually run cache problems, we flip it to have 0 be up top and down there, okay?
All right. So this is going to be 1 byte wide. And if this is a 4 byte cache, that must be that this is 4.
There are four of these guys because this times this is going to be the total size of the cache, okay? It's like the area, think about the area.
We'll actually have a picture or two later we show that, but that's the idea. Width times height is the area of the cache, okay? But that's the idea.
So every four — so I can tell you without even thinking, there's no search anymore. Well, let's see, how about 9, where does 9 live? Really, it's like modulo, modulo 4.
Well, what's 9 mod 4, one? Well, no, that's what color — I didn't know that — I didn't know that, okay? I know — I know my — 9 mod 4 is 1.
Let's just see if that's true. Well, 9 is this red color, and 1 is the red color, see? Did it for me. So in a way, this cache is doing modulus for us.
And that's how we do it. Another way to think about it, here's another way to think about it.
What are the memory — what's 9 — what are the memory addresses here? Let's look at 9 here — 1001. Which of these bits is telling me what row of the cache it is?
Which one? Can you guys tell me? Yeah. Isn't that lower bits telling you what that is?
So already I can tell, if you just tell me the number — oh, what's your memory address? Oh, it's FQ — these have to be hex values — good, q, good, Dan, q.
That's a nice hex value. FED 97346. Oh, 6, the last one was 6. 6 is 0110.
I bet you you are in spot 2, which is the third spot, but it's spot labeled by 2, okay?
So all you're going to do is look at the lower the bit to tell you what row you're in. We're going see it's a little bit more complicated than that.
But that's kind of neat to be able to quickly go and figure out where things are immediately, just by looking at those bits.
So cache flow is — I've said some of these things — but cache location 0 can come from 0, 4, 8, or anybody that has two zeros in the lower bits.
Basically, anybody that's divisible by 4. Ah.
0, 4, 8, C — keep going — 0, 4, 8, C — in fact, if you look at any memory address, this is all you need to — look at that hex — look at the last — look at the nibble, the least significant nibble, and that's basically it.
0, 4, 8, C, you're at 0 — sorry, that's like a sheet. All right. 0, 4, 8, C. You're in bug 0.
Next, let's do it together, 1, 5, 9, D, you're in bunk one. Get it? Okay?
2 — let's do it — 2, 6 — come on — A — keep going — E, you're in bunk two. Those guys in mod 4 are 2.
And let's do it together, ready? Fast — 3 — can you do it — 7 — keep going — B, F, you're in bunk three, enjoy yourselves — pretty cool.
All right. And all I was doing is looking at the lower 2 bits of those numbers to figure out where they go.
So these four blocks — by the way, memory can't stop. I show memory here stopping at F. Memory could be all the way down to 32 gibi — 4 gibi, 4 gibi.
I got 32 in there — 4 gibi. 2 to the 32 is 4 gibi. I go to 4 gibi. This could be 4 gibi high, and it would still work.
All the blues — all the blues, one quarter of the whole guys are blues. They all mapped to that blue spot. It's kind of a little cyan-y, but that's it.
Now, what if we wanted a block to be bigger than 1 byte? Because if you think about it now, you know what this really means?
If — I mean, this kind of doesn't work at this level, because if I had any 32-bit value, it means a 32-bit values are being spread across the different cache spot.
Like if I load in a float, a float's 32 bits wide.
Well, that means that the lower 8 are here, and then the next one is at the red, and the next — that doesn't make so much sense.
So usually, we think of cache as being at least a word wide, just so I can load a float in that spot. Otherwise, the float's being split across.
That doesn't — I don't like that so much. So we want to think about larger 1 bytes.
But we're going to start teaching what cache is at a very basic level so you understand what this is. So for now, we're in this beautiful abstract padded world model right now.
Padded room, I can just walk around. I can't hurt myself in padded room in which we're just talking about bytes. We're just reading and writing bytes.
Don't worry about anything bigger than that for now, just to be easy. So now — again, we're just reading by bytes for now — again, the easier words.
Look at how it happens now. This direct map cache now says, I'm going to have an 8 — I've doubled my size. Look, my block size is now 2 bytes.
It's wide. 4 rows, 2 bytes each, it's 4 times 2 is 8. It's an 8 byte cache, okay? It's direct mapped, still the easiest kind of caches we have.
But you see how we're doing it? And this is critical, by the way. We're going to label — the lowest byte is the top right. It's almost like kind of a right to left.
If you were maybe eating corn like this. It's the opposite how we read a page or something. Here is the lowest byte of all of memory. Then it goes across.
That's the next byte. And then it goes back to down here, and that's the next one. So you kind of do this little ziggety zaggety thing as we read.
And as the block size gets bigger — remember, block size is the width of the cache, and it's still, again, drawing our memory the same width as the cache.
As I widen that block size, I'm going do the same thing.
I don't care how it is, the top right is going to be the least byte, the lowest byte of the lowest word of the whole thing, and I walk my way across.
I pack them in until, again, however wide that block size is, and I jump back. It's always going to be this way, this kind of ziggety zaggety kind.
So that's not different. As I change my block size, that won't change. So again, the whole blue thing moves up there.
But now when I ask for a byte, the controller has to figure out where it is. So now, it's a little bit more complicated. Is it always the lowest bit?
Let's see, if it's the lowest bit anymore now? I don't know if it is anymore. How do I figure out which goes where? We can almost have a design question here.
0, 0 — well, that's in 0. And 0, 1, that's this spot. That's this guy right here, okay? That's also in 0.
But now, 1, 0, that's in 1. And then 1, 1 is in 1. You see what I'm doing?
So it's not so much I'm looking at — let's look here — that somehow the lower bits are telling me where it is. It's almost like I'm ignoring this one, isn't it?
This isn't telling me anything. It's kind of like this is telling me. But in fact, there're obviously four of them, so it sounds like I need to be looking at these two bits.
So just as we're looking at this, it looks like it isn't always the lowest bits that tell me where to go.
As I have more larger block size than 1, I feel like I have to somehow skip some amount until I start counting.
And we're actually going to look at this in a second how that actually works. So I try to lead you like, wow, it's pretty simple looking at the bits.
It is simple, but it's not as trivial as looking at the least significant bits to tell you what row you're in. Okay.
So when we ask for a byte, again, the controller does it, finds out which — so I block it and loads it for us. That's what's beautiful about these things that are automatic.
How does it know the right one? We kind of talked about that, so that we talked about. How do we select the right byte?
So now, once I ask for it, how do I know which — is it the right blue — guy in blue? Is it the right blue guy or is the left guy blue?
I'm trying to return a byte. Which of these two that you just loaded — the controller did something for us — but which of the two blue guys do I want?
That's what we got to figure that out here. And in fact, that might have helped our numbers, actually. That column we crossed off, maybe that was a secret for what byte it was.
That's — I'm giving you a little hint of what's there. So for example, memory address 1, 1, 1, 0, 1. Okay. Well, what's that?
By the way, what's 1, 1, 1, 0, 1 — really fast, really fast. See, you got to know that faster than that. You were too slow. Here's how I did this.
1, 1, 1 is 7. 1, 1, 1, 0, 0 means 7 has been shifted to the left by two spots — that's times 4 — 7 times 4 is 28, plus 1 is 29.
So in my head, you give me 1, 1, 1, 0, 1, I'd say 29. You're like, how do you do that so fast?
I was not adding 16 and 8 and — I wasn't doing that. I got to 29 by saying, oh, that's 7 times 4, 28 plus 1 is 29.
So think about how to do this faster.
So you get to some interview and they give you some bits and you're playing with bits much more fluently by looking at how to think of this.
So 1, 1, 1, 0, 1 29, really fast, right? Pretty cool — neat. 7 times 4 plus 1. Okay.
So what's actually happening? So how do I know which color block 1, 1, 1, 0, 1? This is kind of the main problem — 1, 1, 1, 0, 1 — how do we know?
Well, I was kind of telling you that somehow we're going to skip this lower guy, and we know what row it is from the 1, 0.
But then maybe this is the one which is — which left the right guy that does that.
So that's part of what we're trying to get to is, how do you figure out how to do this? And here's the interesting thing.
I think the bigger question isn't which blue, but the bigger question — I mean, which blue from the left to right point of view.
But the bigger question is, how do I know which blue it came from? So remember, the memory controller loaded a blue, aimed at my — and oh, oh, it says blue's filled.
I look at the bits and it's filled with bits. Remember, I can't tell by looking at a cache. Bits are bits. It could be garbage, it could be values.
So you can't just look there. So there's got to be something else that tells me that whether it was empty or not. We're going to get to that in a couple of slides.
But there's got to be a way to know which of these blues did I mean? Look, this blue is full of data. Yep, filled with good data, very happy, maybe that's even a picture.
So there's a picture there. Could be garbage — that happens to be a picture, or it could be a picture. Whatever, somehow there's data there.
But I'm asking myself, was it from this guy, or was it from this guy? I have to know which one that is to be able to know that I saved myself time.
Or do I have to go grab another blue and replace that one? So what do you do at baggage claim?
There's a great sketch which — there's a funny sketch I saw on YouTube in which a person says, I'd like to find my bag. And the person says, you have to describe your bag.
Yeah, it's a roll on, it's black. Like every other bag in the world? Oh, yeah, sorry, it's got a toothbrush in there. Again, like every other bag in the world?
Oh, yeah, sorry, it's got two wheels. Again, right? It's a very funny sketch. So part of what I'm asking is, how do you distinguish your bags when you pick them up at the airport?
You're flying back from home. Welcome back to Cowell. It's late August. Welcome back first week of classes.
Your bag — get your bag. They're all identical black bags. There's some law that says you have to have the same boring rectangular black roll on bag, carry-on.
Well, not a carry-on because you want to check it. But the point is you're checking your bag, you're getting it. How do you have — what's the secret in the airport?
All that story was to tell you, it's a tag. You have a little tag that tells me, oh, it's this one. No, no, it's this one.
So each of these blues should have a tag that tells you which — where did it come from?
Which of those kind of rows, which of those floors — you think of this memory is like floors — which floor did it originally come from to end up being in my — having a copy in my cache?
The tag is the key. Just like a tag on luggage, the tag is the key. So da, da, da, I introduce a tag.
And this is an 8 byte direct map cache with a tag. By the way, those words meant nothing to about 30 minutes ago.
So it's kind of cool that you're like, oh, now I know what this mean. So here's what happens. I get all the blues mapped to the blue. And what should go in the tag?
Well, let's think about, what would you put in there? Let's — how about this. Let's make up a new set of bits for each blue and just make them up.
So everybody — okay, here we go, everybody. All the blues, all the colors, every row in the original, make up a new special code that — we could do that.
Maybe you were to design that one. That's not as efficient as what they kind of already have their address, at the very least, which is usually the address comes with it, right?
Let's just use that. That doesn't make any sense. So let's just use the addresses. And then you're going to say to yourself, well, do we actually need the entire address?
And we didn't — some of the address tell us we were already blue. Maybe 2 of those bits told us that we were blue anyway, right?
If I'm blue, I know that 2 of those bits are 0. And we know that it's not the least significant 2 but the 1 over. So I don't need those 2 bits, right?
And you remember the least significant bit actually was the one that maybe told me which of the blues — is it this guy, is it this guy, or is it this guy?
That's the least significant bit tells me which column I'm in in my cache. So I don't need that bit, either, because that just tell me there. But I probably need everybody else.
So in fact, here's why I think about it. It's really interesting.
When we were — let's go back in time again. We were branch addressing. And remember, you can branch address and branch to every other byte. And that's neat.
You can jump to any 16-bit value. Every other place in memory you could branch to. Not everyone, but every other one. Did we store that?
Do we store the raw — did we store when we stored the branch, the actual branch, did we store to the byte level? We didn't.
We stored it so that the number 1 means the next valid thing I could go to. 2 is 2 over from the most valid thing I could go to.
So I didn't store all the bits. I didn't store all of my throwing away. Anything that was redundant, they all — by the way, they all would have been zeros.
If I'd stored all the bytes, it would have been zeros in that column. Why would I store all zeros? I never store anything if it's all the same value.
That's silly.
So here, all of these guys have something consistent, which is, they all have everybody here — everybody that's here, this — everybody that's ever here has the lowest 3 bytes I don't really care about.
Because the lowest byte is either 0 and 1, telling me, did you really want this one or this one? And the next 2 bytes tell me it was blue.
So everybody has the next 2 bytes the same. And this byte is either a 0 or a 1. Either way, I don't care about those guys.
So is there another way to do this where if I don't care, I kind of in a way — this is a fun way to think about this.
What if I just count by cache number? Like what do you mean cache number? I think — I don't know. I think I invented this term cache number.
It says, take the cache. Here's my cache. Whatever size it is, draw the same size here and label from 0 and 0. And the next one, draw another cache and label it 1.
And keep doing this, keep — for the whole — for the rest of the whole — of all memory. Go ahead. I'll give you time. 32 gibi, keep coming — 4 gibi.
I keep thinking 2 to the 32, or 4 gibi. Go to the bottom and, literally, make these squares and label them all. The guy here, here I'm calling the cache number.
And I claim that everybody in the first cache, everybody from 0 to 7, would have — everybody from 0 to 7 would have cache number 0. I claim that.
And I say I claim that meaning, the bits that are left after I throw away the rows, we call it an index labor, those 2 bits that tell me which row I'm in, and whatever bits that tell me what column I'm in, if I throw those away I'm left with I call the cache number.
And that's what I want to have my tag, the cache number. So that's the idea.
And again, I just mentioned this, it's useful to draw memory the same width as — if you do this, you will be in a great space for doing any problem on cache is to understand this.
And so I cross those off so — and I write whatever bits are left, which is the cache number. Where do they come from? If you look at this, 2 is here.
Look, this was 2. That's cache 0. So that's 0. 14 was here.
Here's 14 somewhere in there. That's cache 2. See that? I just keep doing that, et cetera.
So you end up having cache number as your tag, and that is the bits that you care about. Because other bits were either what row or what column, but I'm still in the cache.
I don't care about those. So that's it. I'm left.
I now have the idea that if I look at a generic address, I can now tell you in a generic direct map way, which bits went where.
And remember, sometimes the block size is more than 1. When the block size is 1, some of these values go away. For a generic problem, I have a block size.
The previous problem had a block size 2 of 2 bytes. Maybe it's much larger than that. So I need some number of bits tell me which column in there.
I got to know which row I'm in. And the rest of them is my tag, my cache number. That's the idea. I divide that memory into three fields.
Tag, which is the upper bits. Tag is always the upper bits, okay, that's the ones — the lower guys tell me which row and column. Upper bits are my tag, that's my cache number.
From the last time you — remember, the index was which row I'm in, and that's which block I'm in.
And the lowest set of bits tell me which byte I'm in, which byte or which word I want. And that's which column I'm in. And that's it. That's the big idea.
Each of these fields are read as unsigned values. There's no sign valued here. It goes from 0 to all ones.
And we usually start — by the way, if you look at this, it's listed from left to right, T, I, and O. But we don't think of that way.
We typically think of working with the cache by going with the I first.
We go to the middle first, which is weird, because I like ignore the upper bits, the middle bits, and kind of spread them out. Okay.
The other way, the good part of the pie is right here. Take the side — take the crust off and I get the stuff in the middle. My index is what row I'm in.
That's where the action is. So I go to my index. What's the action? What row am I in, okay?
So what block am I in? Then once I'm there, I'm going to see which byte I want, and that's the offset. Now, that's not the order.
Usually, it's index tag offset — we'll get to that in a second, the algorithm for this. And the tag is the remaining bits.
The offset tells me which column, which byte or word I want.
I mean, a general is what byte I am, but if I'm reading about only words at a time, the lower two guys would be 0, if I want that.
Index is which row I'm in. Offset is what column I'm in. And the tag is the remaining part, always the upper set of bits, to check to see where did it come from.
Did it come from the place I wanted to? Yes. Therefore, it's there already. And you'll see this when we do an example, all these things will become crystal clear, hopefully, okay?
So the tag is remaining bits after I've taken the index and the offset away from them. And I came up with this mnemonic, I think. I don't know.
Maybe other people did, but I came up with this — I haven't heard anybody else use this mnemonic so I kind of — I want to take credit for that.
And in Spanish, the word for Uncle is tío. Hey, Tío Dan. So — and I always think of myself as a fair bit avuncular, like an uncle.
So remember this, Tío Dan's mnemonic, Tío Dan, T-I-O, Tío Dan. Okay? Uncle Dan. Tag, index, offset, left to right — T-I-O — tag, index, offset.
And here's a way to think about caches in general. Here we go.
The lowest set of bits, the index and offset, are what determine the area. That's the overall area. Why? Because the offset tells you the width.
I try to color code this with you. If you're color blind, I'll try to — I'll show you this here. But this is blue here for this, and this is a little green.
And it says, this is the index. And this tells me how many rows I have, okay? So that's — and that is just pure number of blocks. That's the unit, a number of blocks.
The unit of the offset is the bytes per block. I'm thinking about how many columns I have. Well, it's bytes per block is telling me that.
And if I take the number of blocks, which is the height, to bytes per block, which is the width, blocks times bytes per blocks, the blocks cancel, I get bytes.
So when I multiply them together, I get the area in bytes. That's it. That's how we work with it. And the tag is whatever is left.
So that's the big idea. The big idea — oh, by the way, this is important.
Don't forget that if I take 2 to the H and multiply by 2 to the W, I get 2 to the quantity H plus W. You're like, Dan, I get that.
Yeah. But we're going to be talking about height as not just a number like 512. I'm going to say something like 2 to the 9th. Like I should draw like a 9.
And I'm going to say, well, what's the width? Well, I might say 2 to the 6th. And I'd say, quickly tell me the area. Tell me how big your cache is.
And you quickly, in your head, say 9 plus 6 is 15, 2 to the 15 is 32 kibi. You got a 32 kibi cache there, Dan.
So I want you to be really fast by that. I gave you a lecture — several lectures ago — on being able to be fast by that. 2 to the 9th is 512.
2 to the 6th is 64.
And I don't want you to sit down, all right, 512 times 64, let's see, carry the one — I'm not sure, and you're kind of like to take your pencil and kind of like carry the 1.
I don't want you do that. 9 plus 6 is 15. 2 to the 15, 32 kibi. It's a 32 kibi cache.
I want you to be fast like that, which is why I mentioned this, and it's also why I mentioned the idea of being able to be fluent with these numbers.
2 to the 15, you should be very fast, okay?
And by the way, you can imagine, I might ask a question like, oh, I don't know, if my cache size is — my cache size is 32 kibi, and I have an index — uh-oh, and see, now we're playing with this.
I have 9 bits of index, what's my block size? Oh, see, I just asked that — I just flipped the whole thing.
So I'm thinking, okay, 2 to the 15 divided by 9 bits, that's 2 to the 9th rows.
15 to the 15th — by the way, there's the equivalent of this of like, well then, 2 to the H plus W minus divided — so I divided by 2 to the H. If I divide both sides of this, it's 2 to the W.
So I say, okay, I got a 32 kibi cache. I've got 9 bits of index. That's 2 to the 9th. I'm thinking 32 kibi, or K to the 15.
I got 2 to the 9. 15 minus 9 is 6. 2 to the 6th — oh, I got 64 bytes wide block — fast.
That's the kind of thing that we're going to ask you to do and be able to be fluent in.
So hopefully, this lecture gives you a little bit of a — this lecture combined with the other lecture where I told you to be fluent in those numbers, lets you realize that we're going to be talking about 2 to the power for these things.
And the number of bits I have tells me I have 2 to those rows. If I have N bits, or I bits for the index, it's 2 to the I, different rows.
If I have O bits for the offset, it's 2 to the O bytes in that block. That's the idea.
So each of these guys is going to be a function of the — you're going to be — I'm going to ask you to be fluent between the bits to the number of rows and number of columns.
And then overall, again, product of that is the overall size of my cache. Because that — we're going to be — a lot — that's right. You cannot beat an exam.
And this is back in the days when we didn't have open book exams and untimed exams.
But you can't be at a cache question where, let's say, 2 to the 9th, and they're writing 2 to the 9th.
It's — okay, 64 times 2 to the — look it up, multiply it, no — fast, fast, fast.
So we're encouraging all of our folks — you didn't really need it before now, but as we start working cache problems, you're going to need it and it definitely helps.
It definitely helps not to be stalled on kind of some of these simple arithmetic, okay? That's it. We'll see you at the next section. Thanks so much.
Đă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.