YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 24.4 - Caches I: Locality, Design, Management

[CS61C FA20] Lecture 24.4 - Caches I: Locality, Design, Management — Transcript

by CS 61C Departmental · 2,778 words · 394 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back
0:02as we think about how we would design
0:04our cache we still only have a very
0:05rough idea with what this thing is
0:07there are a lot of parameters to it
0:09there's some design parameters to it we
0:10understand what locality means and give
0:12you some new so a little bit a couple of
0:14dictionary words that we're going to be
0:15teaching you here
0:17and also understand how to manage this
0:19cache so let's actually dig deeper and
0:20try to build this an architect kind of
0:22specking it out like how would you spec
0:23this thing out that we're trying to
0:24build that gives that what we had the
0:26last lecture with which is you know this
0:28the speed of the smaller triangles at
0:30the at the size of the lower ones so um
0:32let's design some of these things
0:35so first thing first i think i won't say
0:38okay maybe i will say the fifth time
0:39copy caches always contain a copy of the
0:42lower levels said that um
0:45memory contains copies of disk we
0:46mentioned that before also
0:48here's a new here's the new words caches
0:51work on the principle of
0:53temporal
0:55and spatial locality
0:57temporal means time spatial means space
1:00the idea about temporarily says well if
1:03i used it
1:04recently if i just used it recently
1:05chances are i'll use it again
1:07pretty soon okay if you just use it at
1:10you know time t equals zero you use some
1:11piece of data
1:13chances are
1:14higher that you use that data again
1:16versus another random data i mean let's
1:18think about that that's useful and so
1:20that's the whole idea of having this
1:22recent called list if you called some
1:24number you're probably going to want
1:25that number in the future maybe not
1:26maybe not maybe it's a one-timer and
1:28that's true for data too it could be a
1:29one-timer but you know all things being
1:31equal
1:32it's nice to have a recent copy in case
1:34i happen to write something a couple
1:35times if i have a loop in the array
1:37guess what i'm hitting that array
1:38oftentimes it's nice to have that i'm
1:40calling you know i'm calling my plumber
1:42because he's never answered the phone
1:43it's nice to have his you know my
1:45plumber's number there
1:48spatial locality is about space it says
1:53if i access a particular place of memory
1:55but it acts as a place of memory
1:58boy it turns out that i don't just
2:00usually as a usual there's a lot of
2:02things are generalizations i usually
2:03don't randomly hit memory i'm actually
2:06going to mention at some point the worst
2:08thing you could do with a cache in which
2:10you actually are randomly hitting memory
2:13but let's say that's not that degenerate
2:15case most of the time i hit memory in a
2:17loop where i'm kind of processing
2:19through it and doing something so the
2:20chances are probably going to hit a
2:22neighbor at some point after that
2:24so that's the idea the idea is spatial
2:27locality says if you hit a memory
2:29location at some spot
2:31you're probably going to visit their
2:32neighbors at some point soon temporal
2:34locality says if i used any piece of
2:36data i probably will use it again it'd
2:37be nice to keep that local so i have it
2:39easy and and fast for future accesses
2:42that's the idea that's the pro principle
2:43of these two two guys
2:46so what that means for temporal locality
2:48is
2:49that's the by the way temporal locality
2:51is the entire idea of a cache it says
2:55have the thing that you just recently
2:57used
2:58well store that so if you just access
3:00somebody i literally have one memory
3:02access well remember it remember and
3:04keep it close to you in case you need it
3:05again that's what the tempo that's what
3:08the default behavior of a cache is
3:10always to have temporal locality it
3:12means i've got a copy so that i can use
3:13it again if i ever even if i have a
3:15recently called list of one that's still
3:18if i need to call that number again
3:19because they didn't pick up i've got it
3:20right there that's the idea so basically
3:22every cache unless there's some
3:24parameters we tweak i'll talk about
3:25later that don't have that every cache i
3:27have
3:28supports temporal locality it means i
3:30keep a copy so you can use the guy you
3:32just used in the future
3:35spatial locality says
3:37when you go out to get stuff from memory
3:40if i'm going to sacramento it's like
3:42if i were going to sacramento i had all
3:44these pieces of paper written down with
3:45all these other passwords there
3:47i might use another password soon if i
3:49maybe i'm changing my because i moved i
3:51have to change you know log into all my
3:53banks to ch to tell them all that i
3:54moved so if you're going to sacramento
3:57anyway
3:58how about bringing back some of the
3:59things from some other neighboring
4:01pieces of paper around when i was
4:03working on that paper with that password
4:05i probably was also changing my because
4:06maybe i got hacked or something so i
4:08have the other ones for this important
4:10banks around nearby grab the whole table
4:13i'm sure you've done this you've got to
4:14watch a sporting event like the super
4:16bowl and your friend says i'm going to
4:17the fridge you guys want anything yeah
4:19get me and so while you're going all the
4:21way to the fridge if you're going to go
4:23and make the effort get stuff you know
4:25grab me a couple of sparkling water not
4:28no i think good things you would have
4:29because people are under 21 and then you
4:31bring it back and you'd have the thing
4:33so if you're going anyway bring some
4:35neighboring stuff there that's what
4:36space locality is temporal says just
4:38have a most recently used one so i got
4:40it ready that's almost all caches
4:42basically every every cache and spatial
4:44says when you don't just grab one thing
4:46grab a couple of neighbors while you're
4:47there and there's some details while we
4:48do that that's the idea temporal and
4:50spatial locality two new words
4:52as we think about designing our cache
4:54again we're trying to spec this thing
4:55out we need to have this thing that
4:56operates at the speed of the small guy
4:58but at the size of the big guy and it's
5:00going to be a copy we have to ask
5:02ourselves well
5:04how do i know as i have these spaces
5:05these are let's let's say i have a
5:06recent call list okay i've got some
5:08spots i've got maybe 10 spots let's just
5:09make some easy simple numbers i've got
5:1110 spots
5:12um how do i know the original numbers i
5:15mean maybe i have the numbers but how do
5:16i know in memory where they originally
5:18came from so if i need to write to them
5:20i don't just have the numbers i need to
5:22be able to somehow
5:23access some so
5:25as i made a memory access i need people
5:26to know that no if i've got it in my
5:28recently called list it's here don't go
5:30there because i've got a copy of it use
5:32the one i've got that's really fast so i
5:34somehow need to store
5:35where i grabbed it from if you think
5:37about this and then how i remember that
5:39somehow so part of it is where did it
5:40come from if i grabbed it from that part
5:42of memory and here's the copy of it well
5:44how do i know when i go it again the
5:45system needs to know oh if you're going
5:46for the same spot i got it first already
5:48so how do you tell the system and how do
5:50you remember that
5:51um
5:52overall how do you know what's in the
5:53cache
5:54how do you
5:56if bits are just bits how do i know if
5:57these bits were random garbage bits
6:00remember we talked about something
6:02like an array being initialized to
6:04garbage well if i don't know it i don't
6:05know if those are if the garbage is data
6:08that's good or garbage is there a
6:09sentinel value i reset everything to
6:11okay reset the thing give it some
6:13sentinel value and that i'll know if
6:15it's the sentinel that is some
6:18characteristic value that i'm going to
6:20have no good value would have this value
6:21so i reset it to the sentinel value and
6:23i'll know like negative one or something
6:25if it's all positive numbers or
6:26something if it's an int and i'll say
6:28okay set the whole array to negative one
6:30that way i'll know if i've set you know
6:31if i stored something there or not so
6:33how am i using it to know which elements
6:35are in which elements are not which
6:36which are blank i haven't sorted
6:38anything there
6:39and how do i quickly get them how do i
6:40have to drop to like linearly search
6:42like how crazy would that be is it this
6:44one no this one is there a faster way to
6:46quickly get to it so i want to be able
6:48to get to it know what's there and then
6:50know where it came from that's kind of
6:51what we're talking about in our cache
6:52design kind of a fun space i almost
6:55i think
6:56this is just me reflecting on this i
6:58think it would have been fun to have
6:59this lecture where i stopped now and i
7:02send all the 61 students away for a week
7:04and they design caches because i bet you
7:06nine times out of ten you'd come up with
7:08whatever design i'm gonna teach you in
7:09the next thing so it's i'm kind of
7:11giving away the opportunity for this
7:13design challenge for people to come up
7:14with a new invention of how caches might
7:16work that might be more clever than the
7:18way they currently work so
7:20unfortunately i'm just going to tell you
7:21how we do it but there's an interesting
7:23space to allow you to just pause it so
7:24if you're watching this video pause it
7:26and then talk to your friends about
7:27let's if you didn't read a head in the
7:28book where you got the answer there try
7:30to design this thing what would it mean
7:32to have memory and then have this copy
7:34to know where it came from know what the
7:37values are here what they're initialized
7:38to know what's in it totally and then
7:40know how to how to find it in there so
7:42think about some design for that it'd be
7:44kind of fun to think about it faster
7:45maybe you can do a log search for it
7:47maybe it's even faster than that so
7:49think about how to design this to be
7:50able to have those all be fast and all
7:52be clear answers to these questions here
7:54nice right
7:56so
7:56here's the answer come now positive i
7:58could now unpause the video and come
7:59back uh no i'm not going to give away
8:01that i think i'm waiting a couple of
8:02slides
8:04this is just how we generally manage
8:05these high these levels of the hierarchy
8:07registers to memory
8:09how do we manage
8:11what how data moves between or how the
8:13copies of the data come from memory and
8:15go to registers you've done this already
8:17you know this answer
8:18the compiler does the work right you're
8:20either hand authoring risk 5 code or you
8:23write c which moves down to the compiler
8:26authoring the risk drive code for you
8:27but you know the load the loaf the the
8:31uh the load and stores that's how you
8:33move things in and out
8:35you wrote that right either the compile
8:36either wrote it because you did a memory
8:38access and that became risk five code or
8:40you hand authored it so you're doing the
8:41compiler does that so that's how that
8:43works how about cache to main memory do
8:45you have to manage that yourself
8:47actually here's what's cool
8:49don't need to worry about that at all
8:50that's handled by the system the cache
8:52controller does that for you that's neat
8:54so you can add this whole layer and not
8:57have to physically think about it it
8:59means the same program you had before
9:01if i have a machine with no cache just
9:03runs a lot slower
9:05if i add a cache i don't to change the
9:07program this is a big idea no need to
9:10change a program to to add this layer of
9:12the cache i change the system the system
9:14now manages it and works it all itself
9:16but the hardware does it for you now if
9:17you're going to be a hardware designer
9:19that's when you have to do it so think
9:20about taking upper division classes to
9:22learn how to make the make that work but
9:23that's kind of neat you don't worry
9:24about it from the programmer's point of
9:25view
9:27how about main memory to disk
9:30beautiful thing is that's not even
9:32managed by you either that's managed by
9:34the os and we'll learn about that when
9:35we get to virtual memory so save that
9:37for later but that's kind of neat now
9:39you could say well dan no i had a chance
9:42because when i was writing my program i
9:44could write a file or not yes
9:47you're right you explicitly could write
9:49your array to a file and read it from a
9:51file so you could still do it by the
9:52programmer's point of view but in terms
9:54of
9:55how the virtual memory pages which you
9:57don't know what that means yet work
9:59that's done by the os and we'll get to
10:00that we'll talk about virtual memory but
10:02there is some movement i'll give you a
10:03little i'll like see this conversation
10:06there is some movement from of data from
10:09memory to disk
10:11in and out of disk and that's like going
10:13past sacramento to even farther away
10:15we'll talk about that when we get to
10:16that but that is done by the os and
10:19again you learn more about 162 and we'll
10:20teach you a little bit more about it
10:21when we get to the vm lectures okay
10:24so here's the idea cache domain memory
10:26is the cache controller hardware
10:29and by the way there's some part of vm
10:30which is also kind of a cache
10:32but you don't even know what that word
10:33means and so we'll just skip that for
10:34now but come back to this slide when you
10:36learn from me like oh well you know what
10:37this thing called the tlb that's a cache
10:40too so we'll figure out what that is
10:41later
10:43so in conclusion this is again still
10:44setting these things up we're setting
10:46the design space for the future
10:48caches provide this remarkable illusion
10:50this more abstract i like abstraction
10:52better than illusion but i'll take it
10:53i'll take you the one
10:54it's an abstraction that lets you think
10:56like an illusion let's do the i did that
10:59both lets you think about
11:01accessing data at the speed of
11:04much things a speed of something much
11:06faster than memory but at the size of
11:08memory so all of a sudden memory card
11:09basically abstractly memory got faster
11:12that's pretty cool so i'm going to be
11:14right reading and writing memory and all
11:15of a sudden the reading rights are what
11:17this computer's way it's just sprightly
11:19today yeah because they added a cache
11:20overnight oh but you don't need to worry
11:22about program doesn't worry about it but
11:23all of a sudden i get much faster access
11:25to memory and we can talk about even how
11:28later how to write our code to optimize
11:30for the cache that's a whole nother
11:31conversation and a very rich
11:33conversation how to if i knew there was
11:35a cache what would i do differently from
11:36a programmer ah yes
11:38sometimes you can peek below the hood
11:40and see what hardware i'm running on to
11:42then change your code to optimize for
11:43that that's actually what's called
11:45optimization is called optimization is
11:46often how do i lift lift the hood up oh
11:48that's what hardware running okay put
11:50the hood back down now i'll change my
11:51code same does the same thing it just
11:53does it in a different way to optimize
11:55for the cash we'll talk all about that
11:56later okay see the next lecture thanks

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 24.4 - Caches I: Locality, Design, Management by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,778 words across 394 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.