YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 27.2 - Caches IV: Block Replacement with Example

[CS61C FA20] Lecture 27.2 - Caches IV: Block Replacement with Example — Transcript

by CS 61C Departmental · 3,314 words · 517 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now let's take a look
0:03at what block replacement might mean and
0:06actually see an example
0:07of thinking about who might get kicked
0:09out when things get full
0:12so block replacement policy what do we
0:14know about caches we have a knob that
0:16knob can either go
0:17to um if it's an m total if it's
0:20m total blocks in the cache and it's m
0:23away
0:24it's n way set associative when n is one
0:27direct mapped when n is
0:28m fully associative and in the middle
0:30like two or four or eight
0:31i'm that i'm n way set associative so
0:34when i'm when
0:35n is one and i'm direct mapped is it's
0:38clear what we do
0:39if i have to replace a block it's the
0:40block that used to be there because
0:42everybody
0:42every color blue blue blue blue maps to
0:45the blue guy and if
0:46this is the one that's supposed to be
0:47there and somebody else who does tag
0:48doesn't match
0:49get that guy out easy
0:52both enway set associated and fully
0:54associative are n-way
0:56within it's set and fully fully for the
0:58whole cache
0:59fully associative within either the set
1:01or the whole cache respectively
1:03so it means that what happens
1:06well if i have a choice what do we write
1:08the incoming block it's remember fully
1:09associative
1:10well first of all let's let's find a
1:13blank spot i mean blank is weird because
1:15there's bits everywhere but
1:16let's first check the valid bits see if
1:18there's any rows
1:20any blocks that are invalid blocks that
1:23are garbage
1:24and they're cold in some sense that that
1:26block is empty
1:27put in that spot don't do any work don't
1:29have to kick anybody out
1:31but what happens when they're all full
1:33what happens when
1:35they're all valid but none of the tags
1:37match and we got to bring somebody else
1:39in
1:39well folks ain't no free lunch
1:42somebody's got to go
1:43this one has to go in somebody has to go
1:45out we can't do anything else
1:46so how do we decide and that's called
1:48the block replacement policy the
1:49application policy
1:50when we replace a block because we're in
1:52a fully associated window
1:54either within a set or within the whole
1:55cache if it's fully associative and the
1:57whole cache
1:58how do we kick out some guy if they're
2:00all full but none of them are the same
2:01tag as the one i want to bring in
2:04so the most common thing we do is the
2:08least recently used most recently means
2:10i
2:11just touched it fresh is hottest right
2:12there least recently that's the one with
2:14cobwebs
2:15least recently means the one that hasn't
2:17been used at all
2:18so who got in who back who got in back
2:21who got in back in the
2:22early days of of yesteryear and hasn't
2:25been touched since
2:27and somehow we have to remember hey
2:28let's talk about this so
2:30why would we do let's just talk about
2:31why we even do this why would we do lru
2:34because temporal locality you know
2:37the temperature says if i access a
2:39particular memory location chances are
2:41pretty high that
2:42all things being equal i'm going to
2:43access that same thing again i'm
2:45probably going through an array or maybe
2:46i'm doing a sum and that
2:47maybe i'm adding to one element of the
2:49array is the sum and i keep
2:50taking all the elements putting in this
2:51element the first element is going to be
2:53the sum as i add up all these guys
2:54keep stuffing in this guy well that guy
2:55gets hit a lot so
2:59that's what lru is about lou says if you
3:01visited before
3:03i need to kick out the oldest one that
3:06i'm probably not using
3:07and keep the ones that i am using again
3:09exploding temporal locality
3:11the downside is i now have to keep track
3:15of the relative order of things i've got
3:18four sets let's say four words that
3:19associated and i want to talk about them
3:20what's set now
3:21and let's say i touch them this guy
3:23first then this guy then this guy then
3:24this guy load them all in everything's
3:25happy i'm cash is very warm
3:27i'm going to just read it to these guys
3:29and all of a sudden i read a fifth guy
3:31well and who's the oldest one well i
3:33read one two three
3:34four this is the most recent i touched
3:37them
3:37one that was the oldest one then i
3:39touched that one then this one then this
3:40one that's the that's the newest one
3:41that's the oldest i'll kick this guy out
3:43so now this is the newest one but now
3:46this is the newest but now that's the
3:49second
3:50and this is the third and that's the
3:52fourth okay now now i love the thumb in
3:53who are they
3:54well it's the fourth and this guy has to
3:56go out and now who's it
3:58now this is the newest that's the second
4:01that's the third that's a so you can
4:02imagine i've got to keep
4:04four factorial kind of combinations of
4:08permutations really of what the ordering
4:11is and so
4:11four things the ordering that's four
4:13factorial that's 24 things i now need
4:15five bits
4:16go ahead have some fun trying to come up
4:18with the logic for
4:19how to update that it's almost like
4:22you're keeping a record a scratch book
4:24which is easy to do in software if i had
4:25this software cache really easy
4:27i can just do this all the software i
4:28have a set of ordering and give it a
4:29number and update
4:31the numbers easy harder much much harder
4:35to do in hardware
4:36so that's not easy to do even four way i
4:38said is very hard to do imagine eight
4:40way crazy right
4:41eight factorial but
4:44two way is really easy lru says if i
4:47grab
4:48if here's two here's two rows i grab
4:50this one well that's the one i have in
4:51grab recently so give this a bit called
4:53the lru bit points there
4:55points to zero or one this means this is
4:58the least recent if i just touch this
4:59one that's the least recently used
5:01very easy so you can use a single bit
5:03for two way
5:04love that so actually got to see the
5:05example in about two minutes to think
5:07about this
5:09fifo what does fifo mean you're here
5:10five for your computer science you think
5:11a queue right
5:12first in first in first out like waiting
5:15in the line for
5:16for check out of a grocery store and
5:19that says
5:20i'm gonna ignore the accesses okay you
5:22got loaded into the cache
5:24and you're chugging through and you're
5:25waiting and maybe other things are being
5:27filled up around you that's fine you're
5:28enjoying your time maybe people are
5:29accessing you
5:30but being accessed doesn't bump you to
5:33the front of the line this whole example
5:34i was doing here is whenever you get
5:35touched you get bumped to the front of
5:36the line you get reordered like
5:38that in a fifo model you just say no
5:40when you got loaded in that's the order
5:41and then
5:42you're the first one out it just feels
5:44fair in a way but it kind of ignores the
5:46temporal locality ignores the fact that
5:47i'm keep hitting this guy
5:48even though it was there well no
5:50eventually this even though i'm hitting
5:52every time sorry you get out wait but
5:53i'm hitting it every time or every other
5:55time nope
5:55this one and then somebody knew one and
5:57this one's something new and this one's
5:58something well keep this guy in this guy
6:00is obviously interesting
6:01nope sorry you're you're whatever you're
6:03in line next in line for being kicked
6:05out oh that's a bummer i was really
6:06being used a lot
6:07right that's not so happy or random
6:10random says
6:11you know what uh let's just kick out a
6:14random person and maybe we luck out
6:16and it turns out that you could run a
6:18trace we talked about how to run traces
6:19on this thing
6:20and set up a cache that has a random
6:22policy and it actually may do better
6:23than
6:24all of these that's what's fun about
6:25these whenever you whenever we're still
6:27talking about
6:28you know parameters or settings of
6:29caches if we're still talking about it
6:31then there might be still some
6:32application
6:34where that makes more sense to do it
6:35that way um
6:37you know i mean think about random you
6:38have to code they're ordering even
6:39software hardware you have to code the
6:41ordering don't worry about the queue
6:42you just pick somebody else random kick
6:44them out and so maybe you have
6:45not too bad performance with random so
6:47these are still three active
6:49at random certainly less used than an
6:51lru that which
6:52lru is the most common it's kind of at
6:55least but it's most common
6:57um but random is still out there so
6:59random is still a person
7:00a design choice as you're making your
7:02own caches so let's actually look at an
7:04example this will ground it once we
7:05actually work on this
7:06so we have a same two-way set
7:09associative cache
7:11four byte total so four bytes very small
7:14one byte blocks just we're talking about
7:16bites now we're back to the days or load
7:17bites
7:18but here's the idea it's two-way so that
7:21means
7:21two of those guys so let's look here
7:23this here's the picture so that means
7:26two of them and by the way all the reds
7:29are the even numbers if you remember a
7:31slide or two ago
7:32it it showed it was like red green red
7:34green red green
7:35and it mapped to two reds up top and two
7:38greens so it basically says all the even
7:40guys are going to be in red
7:41and all the odd guys are going to be in
7:44green
7:45and what's going to happen we're going
7:46to redraw this so these are both the red
7:49all the even guys all the even memory
7:51out memory
7:52accesses are going to go in the top set
7:54and all the odd memory access is going
7:55to go there that's the idea
7:57and we'll see what happens so we're
7:59gonna do very simple
8:00zero two zero one four zero and by the
8:02way here's the fun thing
8:04if i this is a great exam question i
8:06give you a cache and i say give me
8:08the access pattern to make it look
8:10really good well just hit the same one
8:12all the time right zero zero zero zero
8:14zero i'd load it in and now i've got it
8:15but maybe you're do something else and
8:17random kicks it out so think about
8:19if i tell you to construct the access
8:22pattern think about what that access
8:23point might be to make it look really
8:24good or really bad so you can do that
8:26that's a great question i might ask in
8:27an exam
8:28so here's my cache remember the top row
8:31is for even
8:31memory accesses and the bottom is for
8:34odd so i ask for zero this cache is
8:36cold stone cold so i got to bring that
8:38in and i don't care i'll just bring it
8:40into uh
8:40location zero and what i really this
8:43zero is really saying
8:44it's the data at location zero i'm not
8:46bringing literally the zero in
8:48this representation this picture says
8:50bring the memory
8:51it's really memo of zero is being
8:53predicted whatever was in memo of zero
8:54that goes there that's what just make
8:56sure you understand i'm not bringing the
8:57number zero in
8:58it's memo of zero but i'm showing it at
8:59zero just to make it easy here i've
9:01gotta set the lru bit which is the one
9:02that's least recently used it's the
9:04other guy
9:04because it's most this location zero is
9:07more recently used than location one so
9:09even though there's nothing there and
9:10the valve is turned off there i'm gonna
9:12set all of you there just to remind you
9:13that there's
9:14that's the lru side now i copied that
9:17down so that
9:17i kind of show you the the the time
9:19views of that
9:20and now i ask for two two is also an
9:22even number and
9:24two is not loaded in um i can check the
9:26tags so verify two's not there
9:28so i bring two i first check of all the
9:30in parallel i'm checking
9:32the two locations in parallel of two um
9:35i know it's a miss because location 1
9:38has its valid bit off
9:39and location 0 has a different tag the
9:41tag is for
9:42the 0 not for 2. so i am going to
9:46blink i'm going to bring it in and now
9:48i'm gonna
9:50set location this is by the way a great
9:52example if i were copying back and forth
9:53from zero to two
9:54they could both live there both of those
9:56memory locations could live there i
9:58could copy back and forth from zero to
9:59two this is again one of the benefits
10:01of even a two-way set associative guide
10:03so because i touch
10:04two last i'm going to make over and say
10:06you know if you have to kick somebody
10:07out and set zero kick out the zero
10:09because two is the freshest one
10:10and zero's the most stale kind of
10:12smelling a little bit too
10:14let's ask for zero again oh see well
10:17let's flip it again
10:18it's a hit yay zero and two are both
10:20there that's a hit
10:21we're going to move the lru bit over and
10:23now two is the oldest one because i most
10:24recently
10:25you touched this here we go one
10:29well i have yet to have an odd number so
10:31i haven't even touched set one yet
10:33so let's bring that into a set that's
10:34that really that whole set was cold
10:36so let's bring it into location zero and
10:38set our lou butt over
10:39all this is kind of making sense as
10:41we're working with this
10:43now i've got just copy that down again
10:45and now the last one
10:46i've got a four or a second to last one
10:48i got a four now here's an issue this is
10:50exactly why i was keeping track of my
10:52lru bit
10:54i look at both of those locations any
10:56valid bits off any blank spots really
10:58nope they're both valid all right well i
11:01wish i had boy i wish i had a way to
11:03kick to figure out what a block
11:04replacement policy is
11:06i have one i got four is not in there so
11:08the tags don't match
11:09and they're both valid which means
11:10that's exactly the case of kicking
11:12somebody old out
11:13and bringing my new four in there or
11:14memo4 in there
11:16who do i put it where do i put it i put
11:18it in
11:20the lru spot that single bit told me
11:22that's the guy you're gonna do that's
11:23the one who's the dustiest oldest
11:25most stank uh piece of memory
11:29most stank data from whatever piece of
11:31memory have so bring in
11:32memo four there and set the lru bit over
11:36whoops
11:36to the zero keep going
11:40now i'm going to ask for a zero yay the
11:43zero didn't get kicked out
11:45i mean there was a little bit of an ally
11:46you bit question over there but zero's
11:47still there again zero is another hit
11:49so that's awesome if you remember let's
11:52go back to the day
11:54of this is the first first lecture i
11:56ever gave you the first
11:57like second lecture where i had a very
12:00simple blue red
12:01i forget the colors but there was only
12:02it was a four byte
12:04cache one direct map four byte
12:08direct map cache and it was blue so zero
12:11would have gone to the zero spot two
12:13goes here
12:14zero is a hit one's a miss okay
12:17four would have been a miss it was
12:20and because now it asks for zero again
12:23zero and four
12:24are both blue they would have pointed to
12:25the same spot this was better
12:28all it would have been the same it would
12:29be exactly the same zero miss
12:31two miss zero hit all that would have
12:33been the same so far
12:34one miss four miss it would have been in
12:38the olden days it would have said
12:400 missed because 4 and 0 would have
12:42lived in the same blue row
12:44but because 0 and 4 can both be here
12:46together
12:47this is a hit so that's that particular
12:49example was the same all up until that
12:51last
12:51zero in which i had direct map zero
12:54would have been a miss
12:55here it's a hit because zero and four
12:57both blue and the first picture that i
12:59showed you
13:00can both coexist happily and i could
13:02very happily copy between zero and four
13:04in this guy i couldn't have in a direct
13:06map cache that's kind of the example we
13:08got there
13:10blue and now we set the all of your bit
13:11now what's really wonderful is there's
13:13a simulator i didn't write it
13:17um someone at umass wrote this corin i
13:20believe at umass wrote this amazing
13:22professor corn i'm sure
13:23i should give credit i don't actually
13:25know who who wrote this but i know that
13:26yours already is corn
13:27wrote this wonderful simulator and you
13:30can set the parameters of your cache
13:32and i just adjusted the parameters to be
13:34exactly this
13:35problem and then you can go in
13:38and set up the sequence the the
13:42the request show me the list of requests
13:44memory requests
13:45so i put in zero two zero one four zero
13:49and what this does is look what it does
13:51it color codes them
13:53as compulsory miss which means we talked
13:55about that before you gotta take the
13:57loss anyway
13:57it was you know it's cold you gotta take
13:59that miss anyway capacity miss
14:02that means if you only had more space
14:04you wouldn't have had that issue
14:05and conflict misses say well that would
14:08be nice but two guys are at the same
14:10spot
14:11watch this blue zero the first zero that
14:15was a
14:16compulsory miss then the next one two
14:19was a compulsory miss
14:21zero was a hit in this guy you saw that
14:23that zero was a hit
14:25one was a compulsory miss four again
14:28four was a conflict miss okay in this
14:32particular case and i kicked out
14:34the two there wasn't room to hold
14:37zero two and four in this cache that's a
14:40conflict
14:40miss so kick out two and it seems this
14:44even shows look
14:45kicked out the two and then bring back
14:49the zero and zero is a hit again so
14:51it even color codes in these categories
14:53what this is
14:54it'll tell you i've got six queries
14:57four of them were misses so it tells you
15:00the miss ratio
15:02the hit mish rate sorry the hit rate
15:05really nice simulator so you can
15:08practice and make sure that you
15:09understand this
15:10you can say you know here's a particular
15:12cash parameter can you ever get to
15:1580 misses can i can you play with that
15:18can you
15:18predict what you'll get how about this i
15:20could imagine i give you this setup
15:23i give you this sequence and i say fill
15:25in this table
15:26you should be able to run the traces in
15:28your head or like on paper like i just
15:30did
15:31and get those values so i love
15:34this cast simulator please feel free to
15:36help you learn what caches are and how
15:38they work
15:39we'll see the next lecture

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 27.2 - Caches IV: Block Replacement with Example by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 3,314 words across 517 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.