YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 26.2 - Caches III: Writes, Block Sizes, Misses

[CS61C FA20] Lecture 26.2 - Caches III: Writes, Block Sizes, Misses — Transcript

by CS 61C Departmental · 5,364 words · 842 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now we're going to
0:02reveal some layers of the onion
0:04we kind of were living in a rubber room
0:06for a while now we're going to realize
0:08that it's
0:08a little sharper and there's some more
0:10details behind this so let's think about
0:11how to handle rights for
0:13up to now we've only been reading we now
0:15we were reading words
0:16more than just bytes in beginning we're
0:17just reading bytes now reading words now
0:19how about writes what happens there what
0:21about block sizes and what happens when
0:23we have misses
0:24let's talk about all those elements near
0:25and now and get some more details
0:28so this is a beautiful picture of a
0:30multi-word
0:31uh multi-word block multi-word block so
0:35it's a block that's more more than just
0:36one word
0:37um direct map cache i've got here
0:42let's make let's actually make four
0:44words a block okay so four words so the
0:46block size is going to be
0:48like before four words are blocked um
0:50the cash size is going to be
0:524k words this is the same as before we
0:54saw this exact picture before 4k words
0:56or
0:5716k bytes all that's the same we saw the
1:00way we can think about our our ti and oh
1:02and divide them up
1:02and we saw the picture here in in the
1:05cache and the data is on the right side
1:07got a valid tag and i've got 10 10 24
1:10different rows
1:11so here is what happens we start
1:15by looking at the index and next tells
1:17how much row i'm in
1:18the row first i check my valid and i
1:21check my tag and so the tag comes out
1:22and my valid comes out of there
1:25so when my when i am valid and when my
1:28tag equal is equal
1:30i grab that particular
1:33word out of this and that let's actually
1:35look at some details here as i look at
1:37this
1:38here's what's actually quite interesting
1:41i only have a hit when do i have a hit
1:45you have a hit when you just you could
1:47think of the logic already when
1:49the valid bit is on there's a one there
1:52and the tag matches
1:53so i take my 18 bits of the tag compare
1:56with the 18 bits
1:57of the tag that's stored in that row and
2:00that block
2:01and well this is the block but in the in
2:02that row and i do a comparison there's
2:05an
2:05equal sign there so that means you just
2:07compare like they're if they're the same
2:08there's a one at the output of that box
2:10if they're not the same as the zero
2:12and only when i am that with the valid
2:15bit so only when it's valid and they're
2:17equal do i have a hit
2:18so that's already kind of interesting
2:21each of the data words
2:23is going to be fed into a mux here's my
2:26mux
2:27now what am i selecting from i'm
2:30selecting from
2:31which particular one i wanted
2:35you know remember we've mentioned it
2:37before these are all words i'm grabbing
2:39i ignore these last two bits those two
2:42bits are the byte offset
2:43that's where i am but i'm reading only
2:45word aligned values
2:46so i'm never reading every single
2:48request ever those two are zeros because
2:50i'm only reading words and words and all
2:52my words gonna be word aligned
2:54so that byte offset i don't i ignore
2:56they're all these are all zeros zero
2:57and zero that's what they are these two
3:01bits
3:02are the bits which are my block offset
3:05taken together those four bits are my
3:07bite offset but i'm reading words
3:09and if i'm word aligned i'm only ever
3:12getting
3:13having it be that those four guys if i
3:15look at that
3:16that nibble describing this thing that
3:18nibble is either 0
3:204 8 or c which means i want that
3:23byte that by word that by 8
3:26or c okay each 040 to c had two bits in
3:30the lower side
3:31are zeros so i actually only use the
3:33upper bits
3:34and the upper two bits are zero one
3:37two three what's the upper two bits of c
3:40one one upper two bits of
3:41of eight one zero what's happened to
3:43it's a four o
3:45it's a zero zero so this is this number
3:48is telling me
3:49which of those words is the mux going to
3:52be sending out
3:53and that might send that data out and
3:54i'm done that's a beautiful picture so
3:56this picture is actually describing
3:58what's happening
3:59in hardware and these are all happening
4:00at the same time it's not like well do
4:02this first
4:03okay you know computer scientists always
4:05think well you're sequentially
4:07well first check this and then
4:10you got to go and check the tag because
4:12if you're doing software you'd be doing
4:13in steps
4:14not zone hardware folks all these things
4:16are happening at the same time
4:18same time same time same time same time
4:20all that's coming out here
4:22okay and by the way if this is not a hit
4:26you ignore what this is i don't care
4:28what data's coming on those those lines
4:29i'm not going to pay attention to it
4:30because i haven't
4:31it's the wrong one either it's not valid
4:33or the tags don't match so i'm going to
4:34ignore my data so all those things
4:35happen at the same time but at the end
4:37of the day i check this hit first and if
4:38that's good
4:39then i'll use the data otherwise i'll
4:40ignore that data
4:43now i ask you what kind of locality are
4:45we taking advantage of here
4:46and i'll just pause as you think to
4:48yourself and before i give the answer
4:51the answer is both both temporal
4:54locality and
4:55spatial locality probably the person who
4:57wrote this slide i
4:58inherited a slide deck from other 61c
5:00instructors probably their mention they
5:02want you to say
5:02spatial locality because your block size
5:04is more than just one byte or one word
5:06so they want you to say spatial locality
5:08because they're talking about the block
5:09size
5:10but it's a cache all caches have
5:12temporal locality unless
5:13unless they don't remember the most
5:14recent guys but this one cache does and
5:16so
5:16they do that so it's it's taking
5:18advantage of both temporal
5:20and spatial locality we haven't at all
5:22though
5:23talked about rights let's just be honest
5:25let's be clear
5:27rights are part of the world right i do
5:29some sws sbs shs as well
5:32so what do we do on writes okay i have
5:34some data
5:35i'm going to store it in the cache the
5:37cache may have
5:38different data than i have i'm going to
5:40be writing to the area as i'm clobbering
5:41the cache
5:42as i'm writing something to memory i'm
5:44writing to memory i'm going to write
5:45into the cache too so that i stores it
5:48as well
5:49now i could either just
5:52treat them all as always consistent and
5:55that's the easier case
5:57the much easier case is what's called a
5:58right through so i'm taking my data from
6:00the processor
6:01and i'm pushing it out to the cache
6:03update the cache
6:04and you know what go to sacramento
6:06anyway push it all the way through the
6:07sacramento
6:09done now my life is so much easier thank
6:12you so much for doing it right through
6:13because
6:14they're always the same i don't worry
6:15about any of the details of
6:17what happens when they're inconsistent
6:19or in a way corrupted
6:20and maybe corruption is part of the
6:22design that's what the second one is
6:24about
6:24so write back says you know if you're
6:26just reading and writing to
6:27value you don't need to why don't you
6:30just stay in the cache
6:31here you know i'm going to read from an
6:32array value and i got it that's fine or
6:34read it or maybe it wasn't loaded so i
6:35load it up now it's there
6:36and now same same array value same array
6:39address
6:40i'm going to write a different value
6:41well do i have to go to sacramento i
6:43just
6:43i just came from second why couldn't you
6:45have them being consistent as the design
6:48because watch i write it and then the
6:49next line i read it again hey wait if i
6:51if i just read it again and write a
6:53different value and read it again a
6:54different value
6:55why do i ever need to tell memory like i
6:57feel like i can live with my cash
6:59and we talked about the we mentioned i
7:01mentioned this over and over
7:03it's always a local copy but you know in
7:06this world of right back
7:08i can save a ton of trips to sacramento
7:11i can save a ton of trips to sacramento
7:15if i just don't have to update
7:16sacramento all the time i'll let you
7:18know
7:19whenever i remove it from that so that
7:21we'll talk about that
7:22what do i need to actually up tell
7:24sacramento i wanted to actually write it
7:25to memory
7:26and but i get a big performance win if
7:29i'm reading it right in the same spot
7:30to not have to go to sacramento with
7:32every right if you say right through
7:34i'm going to sacramento in memory every
7:35single time but if i'm just going read
7:37write read write of the same location
7:39boy right back is way faster than right
7:41through are you kidding me it's a
7:42thousand cycles or more
7:44due to sacramento every time i'm doing
7:45that right so if i can save that i love
7:47it so people really appreciate write
7:49backs
7:49but you end up having more complexity
7:52what does a slide say
7:57memory when it's inconsistent there's a
7:59word for it we call it being stale
8:01stale is like stale bread it's kind of
8:02smelly and old and kind of you know
8:04maybe moldy so it means that memory was
8:07old
8:08stale means it's got older the most
8:10recent copy the freshest copy the
8:12the true the single source is almost
8:14there's no more single source of truth
8:15by the way but like the
8:17the the answer
8:20is in the cache not in memory memory is
8:23no longer the referential
8:24place where stuff is it's in the cache
8:27so there's a little bit we have to think
8:28about that memory is no longer the
8:30the last word cache is the last word
8:33actually if it's ever stale
8:35it also means i need to tell the system
8:38you know what
8:39if i'm going to go with right back i
8:40mean i i need to let the system know
8:43that this is now inconsistent i don't
8:46say corrupted because raptor usually
8:47means a negative thing
8:48i'm designing this into this so right
8:50back isn't corrupted it's that when i
8:51let memory be stale i gotta
8:53let it know that way that really it's
8:54the cash that has the referential
8:56value and that means i need to add
8:59another bit
9:00i had a bid for valid to say when i
9:01initialize the cash i need to know
9:02whether it's
9:03whether that tag is i can trust it or
9:05not so i had a valid bit
9:08we do the same thing here and similar i
9:10have a bit called the dirty bit and that
9:12dirty bit on a right back cache
9:14says that cache block is not the same as
9:18the block and this whatever that happens
9:19to be in the same
9:20place you know align that the same block
9:23there in memory
9:24that's not the same the cache has a
9:26different value
9:27even if by the way when i write it
9:31it happens to write the same value that
9:33was there before that's a little bit of
9:34a subtlety what if it's all zeros
9:36and i happen to write all zeros well i'm
9:38doing it right and it's right back it
9:40doesn't check them all
9:41and then say well if they're the same
9:42don't let nope even though i'm writing
9:44the same value it'll still make it stale
9:46it'll still say nope
9:47dirty bit said hi this guy is stale even
9:49though they're actually the same value
9:50so there's a little bit of a subtlety
9:51maybe you can optimize it and
9:53read but that's who wants to do that
9:54because maybe often block sizes are
9:56really wide
9:56who wants to spend time cycling through
9:58comparing the old guy with the new gun
10:00i'm going to write and when they're the
10:01same
10:01no but you often write a change so you
10:04don't do that so the point is even from
10:05writing the same block as was in memory
10:07i still say
10:07memory is now stale and dirty bit for
10:09that block is now one
10:11they're inconsistent and when the block
10:14is replaced that's when you need to
10:15write to memory so
10:16eventually memory gets updated but only
10:19when the block has replaced it or
10:21it's also replaced if the you don't know
10:23about the
10:24operating system yet but when the
10:25operating system has an input output
10:27activity
10:28it often flushes the cache and when you
10:30flush the cache you have to then
10:32correct correctly put back in memory
10:33because when you flush the cash you
10:34don't want to remember cash is now the
10:36same
10:36is now the truth and you don't want to
10:38just throw it away when you flush the
10:39cash
10:40if cash is only a copy i can just erase
10:42it all how do you raise the cash
10:44set them all invalid but if some of them
10:46had the dirty bets said hi
10:48you'd better put those back to
10:49sacramento to make sure that you update
10:50memory before i set the dirty bit and
10:52that
10:52kind of erase the cache if you will
10:54remember you never go
10:56you never do that you just set the dirty
10:57bit to erase the cache so when you flush
10:59it or raise the cash you set the valid
11:01the valid bit to zero but all the dirty
11:03bits that were won
11:04you got to make sure you write those
11:05back to sacramento okay
11:07and then you can play with the
11:08performance conversation and performance
11:09trade-offs when does one win when does
11:11the other win
11:12right what can you come up with a
11:14scenario where each one of them looks
11:15bad
11:16if you can by the way we can and you
11:18should think about that
11:19that's why we don't just say here's how
11:21we do it by the way remember how we
11:23talked about direct map cache and i
11:24even alluded to how would you find which
11:26which block it was maybe you use a
11:28linear search i was just making stuff up
11:30nobody does that this is where you just
11:32immediately go there it's a
11:33constant time figure out what exactly
11:35what row i have to go to by looking at
11:36the bits for my index we know how to do
11:38that now
11:39there's no log search for these things
11:42so in the same way
11:43because i'm still talking about two of
11:44these guys that must mean that there's
11:46some scenario where this is better some
11:48performance from some usage
11:52some characteristics of a cache with a
11:54usage pattern
11:55that makes right through be better and
11:57might be some characteristic with
11:58youth's pattern that makes right back be
12:00better which is the decision why we
12:01still talk about two ways of doing
12:02things
12:02so that there isn't like a clear winner
12:04and we just ignore and it's lost to
12:06history
12:06one's compliment lost to two's
12:08complement i'm sorry one's compliment
12:10you lost
12:11two's complement is better i don't want
12:13two two zeros so one's complement is a
12:15kind of a historical footnote
12:17but both right through and right back
12:18aren't historical footnotes we both
12:20these are both reasonable designs in a
12:21particular cache for a particular system
12:23so thinking about that is that still a
12:25conversation for that particular
12:27instance
12:28it isn't by the way all caches aren't
12:29always about memory hacking you have
12:30caches for the web page i got one paid
12:32cache
12:32cache isn't many i have cache for my
12:35recents of my uh
12:36phone call list so they're catches in
12:38all these places
12:40um and in any one of the situations the
12:42design might be well this one should be
12:44right through
12:44that one should be right back depending
12:45on how long is it to sacramento maybe
12:47it's not too long but
12:48all those come maybe the complexity
12:50means that it is longer but it's not
12:52that big a pain so i'll do that because
12:54the code to write the write back is
12:55whatever i hurry okay
12:59now let's talk about block sizes
13:03we started by starting the first picture
13:05of a cache i had a one byte block size
13:07like one you know the column width was
13:09where the width was one and i said well
13:10make it two
13:11and then we actually now have seen 16 16
13:13byte wide
13:14blocks what are the benefits of that
13:17well the benefits are you know spatial
13:19locality is screaming for spatial
13:20locality
13:21if you're going to sacramento if you go
13:23to the refrigerator get me a hole
13:25get me some food okay i came back here
13:27here's this and here's that
13:28okay if you go in there anyway it once
13:31you're going to the long distance path
13:33while you're there grab some stuff and
13:34then bring more of it back so you can
13:36stream it back as you're coming back
13:37with some data
13:39so this is very applicable for stored
13:42program concept
13:43model because we often have sequential
13:46arrays
13:46and you typically sweep through an array
13:48so if i'm going to go there
13:50i'm going to go and grab the whole block
13:53of that and that's going to be some
13:54fraction of the array and now as i'm
13:55walking through
13:56it's there it's a miss but then the rest
13:58of it or hits
13:59that's the idea of a larger block size
14:01what's the drawback
14:04we talked a little bit before two slides
14:06ago i believe two lectures ago
14:08on hit hit rate miss rate
14:12hit or miss penalty when you have a miss
14:15how much pain do you have to suffer to
14:17go to sacramento or go even farther for
14:19that
14:19so a larger block size means your miss
14:22penalty goes up
14:23it means if you come you know reasonably
14:26rather than go and grab one bite i gotta
14:27grab
14:28really i gotta go stack i grab 16 bytes
14:30what if i'm literally how about this
14:32randomly hitting memory just randomly
14:34literally and making it as bad
14:35what if i'm looking at what how you did
14:37what you did how you design your cache
14:39and making you do the most work possible
14:41it's a robot and i'm making you
14:42literally
14:43move to every corner like it's like
14:44taking the roomba go to that corner
14:46and then that corner and then that
14:48corner like it's literally and then
14:49and then like it's not just letting it
14:51kind of sweep a room it's literally like
14:52setting it random spaces as far away as
14:54it can
14:55so you can make this look really bad
14:57because of the miss penalty by
14:59hitting it randomly and therefore
15:00there's no spatial location the spatial
15:02academy isn't being exploited
15:04you're grabbing its neighbors but never
15:05visiting its neighbors i'm going to
15:07grab this block and it's a lot maybe
15:09it's really wide
15:11and then guess what i'm never going to
15:12see it again i'm going to grab another
15:13guy
15:14in fact if you make it even worse i'll
15:15grab another guide that happens at the
15:16same index and boop it's in the same
15:18spot oh my god really i went to get
15:19this huge amount and now it's replaced
15:21the same guy again and every single one
15:23is going to be a cache miss black
15:24replacement
15:25yes yes how do you do that
15:29you make a stride the stride is exactly
15:31the same as
15:33because i want to have an array an array
15:34an array has to be the same
15:36spot every so if your stride memory
15:39access memory access plus
15:42cache size cache size means remember the
15:45picture i drew before
15:46i drew this picture here with the cache
15:49size
15:50here's access one the next access
15:54is exactly the same spot in the next
15:58cache down
15:59that means this tag is i and this tag is
16:02i plus one
16:03and i plus two if you stride by cache
16:06size
16:06you typically have the worst possible
16:08performance because you're not making
16:09use at all
16:10of the fact that you loaded this whole
16:13block
16:14you're not using the neighbors you're
16:15going around and replacing the same guy
16:18that you if this is really wide imagine
16:20how if making this really wide
16:22you're having to go to sacramento grab
16:24all the neighbors and you're never using
16:25them
16:26can you please just the next memory
16:28access go plus one minus one so you can
16:29use some neighbors no sorry
16:31stride plus cash size worst possible
16:34performance ever
16:35in fact i encourage you look up your
16:37system's
16:38cache size and write a four line program
16:41that
16:41reads a bite i don't care what you do
16:43just you know read read a word read a
16:44word from make a huge array make a huge
16:46array in malik
16:47huge array find out what your cache size
16:50is
16:50and literally have a loop that reads it
16:52and then jumps by the next memory access
16:54is exactly the next cache size
16:56so that will be the worst possible
16:58situation you're never going to exploit
16:59at all the cash at all forget even
17:01spatial locality you're just never able
17:03to be you're never visiting the same
17:05spot you're just jumping a raid that's
17:06exactly
17:07that's really big and you're jumping
17:09you're striding by cash size
17:11worst possible performance by the way do
17:12that and run like 10 of them
17:15take your computer find out your cash
17:16what your block size is
17:18and run 20 of them just run a little
17:19thing you know make a little terminal
17:20make like 10 terminals and run them all
17:22you're going to be hitting this cash
17:24like okay i mean you're hitting the
17:26memory i create every single one
17:27not a single memory access is hitting is
17:30it's really funny
17:30to do this this is more fun in vm by the
17:32way because in vm you're moving data
17:35from the disk and then
17:36so it's it's worse this is a fun story
17:38to do i'll bring it hope
17:40hope i give that lecture but that's a
17:42situation where you can make vm look
17:43really bad
17:44by always striding by the thing that's
17:46going to be the unit of data because the
17:48worst possible same idea in vm you have
17:50these
17:50this unit uh we have here blocks and
17:52cache sizes we'll talk about pages there
17:54if you stride by page size that's really
17:56bad so
17:57that was an aside to make your system
17:58look really bad you want to make it
18:00really bad
18:00stride by the cash size then you'll
18:03never take advantage of temporal or
18:04spatial locality
18:06okay so if you make if your blocks that
18:09all that aside was
18:10if you have a large block size you're
18:12going to have a big miss penalty
18:14okay because you have to go when you're
18:15going to segment you have to bring more
18:16back with you that's the idea
18:18and by the way here's the funny so if
18:21the block size is too big relative to
18:22the cash size
18:23there are too few blocks and the miss
18:25rate goes up
18:26so in the extreme case where you just
18:28make it remember i told you you could
18:29take your cash
18:30and for the same area you can make like
18:32in any
18:34how do i say this if i said i want you
18:36to make a fence where the area inside
18:37the fence is
18:38fixed well it could be this way or twice
18:41as tall
18:42and half as wide or twice as wide and
18:44half as tall same area right i have this
18:45flexibility of aspect ratio
18:47of the cash that's the aspect ratio when
18:49you make it the degenerate case
18:51which is one high one you know one high
18:54by total number of bytes equal to the
18:57cash
18:57so one high and total equal to that that
19:00is the that
19:01in a way that's pretty good you just
19:03grab the huge
19:04range from that but here's the funny if
19:07you're like making a copy what if i'm
19:10copying a piece of code like two-line
19:11piece of code that copies from this part
19:13of memory to that part of memory
19:14so i go from here and i read a bit and
19:17then i go to here
19:18well this is a different part so i have
19:20to now bring and let's say that they're
19:22far enough away that they don't all fit
19:23together
19:24have to bring this guy in put that long
19:26thing around there
19:27well there remember always draw your
19:29memory same with this cache i'll draw
19:31memory wide so i'm
19:32reading from here memory to here i'm
19:34just reading copying from here to there
19:35a to b a to b a to b little loop well
19:38read this
19:39miss then i read this one well that's
19:41not there because that cause i only have
19:42one cache it's only one row
19:44so that's a miss two i'm trying to write
19:45that value and i read this one read the
19:47next guy over here
19:48okay that's a miss too and you have this
19:50crazy
19:52you're just loading in and out just
19:53never have a cache hit because you're
19:55always reading and writing
19:56from different places but there's only
19:58one row to store stuff so that's
20:00terrible
20:01even if i had two that'd be better but
20:03then you had this issue that's two and
20:04the direct map that could
20:06have the same index which means the
20:08mother wrote the same the best situation
20:09is when they end up having two different
20:11rows and i can read from here oh read
20:12read read right from here this is great
20:13like how fast this is if they both can
20:15fit in the cache at the same time
20:16so even two different rows can be can
20:17save me that if i happen to have a
20:19direct map cache
20:20that happens to have the same index
20:21where they end up in the same row
20:24long story short one big row is really
20:27bad and you often have this called ping
20:28pong effect where i'm continually
20:29kicking out
20:30these two guys and then forcing them out
20:31because they happen to have only one row
20:33and they don't fit they both can't fit
20:35so this is a really nice graph of a
20:37block size trade-off
20:39if i look at block size versus miss
20:42penalty how bad is your penalty your
20:45time
20:46for larger block size it just goes up
20:48and if you're going to sacramento
20:50and i'm i'm going to it's a linear you
20:52know relationship i've gone to
20:53sacramento to
20:54fetch one thing it's there fair fast
20:56double it's a bit more if i flash four
20:58times that that
20:59it's more there it's kind of a linear
21:00relationship there's probably some
21:01overhead i've got a sacramento period
21:03but then every kind of extras thing i'm
21:05grabbing is slower to grab
21:08put in my arms and walk it across so
21:11this penalty goes up linearly with block
21:13size
21:14how does miss rate relate to block size
21:17that's the kind of interesting thing
21:19normally block size is helping a little
21:21bit with that because
21:23all of a sudden you know spatial
21:24locality is coming in here so if you
21:26look at this
21:27spatial locality means that miss rate
21:29remember i don't have misses
21:31i want this to be as low as possible i
21:32don't want me misses okay i want my hit
21:34rate to go up
21:35so my miss rate is high but then as i
21:38make my block side better
21:39spacial cali is like hey you went there
21:41already and now my neighbors got it for
21:43me so that's kind of neat
21:44but what happens is at the end of it we
21:46just talked about this
21:48we lose temporal locality i end up
21:49having too few blocks to hold all the
21:51things i normally do and it starts to go
21:52up it there
21:53and that's a problem and if you remember
21:57there well i think i showed you this yet
21:59average access time where i see this
22:01again
22:01is a product of those guys so we kind of
22:04multiply them together
22:05and this the fact that this guy goes up
22:07here the fact that this guy goes up
22:09kind of amplifies this a little bit more
22:11if you see that and so this goes up here
22:13and what we typically
22:14say is we look for the knee in the curve
22:17we look in a place where the curve drops
22:19down otherwise the no
22:21otherwise known as the local minimum and
22:23so there is a
22:24sweet spot for the block size it isn't
22:26like well
22:27just make it as big as possible it's
22:28always a win or i mean if you only look
22:30at this miss penalty make it as small as
22:32possible
22:33if you just look at one number if i want
22:34to reduce missed penalty make it as
22:36small as possible
22:37well but then the remiss rate goes up
22:38and the fact that the fact that average
22:40access time is a project both of those
22:41means that i have to think about the the
22:43knee and the curve for that
22:46now let's let's talk about this what
22:48we're talking about misses what kind of
22:50misses do i have
22:54first is a compulsory miss these are
22:56these misses
22:57are misses because it's a cold cache
23:00cache starts there's nothing there all
23:02the valid bits are off there's no
23:04nothing's valid so
23:05i gotta take the hit compulsory means
23:07you just gotta do it
23:08uh you gotta take the hit you gotta
23:10start you gotta take the take the fall
23:12you need to take the miss
23:13on every road that hasn't been visited
23:15before that valid bit is off and you
23:17gotta take you gotta take that
23:18you need to pay that penalty there's no
23:19way around that so that put
23:21so every block is going to have at least
23:24one compulsory miss
23:25okay every block of memory
23:29will have at least one compulsory miss
23:34how about conflict misses
23:38well conflict is because you've got two
23:41remember the blue first picture of the
23:42cache the two blues
23:44mapped to the same i guess it was here
23:46the two blues map to the same blue over
23:48there so
23:51that's a shame oh it's such a shame we
23:52couldn't fix that
23:54in fact later lectures we're going to
23:56tell you how to fix that so two blocks
23:57happen to map to the same thing
23:59and that's the problem with direct map
24:00caches it i mentioned before if i'm
24:02ping-ponging here
24:04if i can even if i have a row a cache
24:06with two rows
24:08i still might have those guys be the
24:10same spot you know this huge block and
24:12this use block end up being the same
24:13because of the way that
24:14the index works they have to be the same
24:16row oh that's annoying
24:17so that's an issue with direct map
24:19caches that maybe we can exploit
24:20and think about relaxing that and maybe
24:23direct map caches aren't the only
24:24game in town we'll explore that in later
24:26lectures so that's fun
24:28so conflict missions you could either
24:30make the cache bigger
24:31and maybe the smart thing is could
24:34multiple distinct blocks fit in the same
24:36index
24:36what would that even mean to have two
24:39blocks two blues
24:40end up being in the same blue area
24:43we'll actually explore that in the next
24:45lecture we'll see you there

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 26.2 - Caches III: Writes, Block Sizes, Misses by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 5,364 words across 842 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.