YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 27.3 - Caches IV: Average Memory Access Time (AMAT)

[CS61C FA20] Lecture 27.3 - Caches IV: Average Memory Access Time (AMAT) — Transcript

by CS 61C Departmental · 2,799 words · 447 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00we're doing great we're about halfway
0:01through this last lecture
0:03now let's take a look at a new way to
0:06measure
0:07how well we're doing with our cache you
0:09know i say like well i want to have the
0:10fewest misses and i
0:12i want to have the maximum hit but i
0:13also want to think about even maybe
0:16adjusting parameters of the cache
0:18and maybe as i just parameters maybe the
0:20time there
0:21you saw this it was like we talked about
0:23before there's a
0:24there's a a a missed penalty
0:28so there's some time there's a number of
0:29cycles that that's a factor then where
0:31does that kind of come in as i'm kind of
0:33running different traces
0:34on different cache parameters so one of
0:36the ways to measure whether
0:38your cache is doing well is to look at
0:40let's actually have a really nice rubric
0:42that'll tell me whether what we're
0:44trying to optimize for and really what
0:45we're trying to optimize for in a cache
0:46design
0:47is this phrase here the average
0:50memory access time or amat
0:54so as i said there's a ton of parameters
0:56in my cash i've now taught at least a
0:58couple look
0:59associative you got this big number n of
1:01what's my associativity
1:02what's my block size remember i told you
1:04you can change the aspect ratio of a
1:05cash
1:06what's my replacement policy what's my
1:09right policy there's at least four
1:11different parameters it's like filling
1:12in a form
1:13that i have to kind of fill in all these
1:14parameters before you let me build a
1:15cache
1:16and so all these elements allow me to
1:19to have flexibility as a cache designer
1:21i'm a hardware person building the
1:23fastest new whatever
1:24a chip a cpu or embedded system i don't
1:27know what i'm doing but i'm going to be
1:28use a cache for it i know caches are
1:29important and i get some parameters so
1:32as i'm looking at the kind of standard
1:33traces standard workload i'm going to be
1:35using my cache on
1:36using the system on how do i know what
1:38to choose for
1:39well design against this particular
1:41parameter the average memory access time
1:44and here's what it is
1:46you've got a cache this is the stuff in
1:48the cache this is the stuff below this
1:50is stuff at the next level of memory
1:52so the total at the average memory
1:54access time
1:55is the hit time
1:58hit time says you hit the cash
2:01that's great if you didn't hit the cash
2:04what happened is
2:06you've got a missed rate
2:09that says when didn't you hit the cash
2:12and a missed penalty
2:14and the reason this is you might have
2:17thought
2:18why dan why shouldn't this be
2:21rate times hit time plus
2:25miss rate times miss penalty why should
2:28why isn't there like a
2:29term in here why isn't this times hit
2:32rate
2:33hit rate why is it like that
2:36and it isn't for the following reason
2:40how much penalty do i have to pay when i
2:42if it's a hit i pay the hit time
2:46when it's a miss stay with me how often
2:49do i have a miss
2:50well miss ray tells you how often you
2:51miss it what's the penalty for that miss
2:53penalty
2:54even after you get that you have to then
2:57grab it from the lower memory put it in
2:59the cache
3:00and almost like restart and then have
3:02another hit so that hit time gets
3:05counted both times so you don't need to
3:07have the hit rate in there
3:09because really the miss rate captures
3:10the other time and because you're paying
3:12the hit time either way
3:14if you weren't paying that time either
3:15way you would fractional it off but
3:16you're paying it either way
3:17so it's like i don't even care what the
3:19hit rate is whether it's a hit or miss
3:20i'm paying the hit time
3:21it's like an overhead right this is oh
3:23you're paying this either way
3:25hit or miss you're paying the hit time
3:27and then if you happen to then
3:28have a miss here's how often you do it
3:30and it's the penalty you have so that's
3:32the reason this term is as it is
3:33okay again the illusion is
3:36really fast as the slowest as the
3:39smallest level
3:40smallest most expensive level but the
3:42size of the larger level
3:44how do we improve the missed penalty so
3:46we played with the block size as a way
3:48to play with these things
3:50and the larger block size is more miss
3:51penalty you saw them remember when i
3:52have a miss
3:53man i got to go to sacramento and bring
3:55more stuff in so
3:57bigger block size affects the the miss
4:00rate in a good way
4:01for a while but increases your missed
4:04penalty
4:05what's another way we can do what's
4:07another design space we could have
4:09almost like we could turn to recursion
4:11for this so let's think about this today
4:14um again when crashes first became
4:16popular the miss penalty was like 10
4:18processor clock cycles
4:19so in the early early days a missed
4:21penalty was you know if you had a good
4:22memory
4:23there was no gap between the processor
4:25and memory speed so there was almost no
4:27penalty miss penalty
4:28and as it became to grow well in the
4:30early early days it was like 10 o'clock
4:31cycles
4:32i could wait 10 no big deal now it's on
4:34the order of 200 or even more okay
4:37that's an issue don't want to go to
4:39memory so this is my picture i don't
4:42have a memory so what do i do
4:43i introduce the cache and the cache says
4:46you know what
4:46from the point of view the processor
4:49you're getting from me i'm doing a load
4:50word i don't it's not like abstraction i
4:52don't care
4:53don't tell me how the data is getting
4:55here just make it happen
4:56mad surprise me okay and maybe that now
4:59maybe it's the cash that has it maybe i
5:00go to sacramento i don't care
5:01a point of view processor the data is
5:03ready when i want to get it
5:06you see this little picture you see how
5:07it's kind of recursive into the way
5:09process of memory
5:10cash back what if i went one more level
5:13watch this
5:15what if i added a second level cache
5:20and this is in my triangle really what's
5:23happening we're adding more levels of
5:25cash here
5:26so adding just
5:29simply one more layer of cash between
5:31memory and the processor
5:32will often call it to the second level
5:34cache it's almost like this
5:36you know someone's on a tightrope and
5:37they might fall and then there's a
5:38little teeny net to save them
5:40if they fall out of that net there's a
5:42bigger net below that so this is the
5:43idea of having these
5:44successive nets underneath so if you
5:46don't have it in those in the
5:48we call it their l1 cache the top level
5:50cash the smallest fastest most expensive
5:52cash
5:53well try it in the l2 cash the level two
5:55cash maybe there's even a level three
5:58cash so all these things
5:59are ways to try to catch the data to
6:01prevent me from going to sacramento the
6:02whole point of sacramento's too far away
6:05that's the point so here's the picture
6:08we saw before you saw this picture
6:10and i i hid this here we go let's see
6:12what happens
6:14there it is so that is the reality now
6:18i'm kind of revealing the
6:20revealing the onion that i've got the
6:23cpu
6:24has this has its core doing something
6:26got registers
6:27and then i'm going to first go to my l1
6:29cache and if that fails my l2 cache
6:31and that fails my l3 cache and every
6:33time i go to a level below
6:35the same rules apply it's bigger
6:38slower and cheaper per bit so that's the
6:41idea
6:41and the lower ones are always a copy of
6:44the ones below
6:45unless i have what
6:48right back if i have a right back right
6:50policy they may not be a copy they may
6:53be
6:53inconsistent or stale the lower guys may
6:56be stale depending if i have
6:58a right back cache don't forget that we
7:00mentioned that before
7:03so let's see l1 l2 l3
7:06the parameters on my computer are about
7:09this mac
7:11here we go system report
7:15here we go can you see this picture what
7:18does it say
7:22says i've got a level two cache per core
7:26doesn't say what my level one cache is
7:27but clearly there is a level one cache
7:29it just doesn't say it it's part of the
7:31internal cpu it's not even showing that
7:32number but we can look at the i7 specs
7:35to see that
7:35but i have a level two cache per core i
7:37have a multi-core machine
7:39i've got four cores in this laptop
7:40there's a little bit older
7:42and i've got 256 in my level two
7:45cache per core every core has its own
7:48level two cache
7:48and certainly every core has its own
7:50level one cache but
7:52there's a shared level three so all
7:55we'll talk about we haven't talked about
7:55multi-core at all
7:56but each of those cores shares an l3
7:59which is big massive compared to that
8:01eight megs so eight megs is really big
8:03how many bits
8:04it makes people eight megs 23 bits
8:08256k is how many 18 bits
8:12for l2 cache so kind of neat that i've
8:15got
8:15uh and and at the bottom and my america
8:18at the bottom is i got 16 gigs
8:19for overall ram so kind of neat to be
8:22able to see this and
8:22look at a particular setup for a
8:25particular computer
8:27now let's analyze this well you think
8:29you're so fancy
8:31what's the benefit of this well let's
8:33let's look let's look at what the
8:34equations are first for my a mat how
8:36does a mat change if i have an l
8:37level two cache remember before amat is
8:39hit time
8:40l1 hit time plus l1 miss rate times
8:43l1 missed penalty but now
8:47what's the l1 missed penalty the l1 miss
8:51penalty
8:52is well if it's in
8:55l2 it's just l2's hit time
9:00plus remember i'm paying the l2 anyway
9:02plus
9:03the l2 miss rate times the l2 miss
9:07penalty
9:08so if i look at this it's almost like
9:09it's a recursive you can imagine it's l3
9:11now 405
9:12in recursive way like this so these
9:14equations kind of nest in this beautiful
9:16way
9:17so amat overall is l1 hit time
9:21times l1 missed rate times the quantity
9:24l2 hit time plus l2 miss rate times
9:28l2 ms penalty complicated just write it
9:31down you'll have it
9:32and in fact let's do an example very
9:35simple example
9:36hit time is one cycle miss rate is five
9:39percent what
9:39whatever 20 is a miss and the penalty is
9:4220 cycles
9:43what's the a mat well it's one you're
9:45paying the one all the time
9:47plus one twentieth times 20. that's one
9:50oneplus one cycles is two cycles for
9:51that that's a very simple for the l1
9:53situation
9:56so ways to reduce the miss rate make a
9:59larger cache
10:01just have a larger cache that catches
10:02more things we love that
10:04um the hit time of the first level cash
10:08is less than the cycle time
10:09so that's great we the first level cash
10:12is less than the cycle meaning i can get
10:13to the first level cash
10:14at a fraction of a clock cycle but much
10:18slower for other other other
10:20larger caches more places to put it so
10:22change your associativity
10:24my goodness think about associativity
10:26handling some of those conflicts we used
10:27to have for the complex misses
10:29fully associated if you saw that the
10:30block anywhere n-way goes a particular
10:32place
10:33in general typical scale of these things
10:35i've kind of showed you before and l1 is
10:37in the scale of
10:38kb kibi it could be bits it could be
10:41bytes i'm sorry it could be bytes
10:42miss rate is one to five percent that's
10:44great
10:45hit time i talked about being in one
10:47cycle miss rate is like what missed rate
10:49is five percent even that's
10:50one out of come on one out of every 20
10:52is the miss rate
10:53i'm hitting a lot of hits i love that
10:55that's just great
10:56l2 which i showed you my number i think
10:59it was 256k
11:02hit time a couple clock cycles there's a
11:05different technology used for that you
11:06might use
11:07sram for that or something usually l1 is
11:09on chip l2 might be on chip
11:11might be depending on the older system
11:13might be an sram um
11:15miss rate is now much larger and you
11:17might ask you know wait why is
11:19the fraction of l1 missing okay why is
11:21the miss rate
11:23so high for l2 it's so small for l1 why
11:25it's so high for l2
11:26partly because l1 got all the good stuff
11:29all the really good temporal coherence
11:31happened in l1 and l2 is just kind of
11:34well whatever other axis pattern you
11:36have is l2 so in fact l2 does pretty
11:38well
11:38misread is not that bad it's not i mean
11:40miss red is only one-fifth or so
11:42but it's not 120th um it's because l1
11:44got all the good stuff it's really what
11:46happens
11:47um let's look at example with an l2
11:49cache let's do our a mat with an l2
11:51cache we have all these parameters i've
11:52got five terms now we got to think about
11:55so let's do this together what if i have
11:58an l2 cache
12:00how much is okay l1 hit time make one
12:02cycle miss rate is five percent
12:05l2 hit time is five cycles l2 missed
12:07rate is 15
12:08let's just do this percentage of l1s
12:10that miss but
12:11but are missed in l2 also and
12:14l2 missed penalty 200 cycles so this is
12:17these terms i plugged them into the
12:18equation i showed you three slides ago
12:20and i get um average memory actually the
12:22l1 miss penalty what's the l1 miss
12:24penalty
12:25well it's the l2 hit time plus the l2
12:28miss rate times the l2 miss penalty
12:30that's what that means
12:31so that's 5 plus 15 times 200 is 35.
12:34okay so that's the l2 l1 miss penalty if
12:37you miss l1 you're paying 35.
12:40you used to pay 200. look at this l2
12:42missed penalty means if you have to go
12:43to sacramento it's 200. now i'm only
12:45paying 35.
12:46that was are you kidding me i'd rather
12:47pay 35 than 200 for sacramento
12:50average memory access time one plus what
12:53is the l1 miss rate
12:55120th what is the l1 what is the l1 miss
12:58penalty
12:59remember i saved from ever go to
13:00sacramento with this great l2 guy that
13:02caught me
13:02it's almost like i'm driving to
13:03sacramento and somebody like
13:06i don't know i don't have an example of
13:08like
13:09in i don't know richmond or something
13:12hey by the way i got your paper here
13:13wait really
13:14you save me from going all the way to
13:15sacramento great grab it from l2 go back
13:17so i still get in my car and drive 35
13:20versus one
13:20but it was much better than taking the
13:22200 to go to sacramento that's the idea
13:24so the average member access i was only
13:252.75 cycles are you kidding me
13:28average memory access time for that kind
13:30of those numbers
13:312.75 cycles compare this without the l2
13:35again one cycle l1 hit time l1 missed
13:38rate is five percent again this
13:40if i have to go to sacramento it's 200
13:41cycles so one plus
13:43a 20th times 200 is that's 10 1 plus 10
13:45is 11 cycles
13:47so compare that 2.75 cycles for amat
13:51average memory access time i've got a
13:53load i've got a store that's a memory
13:55access
13:55how many what's the average memory
13:58access time
13:59i'm only paying at most kind of three
14:01cycles if i have an l2
14:02i'm paying 11 if i don't i mean worst
14:06case it's
14:06for one particular guy it's 200 but on
14:09average
14:10you know there's a lot of hits so that
14:12averages and brings the average down
14:13from 200
14:14but i don't get past 11. 11 is terrible
14:16for average memory access time average
14:18memory
14:18every load is 10 cycles i'm just sitting
14:21idle for 10 seconds
14:22crazy i add an l2 it's only about three
14:24cycles so i love that so l2s are really
14:27great for performance and that's why we
14:28add them
14:30see you next time

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 27.3 - Caches IV: Average Memory Access Time (AMAT) by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,799 words across 447 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.