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
And welcome back. As we think about how we would design our cache, we still only have a very rough idea what this thing is. There are a lot of parameters to it.
There's some design parameters to it.
We understand what locality means and give you some new — just a little bit a couple of dictionary words that we're going to be teaching you here — and also understand how to manage this cache.
So let's actually dig deeper and try to build this and architect. We're kind of speccing it out.
Like, how would you spec this thing out that we're trying to build that gives that — what we ended the last lecture with, which is the speed of the smaller triangles at the size of the lower ones.
So let's design some of these things. So first thing first — I won't say it. Okay, maybe I will say the fifth time.
Caches always contain a copy of the lower levels — said that. Memory contains copies of disk. We mentioned that before also.
Here's some new words — caches work on the principle of temporal and spatial locality. Temporal means time. Spatial means space.
The idea about temporal locality says, well, if I used it recently, if I just used it recently, chances are I'll use it again pretty soon, okay?
If you just use it at time t equals 0, if you use some piece of data, chances are higher that you use that data again versus another random data.
I mean, let's think about that. That's useful. And so that's the whole idea of having this recent called list. If you called some number, you're probably going to want that number in the future.
Maybe not, maybe not. Maybe it's a one timer, and that's true for data too — could be a one timer.
But all things being equal, it's nice to have a recent copy in case I happen to write something a couple of times. If I have a loop in an array, guess what?
I'm hitting that array oftentimes. It's nice to have that — I'm calling my plumber because he's never answering the phone. It's nice to have my plumber's number there.
Spatial locality is about space. It says if I access a particular place in memory — [BLOOP] --access a place in memory, well, it turns out that I don't just — usually.
This is usual. There's a lot of — all these things are generalizations. I usually don't randomly hit memory.
I'm actually going to mention at some point the worst thing you can do in a cache, in which you actually are randomly hitting memory. But let's say that's not the degenerate case.
Most of the time, I hit memory in a loop, where I'm kind of processing through it and doing something. So the chances are probably going to hit a neighbor at some point after that.
So that's the idea. The idea is spatial locality says, if you hit it, a memory location at some spot, you're probably going to visit their neighbors at some point soon.
Temporal locality says if I use any piece of data, I probably will use it again, and it'd be nice to keep that local so I can have it easy and fast for future accesses.
That's the idea. That's the principle of these two guys. So what that means for temporal locality is — by the way, temporal locality is the entire idea of a cache.
It says, have the thing that you just recently used. Well, store that. So if you just access somebody, I literally have one memory access. Well, remember it.
Remember it and keep it close to you in case you need it again. The default behavior of a cache is always to have temporal locality.
It means I've got a copy so that I can use it again.
Even if I have a recently called list of one, that still, if I needed to call that number again because they didn't pick up, I've got it right there.
That's the idea. So basically, every cache, unless there's some parameters we tweak we'll talk about later that don't have that, every cache I have supports temporal locality.
It means I keep a copy so you can use the guy you just used in the future.
Spatial locality says, when you go out to get stuff from memory — if I'm going to Sacramento, it's like if I were going to Sacramento, and I had all these pieces of paper, written down with all these other passwords there, I might use another password soon if I — maybe I'm changing my password because I moved.
I have to log in to all my banks to tell them all that I moved.
So if you're going to Sacramento anyway, how about bringing back some of the things from some other neighboring pieces of paper around when I was working on that paper with that password, I probably was also changing my — because maybe I got hacked or something, so I have the other ones for these important banks around nearby.
Grab the whole table. I'm sure you've done this. You watch a sporting event like the Super Bowl. And your friend says, I'm going to the fridge.
You guys want anything? Yeah, give me.
And so while you're going all the way to the fridge, if you're going to go and make the effort, get stuff, grab me a couple of sparkling water, not the good things you'd have because people are under 21, and then you bring it back, and you'd have the thing.
So if you're going anyway, bring some neighboring stuff there. That's what spatial locality is. Temporal says, just have a most recently used one so I got it ready.
That's almost all caches, basically every cache. And spatial says, don't just grab one thing, grab a couple of neighbors while you're there. And there's some details of how we do that.
That's the idea — temporal and spatial locality, two new words. As we think about designing our cache — again, we're just trying to spec this thing out.
We need to have this thing that operates at the speed of the small guy but at the size of the big guy, and it's going to be a copy.
We have to ask ourselves, well, how do I know, as I have these spaces — so let's say I have a recent call list, okay? [MECHANICAL PURRING] I got some spots.
So I got maybe 10 spots. Let's just make some simple numbers. Got 10 spots. How do I know the original numbers?
I mean, maybe I have the numbers, but how do I know in memory where they originally came from? So if I need to write to them, I don't just have the numbers.
I need to be able to somehow access them.
So as I made a memory access, I need to be able to know that, no, if I've got it in my recently called list, it's here.
Don't go there, because I've got a copy of it. Use the one I've got that's really fast.
So I somehow need to store where I grabbed it from — think about this — and then how I remember that somehow. So part of it is, where did it come from?
If I grabbed it from that part of memory, and here's the copy of it, well, how do I know when I go in again, the system needs to know, oh, if you're going for the same spot, I got it first already.
So how do you tell the system, and how do you remember that? Overall, how do you know what's in the cache?
If bits are just bits, how do I know if these bits were random garbage bits? Remember, we talked about it sometimes being — like, an array being initialized to garbage.
Well, if I don't know it, I don't know if the garbage is data that's good or garbage. Is there a sentinel value I reset everything to?
Okay, reset the thing, give it some sentinel value. And that, I'll know if it's the sentinel, some characteristic value that I'm going to have — no good value would have this value.
So I reset it to the sentinel value, and I'll know, like negative 1 or something if it's all positive numbers or something — if it's an int, and I'll say, okay, set the whole array to negative 1.
That way, I'll know if I stored something there or not. So how am I using it to know which elements are blank, I haven't stored anything there? And how do I quickly get them?
How do I have to — do I have to, like, linearly search? Like, how crazy would that be? Is it this one? No.
This one? Is there a faster way to quickly get to it? So I want to be able to get to it, know what's there, and then know where it came from.
That's kind of what we're talking about in our cache design. Kind of a fun space.
This is just me reflecting on this, I think it would have been fun to have this lecture where I stop now, and I send all the 61 students away for a week, and they design caches.
Because I bet you 9 times out of 10, you'd come up with whatever design I'm going to teach you in the next thing.
So I'm kind of giving away the opportunity for this design challenge for people to come up with a new invention of how caches might work that might be more clever than the way they currently work.
So unfortunately, I'm just going to tell you how we do it. But there's an interesting space to allow you to just pause it. So if you're watching this video, pause it.
And then talk to your friends about — if you didn't read ahead in the book where you got the answer there, try to design this thing.
What would it mean to have memory and then have this copy to know where it came from?
Know what the values are here, what they're initialized to, know who was in it totally, and then know how to find it in there. So think about some design for that.
It'd be kind of fun to think of a faster — maybe you can do a log search for it. Maybe it's even faster than that.
So think about how to design this to be able to have those all be fast and all be clear answers to these questions here. Nice, right? So here's the answer.
Now unpause the video and come back. No, I'm not going to give it away. I take it away in a couple of slides.
This is just how we generally manage these levels of the hierarchy. Registers to memory.
How do we manage how data moves between — or how the "copies" of the data come from memory and go to registers? You've done this already. You know this answer.
The compiler does the work, right? You're either hand authoring RISC-V code, or you write C, which moves down to the compiler authoring the RISC-V code for you.
But the load and stores — that's how you move things in and out. You wrote that, right?
You either wrote it because you did a memory access, and that became RISC-V code, or you hand authored it. So you're doing — the compiler does that. So that's how that works.
How about cache to main memory? Do you have to manage that yourself? Actually, here's what's cool — don't need to worry about that at all. That's handled by the system.
The cache controller does that for you. That's neat. So you can add this whole layer and not have to physically think about it.
It means the same program you had before — if I have a machine with no cache, just runs a lot slower. If I add a cache, I don't have to change the program.
This is a big idea. No need to change the program to add this layer of the cache. I change the system.
The system then manages it and works it all itself, but the hardware does it for you. Now, if you're going to be a hardware designer, that's when you have to do it.
So think about taking upper division classes to learn how to make that work. But that's kind of neat that you don't have to worry about it from the programmer's point of view.
How about main memory to disk? Beautiful thing is that's not even managed by you either. That's managed by the OS, and we'll learn about that when we get to virtual memory.
So save that for later, but that's kind of neat. Now, you could say, well, Dan, no, I had a choice, because when I was writing my program, I could write a file or not.
Yes, you're right. You explicitly could write your array to a file and read it from a file. So you could still do it by the programmer's point of view.
But in terms of how the virtual memory pages, which you don't know what that means yet, work — that's done by the OS, and we'll get to that.
We'll talk about virtual memory. But there is some movement — I'll give you a little — I'll, like, see this conversation.
There is some movement of data from memory to disk, in and out of disk. And that's like going past Sacramento to even farther away. We'll talk about that when we get to that.
But that is done by the OS. And again, you'll learn more about it in 162, and we'll teach you a little bit more about it when we get to the VM lectures, okay?
So here's the idea — cache from memory is the cache controller hardware. And by the way, there's some part of VM which is also kind of a cache.
But you don't even know what that word means, and so we'll just skip that for now. But come back to this slide when you [INAUDIBLE] me say, oh, well, you know what?
This thing called a TLB — that's a cache too. So we'll figure out what that is later. So in conclusion — this is, again, still setting these things up.
We're setting the design space for the future — caches provide this remarkable illusion, this abstract — I like abstraction better than illusion, but I'll take it. I'll take either one.
It's an abstraction that lets you think, like an illusion, lets you [INAUDIBLE] both the — lets you think about accessing data at the speed of something much faster than memory but at the size of memory.
So all of a sudden, memory got — basically, abstractly, memory got faster. That's pretty cool. So I'm going to be reading and writing memory.
And all of a sudden, the read and writes are — this computer's way — it's just sprightly today. Yeah, because they added a cache overnight.
[GASPS] Oh, but you don't need to worry about it. Programmers don't worry about it. But all of a sudden, I get much faster access to memory.
And we can talk about later how to write our code to optimize for the cache. That's a whole nother conversation and a very rich conversation.
If I knew there was a cache, what would I do differently from a programmer — ah, yes.
Sometimes, you can peek below the hood and see what hardware I'm running on to then change your code to optimize for them. That's actually what's called optimization is called.
Optimization's often — how do I lift the hood up? Oh, that's what hardware I'm running. Okay, put the hood back down. Now I'll change my code — does the same thing.
It just does it in a different way to optimize for the cache. We'll talk all about that later, okay? See you in the next lecture. Thanks.
Đă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.