YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 25.1 - Caches II: Direct Mapped Caches

[CS61C FA20] Lecture 25.1 - Caches II: Direct Mapped Caches — Transcript

by CS 61C Departmental · 5,889 words · 892 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now let's finally do it
0:03let's teach you how the basics of the
0:04simplest kind of cache we can come up
0:06with
0:07the direct map cache so
0:10in a direct map cache each memory
0:13address one of the questions we were
0:14asking of a cache is
0:16how do you know when i go to memory
0:18where it lives in the cache
0:20okay where does it go do i put it
0:22anywhere and then search for it linearly
0:24or log we never do that we know exactly
0:27where it is and where it's going to be
0:28is a very clear location we'll talk
0:30about when we show example the idea is
0:32every memory address is associated with
0:34exactly one block there's a new word you
0:36haven't heard before block
0:37that block is the amount of data that
0:41you move in and out of caches
0:42so that's it if i'm talking about a hard
0:45drive i talk about
0:46files what's the unit of data files
0:51if it's registers it's a word move
0:53things in and out in a word
0:54in a cache the thing you move in and out
0:56is called a block that's the unit of
0:58transfer
0:59so which block it's going to be in
1:03is always defined okay and very clearly
1:06defined it's not a search there's no
1:07search needed to find it i know exactly
1:08by
1:09what the bits happen to be let's
1:10actually look at an example to see what
1:11look like
1:12there is your first cache
1:16one of the abstractions of memory is to
1:17think of it as
1:19basically infinite we know it's 2 to the
1:2132 it starts at 0 and moves
1:24to 2 to the 32 minus 1 possible bytes i
1:27could write
1:28and here we're showing it here each
1:29memory address is a byte wide
1:31so we're showing that we're drawing this
1:32memory as a byte wide and by the way you
1:35can draw this picture memory different
1:36ways memory is
1:37i can draw it a byte wide and 32
1:412 to the 32 or 4 billion and actually we
1:44now know the word for it don't we
1:47for gibby look at this 432 is for gibby
1:50remember that
1:51so zero i could draw four gibby
1:54rows where each row
1:57uh is one bite wide
2:01or i could draw it a word wide
2:04so four bites wide and only one gibby
2:07high
2:08so four times one four you know one
2:09gibby times four is four gibby total
2:12or one bite times four gibby is four
2:15give me total so i can draw the memory
2:17and change the aspect ratio thinking of
2:19it different ways
2:21so it's the same memory i'm just drawing
2:22in different ways and thinking of it
2:24different ways
2:24and in fact i'm going to encourage you
2:26from now on
2:28from now from this point on if you ever
2:30draw memory
2:32slowly i'm just going to say this very
2:33slowly so you so we get it all
2:35draw memory so that it's the same
2:40width as your cash that's all you got to
2:43do
2:44from now on when you're thinking about
2:45one of these cash problems oh turn the
2:47page on the final exam it's a cash
2:49problem cash says
2:50the block remember the block is the unit
2:53of transfer that's the width of the cash
2:56is some amount okay whatever that amount
2:58is draw your memory the exact same width
3:01the amount member is going to be
3:02more rows because the number is bigger
3:04than the cache but always draw in fact i
3:06always draw them right above each other
3:07here's the cache his memory so the same
3:09width is like there
3:10with the cache with your memory okay so
3:12do that i'm drawing them here
3:14two separate two separate pictures not
3:15like this but so the same width see i
3:17did it same width okay
3:19okay so here we go
3:23first problem notice the color coding
3:26before i even tell you what's happening
3:27the color coding
3:27tells you the answer which is
3:31every four elements knows exactly where
3:34to go
3:36if you look at this picture all the
3:38blues go to the blue area
3:40so this is a four byte cache
3:44i'm starting to use some words that now
3:45it might make some sense
3:47what's our block size what's the unit of
3:49transfer it's a byte
3:51and that's the width so this is the
3:53block size and it's only one byte
3:55so i'm drawing memory one byte wide so
3:58how high is it
3:594 gb 32 to the 32
4:02total bytes i have access to okay and by
4:05the way sometimes we draw our memory
4:06from zero in the bottom to zero on the
4:08top i actually prefer to draw it
4:09top down but it means lowest number here
4:12increasing number there
4:14but sometimes the picture we flip it for
4:15convenience sake like when we talk about
4:17the picture of
4:18if you remember picture where stuff
4:19lives in code zero is the code
4:22and then above is the static and above
4:23it is the heap and above it there's a
4:25stack at the higher level so we actually
4:26flip and we talk about what the code
4:28does
4:28when we actually run cache problems we
4:30flip it to have zero be up top and down
4:32there
4:32okay all right
4:36so this is going to be one byte wide and
4:39if this is a four byte cache that must
4:41be
4:41that this is four there are four of
4:44these guys because this
4:45times this is going to be the total size
4:48of the cache
4:49okay it's like the area think about the
4:51area we'll actually have a picture of
4:52two
4:52later we show that but that's the idea
4:55width times height
4:56is the area of the cache okay but that's
4:58the idea
4:59so every four so i can tell without even
5:01thinking there's no search anymore
5:03well let's see where how about nine
5:05where does nine live really it's like
5:07modulo modulo four well what's nine mod
5:10four
5:10one well no that's what colors i didn't
5:12know that i didn't know that okay i know
5:13i know my my
5:14nine mod four is one let's just see if
5:17that's true
5:18well nine is this red color and one is
5:20the red color see
5:21did it for me so in a way this cache is
5:23doing modulus for us and that's how we
5:24do it
5:26another way to think about it here's
5:27another way to think about it
5:31what are the uh memory what's nine what
5:33are the memory addresses here let's look
5:34at let's get nine here
5:36101. which of these bits
5:40is telling me what row of the cache it
5:43is
5:44which one can you guys tell me
5:47yeah isn't that lower bits telling me
5:50what that is
5:51so already i can tell if you just tell
5:53me the number oh it's uh what's your
5:55what's your
5:56money address oh it's uh fqs no fq
5:59these have to be hex values good q good
6:01dan q that's a nice hex value
6:03f e d nine seven three four
6:07six oh six the last one was six
6:10six is oh one one oh i bet you you're
6:13in spot two which is the third spot but
6:17it's spot
6:18labeled by two okay so all you do is
6:20look at the low order bits and tell you
6:22what row you're in we're gonna see it's
6:23a little more complicated with that but
6:24that's kind of neat to be able to
6:25quickly go and figure out where things
6:27are immediately just by looking at those
6:29bits
6:30so cash flows kickstart this i said some
6:33of these things but cash flow
6:34location zero can come from zero
6:37four eight or anybody that has two zeros
6:40in the lower bits
6:41basically anybody that's divisible by
6:43four
6:46zero four 8 c keep going
6:490 4 8 c in fact if you look at any
6:52memory address
6:54this is all you need to know look at
6:55that hex look at the last look at the
6:57nibble
6:58the least significant nibble and that's
7:01basically it zero four eight c
7:03you're at zero sorry so okay that's it
7:06like a sheet
7:06all right zero four eight c you're
7:08you're in bunk zero
7:10next let's do it together one five
7:13nine d you're in bunk one get it
7:17okay two let's do it two six come on
7:21a keep going e you're in bunk two
7:25those guys are mod for r2 and let's do
7:28it together ready
7:30fast three can you do it seven
7:33keep going b f you're in bunk three
7:36enjoy yourselves
7:38pretty cool all right and all i was
7:41doing look at the lower two bits of
7:42those numbers to figure out what where
7:43they go
7:47so these four blocks
7:50by the way remember we can't stop i
7:52should remember here stopping at f
7:54remember it could be all the way down to
7:5532 gb
7:57i mean four gibby forgive me i got 32 in
7:59there four give me 232 is four gibby
8:01i go to 42 for gibby this could be four
8:03gimme high and it would still work
8:05all the blues all the blues one quarter
8:08of the whole guys are blues
8:09they all map to that blue spot it's kind
8:11of cyani
8:12but that's it now what if we wanted a
8:16block
8:17to be bigger than one byte because if
8:19you think about it now this
8:20you know what this really means if i i
8:22mean this kind of doesn't work at this
8:23level
8:24because if i had any 32-bit value
8:27it means the 32-bit values are being
8:29spread across
8:30the different cache spot like if i load
8:32in a float float 30 bits wide
8:34um well that means that the lower eight
8:36or here and then the next one is at the
8:38red
8:39and the next that doesn't make so much
8:40sense so usually we think of caches
8:42being at least
8:43a worldwide just like a load of float in
8:46that spot otherwise the float's being
8:47split across that doesn't i don't like
8:48that so much so
8:49we want to think about larger larger one
8:51bites but we're going to start teaching
8:52with cash is
8:53at a very basic level so you understand
8:54what this is from so for now
8:56we're in this beautiful abstract padded
8:59world
9:00model right now padded room i could just
9:02walk around i'm going to i can't hurt
9:03myself and padded room
9:05in which we're just talking about bytes
9:06we're just reading writing bytes don't
9:07worry about anything bigger than that
9:08for now just to be easy
9:10so now again we're just reading reading
9:12buying bytes for now okay easy at work
9:14look at how it happens now this direct
9:17map cache
9:18now says i'm going to have an 8 i've
9:20doubled my size look my block size is
9:22now two bytes that's
9:23wide four rows two bytes each that's
9:26four times two is eight that's an eight
9:28byte cache
9:29okay it's direct map still the easiest
9:31kind of caches we have
9:32but you see how we're doing it and this
9:34is critical by the way
9:36we're going to label the lowest byte is
9:39the top right it's almost like
9:41um kind of a right right to left view or
9:43maybe eating corn like this it's the
9:44opposite how you write read a page or
9:46something
9:47here is the lowest bite of all of memory
9:50then it goes across that's the next byte
9:53and then it goes back to down here
9:54and that's the next one so you kind of
9:56do this little ziggy zaggy thing as we
9:57read and as
9:58as the block size gets bigger remember
10:00block size is the width of the cache and
10:01it's still again drawn
10:02our memory the same width as the cache
10:05as i widen that block
10:06size i'm going to do the same thing how
10:08i don't care how it is the top
10:10right is going to be the the least bite
10:12the lowest byte of the lowest word
10:13of the whole thing and i walk my way
10:15across i pack them in till i get however
10:17wide that block
10:18size is and i jump back it's always
10:19going to be this way this kind of ziggy
10:21zaggity guy
10:22so that's that's not different as i
10:23change my block size that won't that
10:24won't change
10:26so again the whole blue thing moves up
10:28there but now when i ask for a bite
10:31the controller has to figure out where
10:32it is so now it's a little bit more
10:34complicated is it always the lowest bit
10:35let's see is it the lowest bit anymore
10:37now
10:38i don't know if it is anymore how do i
10:39figure out which one
10:41which goes where we can almost have a
10:43design question here
10:45zero zero well that that's in zero
10:48and and zero one that's that's this spot
10:51that's this guy right here okay
10:53that's also in zero but now one
10:57zero that's in one and then one
11:00one is in one you see what i'm doing so
11:03it's not so much i'm looking at let's
11:05look here that that somehow the lower
11:07bits are telling me where it is
11:09it's almost like i'm ignoring this one
11:11isn't it this isn't telling me anything
11:13it's kind of like this is telling me but
11:15in fact there are obviously four of them
11:17so it sounds like i need to be looking
11:18at these two bits
11:19so just as we're looking at this it
11:21looks like it isn't always the lowest
11:23bits that tell me where to go
11:24as i as i have more larger block size
11:27than one
11:28i feel like i have to somehow skip some
11:31amount
11:31until i start counting and we're
11:32actually going to look at this in a
11:33second
11:34how that actually works so i try to lead
11:37you like wow it's pretty simple looking
11:38at the bits
11:39it is simple but it's not as trivial as
11:41looking at the least significant bits to
11:42tell you what row you're in
11:43okay so when we ask for a byte again the
11:47controller does it
11:48finds out what's the right block and
11:49loads it for us that's what's beautiful
11:50about these things it's automatic
11:52how does it know the right one we kind
11:53of talked about that so that we talked
11:54about
11:55how do we select the right bite so now
11:57once i ask for it how do i know
11:59which is it the right blue if i've ever
12:01got a guy in blue
12:03is it the right blue guy is the left guy
12:05blue if i'm trying to return a byte
12:06which are these two that you just loaded
12:07the controller did something for us but
12:08which of the two blue guys do i want
12:11that's we got to figure that out here um
12:12and in fact that might have helped
12:14our numbers actually that column we
12:16crossed off
12:17maybe that was a secret for what bite it
12:19was that's i'm giving you a little hint
12:20of what
12:21what's there so for example memory
12:23address
12:2411101 okay well what's that by the way
12:28what's 1101 really fast really fast see
12:31you got to know that faster than that
12:32you
12:33were too slow here's how i do this 1 1 1
12:36is 7.
12:38one one one oh means seven has been
12:40shifted to the left by two spots
12:41that's times four seven times four is
12:43twenty-eight plus one is twenty-nine
12:46so in my head you give me one one one
12:47one i'd say twenty-nine and you're like
12:48how do you do that so fast
12:49i was not adding 16 and 8 and i wasn't
12:52doing that
12:54i got to 29 by saying oh that's 7 times
12:564 28 plus 1 is 29.
12:58so think about how to do this faster so
13:00you get to
13:02some interview and they they give you
13:03some bit and you're playing with bits
13:04much more fluently by looking at how to
13:06think of this so 1-101
13:0729 really fast right pretty cool neat 7
13:10times 4
13:10plus 1. okay so what's actually
13:14happening
13:14so how do i know which color block
13:161-1-1-1 this is kind of the
13:18main problem one one on one how do we
13:20know well i was kind of telling you that
13:22somehow we're gonna skip this lower guy
13:25and we know what row it is from
13:26the the one o but then maybe this is the
13:29one which is the which left or right guy
13:31that does that so that's
13:32part of what we're trying to get to is
13:34how do you figure out how to do this
13:36and and here's the interesting thing i
13:39think the bigger question
13:40isn't which blue but the bigger question
13:42i mean which blew
13:43from the left or right point of view but
13:45the bigger question is
13:46how do i know which blue it came from
13:50so remember the memory controller loaded
13:52a blue into my and up up it says
13:54blue's filled i look at the bits and
13:56it's filled with bits remember i can't
13:57tell by looking at a cache
13:58bits or bits it could be garbage it
14:00could be values so you can't just look
14:02there so there's got to be something
14:03else that tells me that it's whether it
14:04was empty or not we're going to get to
14:05that in a couple of slides
14:08but there's got to be a way to know
14:09which of these blues did i mean look
14:11this blue is full of data yep filled
14:13with good data very happy
14:14maybe that's even a picture so there's a
14:16picture there it could be garbage that
14:18happens to be a picture or could be a
14:19picture whatever
14:19somehow there's data there but i'm
14:21asking myself was it from this guy
14:23or was it from this i have to know which
14:25one that is to be able to know
14:27did i save myself time or do i have to
14:29go grab another blue and replace that
14:30one
14:31so what do you do a baggage claim it's a
14:34great sketch
14:35which is a funny sketch i saw on youtube
14:38in which a person says i'd like to
14:39find my bag and the person says you have
14:41to describe your bag yeah it's a
14:42it's a roll-on it's black um like
14:46every other bag in the world oh yeah
14:48sorry it's got a toothbrush in there
14:50uh again like every other bag in the
14:52world
14:53oh yeah sorry it's got two wheels uh
14:55yeah again right it's very funny sketch
14:57so part of what i'm asking is
15:00how do you distinguish your bags when
15:02you pick them up the airport you know
15:02you're flying back from
15:04home welcome back to cal it's you know
15:06late august welcome back first week of
15:08classes
15:09your bank get your bag they're all
15:10identical black bags there's some law
15:12that says you have to have the same
15:13boring rectangular black roll-on bag
15:16carry-on well not a carry-on because you
15:18want to check it but the point is you're
15:19checking your bag you're getting it
15:20how do you have what's the secret in the
15:22airport all that story was to tell you
15:24it's a tag you have a little tag that
15:27tells me oh it's this one no no it's
15:29this one
15:30so each of these blues should have a tag
15:33that tells you
15:34which where did it come from which of
15:35those kind of rows which of those
15:37floors you think of this memory it's
15:39like floors which floor did it
15:40originally come from
15:41to end up being in my having a copy in
15:43my cache
15:44that tag is the key just like a tag i
15:46remember on luggage
15:47the tag is the key so
15:51i introduce a tag and this is an eight
15:54byte
15:55direct map cache with a tag by the way
15:58those words meant nothing to you about
15:5930 minutes ago so it's kind of cool that
16:01you're like oh now i know what this
16:02means
16:04so here's what happens i get all the
16:06blues mapped to the blue
16:08and what should go in the tag well
16:11let's think about what should we put it
16:12there let's how about this let's make up
16:14a new
16:15set of bits for each blue and just make
16:17them up so everybody okay here we go
16:18everybody all the blues all the colors
16:20every row in the original remember make
16:22up a new special code
16:25that we could do that maybe you would
16:26have designed that one that's not as
16:28efficient as
16:29well they kind of already have their
16:30address
16:32at the very least which is the address
16:33comes with it right let's just use that
16:35that doesn't make any sense so
16:36let's just do the addresses and then
16:39you're going to say to yourself well
16:40do we do we actually need the entire
16:43address
16:44and we didn't some of the address tell
16:46us
16:47we were already blue maybe two of those
16:49bits told us that we were blue anyway
16:51right if i'm blue i know the two of
16:52those bits are zeros
16:54and we know that it's not the least
16:56significant two but the one over
16:58so i don't need those two bits right and
17:00you remember the least significant bit
17:02actually was the one that maybe told me
17:04which of the blues
17:05is it is it this guy is it this guy or
17:08is it this guy that's the least
17:09significant bit tells me
17:10which which column i'm in in my cache
17:14so i don't need that but either because
17:16that's just telling me there but i
17:18probably need everybody else
17:19so in fact here's why i think about it
17:22it's really interesting
17:26when we were we go let's go back in time
17:28again
17:29we were branch addressing and remember
17:32you can branch address
17:33and branch to every other byte and
17:36that's neat you can jump to any
17:3716-bit value every other place and
17:40memory you could branch to
17:42not everyone but every other one did we
17:44store that did we start the raw
17:46did we store when we stored the branch
17:48the actual amount a branch
17:49to restore to the byte level we didn't
17:52we stored it
17:53so that the number one means the next
17:55valid thing i could go to
17:57two is two over from the next valid
17:59thing i could go to
18:00so i didn't store all the bits i i
18:02didn't store all of them i threw one
18:03away i threw
18:04anything that was redundant they all
18:05bothered that would have been zeros if
18:07i'd stored all the bytes
18:08it would have been a zeros in that
18:09column why would i store all zeros i
18:10never store anything if it's all the
18:11same value that's silly
18:13so here all of these guys have something
18:15consistent which is
18:17they all have everybody here everybody
18:20here this everybody that's ever here
18:23has the lowest three bytes i don't
18:26really care about
18:27because the lowest byte is either zero
18:30and one telling me did you really want
18:31this one or this one
18:32and the next two bytes tell me it was
18:34blue so everybody has the next two bytes
18:36the same
18:37and this byte is either a zero or one
18:39either way i don't care about those guys
18:41so is there another way to do this where
18:44if i don't care
18:46i kind of in a way this is a fun way to
18:48think about this
18:50what if i just count by cash number like
18:52what do you mean cash number i
18:53i think i know i think i invented this
18:55term cache number it says
18:57take the cache here's my cache whatever
19:00size it is
19:01draw the same size here and label
19:04from zero it's zero and the next one
19:09try another cache and label it one and
19:11keep doing this keep
19:12right for the whole for the rest of the
19:13whole of all memory
19:15go ahead i'll give you time 32 gibby
19:17keep coming
19:184 gb keep going 232 or 4 gibby
19:21go to the bottom and literally make
19:23these squares and label them all
19:25the guy here here i'm calling the
19:29cash number and i claim
19:32that everybody in the first cash
19:36everybody from zero to seven would have
19:39everybody from zero to seven
19:40would have cache number zero i claim
19:43that and i say i claim that meaning
19:44the bits that are left after i throw
19:46away
19:48the the rows we'll call it an index
19:51flavor those
19:52two bits that tell me which row i'm in
19:53and whatever bits i tell me what column
19:55i'm in if i throw those away
19:56i'm left with i call the cache number
20:00and that's what i want to have my tag
20:01the cache number
20:03so that's the idea and i again i just
20:06mentioned this it's useful to draw
20:07memory the same width as
20:09if you do this you will be in a great
20:11space for doing a problem on caches to
20:13understand this
20:14and so i cross those off so
20:17and i write whatever bits are left which
20:20is the cache number where do they come
20:21from
20:22if you look at this you know 2 is here
20:24look this was 2
20:26that's cash 0. so that's 0. 14 was here
20:30here's 14. somewhere in there that's
20:32cash 2.
20:33see that i just keep doing that etc so
20:36you end up having cache number as your
20:38tag
20:39and that is the bits that you care about
20:40because other bits were either what row
20:42or what column but i'm still in the
20:43cache i don't care about those
20:45so that's it i'm left
20:50i now have the idea that if i look at it
20:53a generic
20:54address i can now tell you in a generic
20:57direct map way which bits went
21:00where and remember
21:04sometimes the block size is more than
21:05one when the block size is one
21:07and some of these values go away for a
21:11generic problem i have a block size
21:12the previous previous problem had a
21:14block size two or two bytes maybe it's
21:16much larger than that so i need some
21:17number of bits tell me which column in
21:19there
21:20i gotta know which row i'm in and the
21:22rest of them is my tag my
21:24cache number that's the idea i divide
21:27the memory into three fields
21:29tag which is the upper bits tag is
21:31always the upper bits okay that's the
21:33ones
21:33the lower guys will tell me which row
21:34and column upper bits are my tag that's
21:37my
21:37cache number from the last probably
21:40remember the index was which row i'm in
21:42and that's which block i'm in
21:44and the lowest set of bits tell me which
21:46byte i'm in
21:47which byte or which word i want and
21:49that's which column i'm in
21:51and that's it that's the big idea each
21:53of these fields are read as
21:55unsigned values there's no sign value
21:57here it goes from zero to all ones
22:00and we usually start by the way if you
22:02look at this it's it's listed from left
22:03to right t
22:04i and o but we don't think it that way
22:07we typically think of working with the
22:09cache by going with the i first we go to
22:11the middle first
22:12which is weird because i like ignore the
22:13upper bits and the middle bits and kind
22:14of spread them out okay
22:15by the way the good part of the pie is
22:17right here take the side take the crust
22:19off and i get the stuff in the middle
22:21my index and what row i'm in that's
22:23where the action is so i go to my index
22:25what
22:26what's the action what row am i in okay
22:28so what what block am i
22:30in then once i'm there
22:34i'm going to see which byte i want and
22:37that's the offset
22:38now that's not the order usually it's
22:40index tag offset we'll get to that in a
22:41second
22:42the algorithm for this and the tag is
22:44the remaining bits the offset tells me
22:46which column which byte or word i want i
22:49mean in general it's what byte i am
22:50but if i'm reading about only words at a
22:52time the lower two guys would be zero if
22:54i want that
22:55index is which row i'm in offset is what
22:57column i'm in and the tag is the
22:59remaining part always the upper set of
23:00bits to check to see
23:02where did it come from did it come from
23:03the place i wanted to yes therefore it's
23:05there already
23:05and you'll see this when we do an
23:07example all these things will become
23:08crystal clear hopefully okay so the tag
23:11is the remaining bits after i've taken
23:12the index and the offset away from them
23:14and i came up with this mnemonic i think
23:17i don't know maybe other people did but
23:19i came up with i don't know anybody else
23:20use this mnemonic so i kind of i want to
23:22take credit for that
23:23and in spanish
23:26the word for uncle is theo hey
23:30theoden so and i always think of myself
23:32as a fair bit of unclear
23:34like an uncle so remember this
23:38theoden's mnemonic theoden tio theoden
23:41okay uncle dan tag
23:45index offset left to right t i o tag
23:48index offset
23:49and here's a way to think about caches
23:50in general here we go
23:54the lowest set of bits the index and
23:57offset
23:58are what determine the area that's the
24:01overall area
24:02why because the offset tells you the
24:05width
24:06i've tried to color code this so if you
24:07call it if you're color blind the i'm
24:09trying to i'll show i'll show this here
24:10but this is blue here
24:11for this and this is a little green and
24:13it says this is the index index tells me
24:16how many rows i have
24:18okay so that's and that is just pure
24:20number of blocks that's the unit
24:22a number of blocks the unit of the
24:25offset is
24:27the bytes per block i'm thinking about
24:29how many columns i have well
24:30it's bytes per block is telling me that
24:33and if i take the multiple take the
24:34number of
24:34number of blocks which is the height two
24:37bytes per block which is the width
24:40blocks times bytes per blocks the blocks
24:42cancel i get bytes
24:44so i multiply them together i get the
24:46area and bytes
24:47that's it that's how that's how we work
24:49with it and the tag is whatever is left
24:51so that's the big idea the big idea by
24:54the way this is important
24:55don't forget that if i take 2 to the h
24:59and multiply by 2 to the w i get 2 to
25:02the
25:02quantity h plus w he's like dan i get
25:05that yeah but we're going to be talking
25:06about
25:07height as not just a number like 5 12
25:11i'm going to say something like 2 to the
25:12ninth
25:14you're like oh i should draw like a nine
25:16i'm gonna say well what's the width well
25:17i might say two to the sixth
25:19and i'd say quickly tell me the area
25:22tell me how big your cache is
25:24and you quickly in your head say nine
25:26plus six is
25:272 to the 15 is 32 kibi you got a 32 kb
25:31cash there dan
25:32so i want you to be really fast by that
25:34i gave you a lecture
25:35several lectures ago on being able to be
25:36fast by that two to ninth it's 5 12.
25:382 to the 6 is 64. and i don't want you
25:40to sit down all right 512
25:42times 64. let's say carry the one i'm
25:45going to
25:46have to kind of like to take your pencil
25:48and kind of like carry the 1.
25:49i don't want you to do that 9 plus 6 is
25:5215 2 to the 15
25:5332 kibi it's a 32 kb cash i want you to
25:56be fast like that which is why
25:58i mentioned this and that's also why i
26:01mentioned
26:01um the idea of being able to be fluent
26:04with these numbers
26:052 to the 15 you should be very fast okay
26:08and by the way you can imagine i might
26:10ask a question like oh i don't know
26:13if my cache size is uh my cache size is
26:1632kb
26:17and i have an index oh and see now we're
26:20playing with this
26:21i have uh nine bits of index
26:25what's my block size oh see i just asked
26:28that i just flipped the whole thing
26:29so i'm thinking okay two to the fifteen
26:32divided by
26:32nine bits that's true to the ninth rows
26:35fifteen to the fifteenth
26:37to the 15th by the way there's the
26:39equivalent just of this of like
26:40well then true to the h plus w minus
26:44you know uh divided sorry divided by 2
26:46to the h
26:48if i divide both sides by this h2 to the
26:50w so i say
26:51okay i got a 32 kb cash i've got
26:54nine bits of index that's two to the
26:56ninth i'm thinking 32 kb
26:58or k to the 15 divided by two to the
27:00nine 15 minus nine is six
27:01two to the six oh i got 64 bytes wide
27:05block fast that's the kind of thing that
27:08we're going to ask you to do and be able
27:09to be fluent in so
27:10hopefully this lecture gives you a
27:11little bit of a this lecture combined
27:13with the other lecture where i told you
27:14to be fluent in those
27:15numbers let you realize that we're going
27:16to be talking about 2 to the power for
27:18these things
27:19and the number of bits i have tells me i
27:21have two of those rows if i have
27:22n bits uh i bits for the index is true
27:24to the i
27:25different rows if i have o bits for the
27:28for the offset it's two to the o bytes
27:31in that block
27:32that's the idea so each of these guys is
27:35going to be a function
27:36of that you're going to be i'm going to
27:38ask you to be fluent between the bits
27:40to the number of rows and number of
27:42columns and then overall
27:43again product of that is the overall
27:45size of my cache
27:47because that we're going to be a lot
27:48that's right you cannot be at an exam
27:50and this is back in the days when we
27:51didn't have open book exams and untimed
27:53exams
27:53but you can't be at a cash question
27:55right let's say 2 to the 9th then you're
27:56writing 2 to the 9's okay 64 times 2 to
27:58the 5
27:59look it up multiply it no fast fast fast
28:02so we're encouraging all of our folks
28:03you didn't really need it before now but
28:05as we start working cash problems
28:07you're gonna need it and it definitely
28:08helps it definitely helps not to be
28:09stalled on kind of some of the simple
28:10arithmetic
28:11okay that's it we'll see at the next
28:13lecture thanks so much

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 25.1 - Caches II: Direct Mapped Caches by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 5,889 words across 892 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.