YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 26.1 - Caches III: Direct Mapped Example

[CS61C FA20] Lecture 26.1 - Caches III: Direct Mapped Example — Transcript

by CS 61C Departmental · 2,938 words · 454 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back halfway point let's do
0:03this
0:04let's see a real example where we talk
0:06about a direct map
0:08cache and poke at it with requests and
0:10have some hits
0:11and some misses and misses with block
0:13replacement and understand the valid bit
0:14and actually put it all together with an
0:16example
0:16it often doesn't ground itself until
0:18this lecture hope with this lecture
0:20feel free to watch you know watch this
0:21at half speed you'll get this
0:23so this is an example of a direct
0:26mapped cache let's do this okay
0:31boy guess what same problem i had before
0:3416 kibi bytes of data we should
0:37that was the last lecture we ended with
0:38that picture forward blocks again
0:41see the same thing we're going to work
0:43out the height with an area we did this
0:44already we already worked out those bits
0:45in the last problem
0:46i'm going to re read four addresses 14
0:50in hex 14 1c 34 and 80
0:5314. what happens that's what i'm going
0:56to do
0:56and now you'll see how to do every
0:58single thing we'll break it all up we'll
0:59do this for you
1:00and here's the memory values by the way
1:01just to let you know we're going to put
1:03some values
1:03you know whatever a is these are word
1:06wide okay these are words here we're
1:08talking about
1:08so a is some value of words not this
1:11doesn't mean
1:12a the hex value a means that lowercase a
1:15means
1:15some value of uh that's that we're going
1:18to label a
1:19and again a through d is the lower side
1:21and then in the 30s here in terms of the
1:23address it's e through h
1:25and in the 80 kind of 8 000 e range
1:29it's going to be i j k and l okay here
1:32to see why we choose those values
1:33in a second here we go here's my four
1:36values
1:3714 34 1 c 80 14. write out the 32 bits
1:42draw your columns where's your t where's
1:44your i
1:45where's your o how much is it we talked
1:47about before there's
1:4814 bits for my cache four bits are my
1:52offset
1:53that's one of 16 different bytes
1:5710 bits for my index that's one of a
1:59thousand twenty four different rows
2:01different blocks so where here here's my
2:04ten
2:05here's my four then how many is here in
2:08my tag well if it's 32-bit wide
2:10r you know risk 5 32 this is 14
2:13that must be an 18 bit okay
2:17tag so we kind of know that from before
2:20and by the way notice by the way here
2:21look the tags are all this is all zeros
2:23that's a zero that's a zero that's a
2:25zero that's a two
2:26so let's remember that for the future i
2:28have kind of the other if i'm if the
2:30range is in the eighties my tag's not
2:31going to be zero the other guys on the
2:33low side of memory
2:34this is on the higher side of memory um
2:37my indices are look okay that's like
2:38that's a row that's row one that's where
2:40one that's row three that's right so
2:42already kind of seeing this i'm gonna be
2:43poking at this in row one and row three
2:45and these are the different columns i'm
2:47getting that's a four
2:48that's a 12 that's a 4. okay that's a 4.
2:51by the way what why is what do i know
2:54about this
2:55all these are zeros i'm probably reading
2:57words here if i'm reading words
2:59if you remember the picture i showed you
3:00a second ago i think i watch
3:02these were word-wise this is four bytes
3:05wide
3:06so if i'm only reading load words you
3:08know i'm going to be word aligned in my
3:09memory accesses
3:10which is why all these guys are zeros
3:14that's pretty cool okay so all this
3:16starts to make sense once you play it up
3:18with it
3:19here's my picture beautiful there's my
3:21valve i need a valid bit
3:22what do i reset my valid for yes they're
3:24all zero
3:26what temperature here we go what's my
3:27temperature my cash freezing cold
3:30empty nothing there valid bid's telling
3:32me nobody's ever
3:33visited this guy before it is it is
3:35literally it's got that it's got the new
3:36cash smell i just
3:38cracked it open tennis you're gonna open
3:40like a tennis
3:41i have one here i'm pulling this out you
3:42ever open this guy
3:44open the thing new tennis ball smell
3:47okay that's a little weird but i usually
3:49do that when i open my tennis ball bags
3:50i got right got my new cash smell here
3:52okay give me here we go ready
3:54having some fun i'm just trying to make
3:55this fun for you guys all right
3:58let's do it we got four reads to do
4:00remember no rights here i'm just doing
4:01reads and it's simple direct map is the
4:03simplest kind of cache
4:04still this complexity to it but this is
4:05the simplest kind of cache without
4:07before we add more layers to complexity
4:09i'm reading memory address 14. i break
4:12it up what do i got
4:14i got a zero i got a one i got a four
4:17and by the way just so you know just so
4:19you know
4:21because i have four bits here in my
4:22offset this
4:24hexadecimal nibble is my offset
4:28instantly and this because i have this
4:31is 10 i think
4:32i said 10 bits right 1000 rows well 10
4:35bits is
4:36is kind of like well it's like this and
4:38then like
4:39half of that so just in the future if i
4:42i can almost read directly
4:44what my index is by reading
4:47kind of eight to ten bits here which are
4:50the lower two hex digits
4:52nibbles lower two hex nibbles and then
4:54half of the other ones so
4:56let's just give it a little taste of
4:57that okay so what happens
5:00i first got to figure out what row i'm
5:02in this is why we always start with i i
5:03think i mentioned last lecture or two
5:05lectures ago
5:05we start with my i what row am i in i
5:08look at my index i'm in row one
5:12before i tell you what's gonna happen
5:13see if you can predict what what the
5:14algorithm should be doing
5:15what does it do next can you can you
5:17figure it out
5:19you're right i look at the valid bit how
5:21we gotta check that first
5:22i don't okay this way this would be a
5:24great question on an exam i like that
5:26is the next thing you do if you look at
5:27the index the tag no if the valid
5:30is wrong if the valid is not wrong zero
5:32that tag could be garbage and
5:33might actually match my tag taking me
5:36down a path of code that i want to be
5:37that's the wrong thing to do
5:39check your tag first check your check
5:41let's go back
5:42check your valid bit first i have to do
5:44this check your valid bit first
5:46when it's zero it's not valid so
5:49cash miss had to do it just how to do
5:51this we're going to call it we're going
5:52to learn that this is called a
5:53compulsory miss
5:54i don't want to teach you that word i'll
5:55teach you that word a moment but it's
5:56like i got to take the miss when i got a
5:58when i was a zero valid bit
5:59i got nothing to do but a miss there's
6:01no way that i can have a hit there
6:03so i load the data in well how much when
6:06you're going to sacramento you might as
6:07well get some more stuff
6:09folks what kind of what kind of uh
6:11locality we're working with here
6:12temporal or spatial both
6:16it's a cache i'm remembering the guy i
6:18just visited that's the temporal part
6:20and i didn't just load a bite i loaded
6:21the bite and a word i should not little
6:24bite and it's neighbors a word
6:25and their neighbors three more words so
6:29there is some spatial locality i'm
6:31trying to exploit here with this
6:33wider block size okay
6:37i set my notice this oh i've got to set
6:39my valid bit don't forget to do that by
6:40the way if you're implementing a cache
6:41ever in hardware you forget to set your
6:43valid bid
6:43you'll never have any hits because it'll
6:45always be you'd always think it's cold
6:46when it's actually warming up
6:48so make sure you set your valid bit and
6:50what's last what's the next thing you do
6:53you got to return something it's a load
6:54word who you're returning well
6:56this value of 4 says look up here and
7:00grab
7:01the b and i return b okay
7:04this is these are bytes zero through
7:06three or that a
7:08a encompasses this whole thing is this
7:10is i always draw these dotted lines
7:12this is four bytes in here or a word if
7:15if i'm loading a word i'm going to load
7:16either this word or that word it's got
7:19to be
7:19it's got to be word aligned so i'm
7:21loading b because
7:22i i kind of ignore in a way i kind of
7:25ignore those bits because i'm learning
7:26words
7:27i ignore those bits that tells me the
7:30number
7:30starting from zero of the word i'm
7:32grabbing if it's all zeros it's a if
7:34it's zero one it's b
7:35so in a way you can actually look at
7:37this and if i'm loading words i ignore
7:39those lower bits
7:40just fyi so i return b so i had i got a
7:44cache miss
7:45loaded the block up and return to b
7:48that's the first request i got three
7:50more let's do it read
7:52one c okay what do i do again this is
7:55going to seem very boring once you've
7:56done a couple of these but for now
7:58let's go slowly well divide 1c up
8:02into the bits what's my tag zero what's
8:04my index
8:05one what's my offset 12. okay so think
8:09about that
8:10as we move forward here i check
8:13i go to my i take the index i take the
8:15little orange label and say
8:17go to my index always the i first it's i
8:19t o
8:20it's actually i process check my end
8:21actually i v t o really
8:23ooh ivto is the new mnemonic i need a
8:26new mnemonic for ivto
8:27index okay got that row
8:30v for valid then i tag
8:34hey the tag matches this means i read
8:37this
8:37block i read somebody from this block
8:39recently and
8:41nobody else in no other color did i read
8:43since that one
8:44i don't know how long it's been there it
8:46might be really dusty in cobwebs but
8:48i've read anybody else
8:49since i read that one so that's pretty
8:51cool um tag matches
8:54next thing as you know i v t the t is
8:57there
8:57and the o check your offset offsets goes
9:00go grab c
9:01and go grab the last word in that block
9:04and there's your d
9:05return your d so we return to b and a d
9:08we're doing pretty well
9:09we had one miss and we got a hit i love
9:12the caches
9:12already we're saving our time i didn't
9:14have to go to sacramento because when
9:15you went to sacramento you brought your
9:17neighbors i brought a b c d you only
9:18wanted b last time but i brought abcd
9:20guess what
9:21now i wanted d i love this this is just
9:23great
9:25all right here we go this is going to be
9:26trouble now 34
9:28okay let's try it so first thing divide
9:30the bits up
9:31and i already can see there's some
9:32problem is that my index is a three
9:35i've never visited three before so
9:37that's the same situation we can go
9:38faster
9:38i've never i've never seen this before
9:40it's not valid
9:42i load no valid data i load the guy in
9:45uh load the cache block set valid
9:48look at my offset return my f and i move
9:51on
9:52so we've said we've kind of seen that
9:53case before we did the first one
9:55here we go there's excited 80 14. here
9:59we go
9:59let's try it okay oh 80 14. that looks
10:02like
10:03this looks like a whole different a
10:04cache number i can tell that because the
10:07tag is different
10:08that tag is my cache number so we first
10:11go
10:11check my index ivto index is the second
10:14row or
10:15index number one
10:18how's my valid check data's valid so
10:21that's the second part v
10:23t check my tags tags don't match
10:28and these are only reads for now so this
10:30is a copy and because i'm only reading
10:32never writing i can just throw this away
10:34that's the key thing we're going to get
10:35this mor
10:36when i reveal the hood reveal the
10:38simplicity
10:39we're in a little rubber room for now
10:41once i make these rights
10:43well what if i've had this right and
10:44it's not the same as memory what do i do
10:46there can i throw it i can't throw it
10:47away because that's the most recent data
10:48is in the cache not
10:49all those the complexities we're not
10:50even talking about now so for now i just
10:53throw that away i got to throw that away
10:54it's a cache miss block replacement i
10:57got to load in
10:58whatever that block is whatever those 16
11:00bits were those four words
11:02from memory and replace abcd if you
11:04remember that before it is
11:06ijkl i've got an offset and again
11:10set my update the tag too don't forget
11:12by the way yeah make sure to update the
11:13tag just update the valid make sure to
11:15update the tag with if there's a new tag
11:16put your new tag there otherwise that'll
11:18be all wrong that would be really bad if
11:19you didn't up your
11:20date your tag um it would think it's the
11:22wrong place and that would be really
11:23inconsistent
11:24and now go to my offset ivto what's the
11:27last guy o
11:28offset is four grab my j return j that's
11:31not bad that is not bad for
11:35four things okay here we go now okay
11:37this is one of those cases almost like a
11:39clicker peer instruction question
11:43what if i gave you and the value of
11:45values could be a b c d e up to j k
11:47l before 30 okay
11:51and i'm going to ask you what if you
11:52read a 1c so i
11:54really encourage you very strongly to
11:57pause it right now
11:58pause the video try to do a read of 30
12:01i've added address at 30 and read it
12:03address 1c
12:05and we'll come back in a second
12:09and welcome back say hi i paused
12:11pretending like i was i pause here we go
12:13all right 30. we need to do it to get
12:15together here we go watch
12:16i'm not even gonna i'm gonna stay on
12:18this page i'm not even gonna need any
12:19help there's nothing on this page i'm
12:21doing it
12:22okay dan said okay dan said i-v-t-o
12:25i-v-t-o i there's my three
12:28so i go here my three v
12:32valid yes t
12:36that's a zero is that the same as that
12:38one
12:39yes oh
12:42oh i think i return e
12:46i'm feeling pretty good so this guy was
12:49return
12:50e okay
12:53how about nothing nothing i don't change
12:54anything i actually don't update at all
12:56just return e
12:57cash hit best possible case 1c
13:01divide it up ivto
13:05index one go back here so we go to my
13:09one
13:10v valid yep valid
13:13tag zero oh man
13:18what's the tag there are they the same
13:21that's not so good i'm not just saying
13:24so
13:24cash miss block replacement i got to
13:28swap it out
13:29do you remember what was in that first
13:30guy i believe it was a b c d
13:32so then i go here and
13:36by the way this was before i think i
13:37asked this before maybe i did i don't
13:39know
13:40uh i i want a
13:44i want to ask and i think it's going to
13:46be there this is going to be cross it
13:48off
13:49a cross it off b cross it off c
13:53cross it off d cross this off
13:57write the zero there and you wanted
14:00the 12 and that is i'm counting by this
14:03guy you wanted the 0 1 2
14:053 the last one and i think you return a
14:07d
14:08let's see how we did so i think what did
14:10i say i think we returned
14:12an e and a d i think that's what we did
14:15let's try it
14:17okay what we get
14:21i return an e return to d there's my
14:24values e and d
14:26huh what's the thing and they're perfect
14:28and then
14:31that's it that's not too hard that's not
14:33too hard if
14:34only there were a cache simulator that
14:37existed out there in the real world i
14:38could just play with
14:40and explore oh i wish it's just too bad
14:42that no one
14:43has written a simulator of a
14:46cache to ma'am well i guess i guess i
14:49guess
14:50that one doesn't exist out there it's
14:51just too bad that we don't have a cache
14:52simulator
14:53oh well and on a sad note no cash
14:55emitter out there
14:56as far as i know
15:00see the next lecture

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 26.1 - Caches III: Direct Mapped Example by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,938 words across 454 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.