YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 35.3 - Thread-Level Parallelism III: Cache Coherency

[CS61C FA20] Lecture 35.3 - Thread-Level Parallelism III: Cache Coherency — Transcript

by CS 61C Departmental · 4,095 words · 646 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now let's explore cache
0:03coherency one of the hardest
0:06parts of putting together a system that
0:09has
0:09multi-core and each core has some number
0:11of caches and the caches are either
0:13shared or not shared
0:14there's hard stuff so from the point of
0:16view of an architect we need to be
0:17thinking about
0:18how to keep the cash values coherent you
0:20saw the last i ended the last lecture
0:22with what happens when
0:23they have 20 and i want to write my 40
0:25and now the wrong value happens caches
0:27should only make things faster they
0:28should never change the value so
0:30cash is the same value that should
0:32return without caches and
0:33also same with multi-core if you do it
0:35right just adding more cores
0:37adding some parallelism shouldn't change
0:39the value just give it to you faster so
0:40again
0:40we just have the same value should come
0:42out at the end of the day just faster
0:45so here's the model when a cache so the
0:48idea is when any processor has a cache
0:49miss
0:50or right you have to notify the other
0:53processors there's a
0:54interesting way we talked about the only
0:57way you can connect with other
0:58processors
0:59other cores is through memory i can
1:01write your variable and wait for you to
1:02read it but there is a way to actually
1:04communicate with them that we're going
1:05to add and we can ask them to do things
1:08we can
1:08ask for their values in a certain block
1:10i can also ask them to invalidate a
1:12block and the way invalid blockers
1:13should make it invalid very easy
1:15so we're going to add some communication
1:17between cores to be able to actually do
1:19some of the things we're going to do
1:21so if i'm only reading in the model that
1:22we modeled before from the last lecture
1:24we're only reading
1:25we other processors can have copies we
1:26all have copies it's fine we're just
1:28reading it's just
1:28just a read-only memory finally fine on
1:30rights
1:31you can imagine we have to invalidate
1:33the other copies um
1:34and so we talked about it we that we
1:37talked about the
1:38some researchers came up with a way a
1:40protocol what they called the snoopy
1:42product protocol
1:43to think about different ways to
1:44categorize um
1:46each block in each core as one of
1:49several
1:49states and then depending on what you're
1:51doing reading and writing
1:52you change the values in those states
1:54it's a kind of interesting way to do
1:55think of that and the other cool thing
1:56is
1:56you can snoop across to ask what the
1:59values of their
1:59of their right here's a here's a here's
2:01a here's an index
2:03um here's a tag do you have the same one
2:05and if so what's your state
2:07and then do something we can have that
2:08communication and i can say please
2:10invalidate your copy if you have the
2:11same one so that's really neat
2:12and we always have to check the tags to
2:14make sure it's the same guy that's
2:15important
2:16so how do we keep them coherent each
2:19cache is going to get
2:20of each block you're going to keep track
2:21of some set of bits to keep a track of a
2:24state
2:24we're going to label these states number
2:26one shared this is like reads very easy
2:29we're all i have an up-to-date copy so
2:31this is from the point of view of each
2:33core each core has a if you're shared it
2:34means that i have an updated copy of the
2:36data
2:37and other caches may also have a copy
2:39just like the read the easy case
2:40shared everything's shared five people
2:42shared a hundred people shared oh fine
2:44modified is different modest modified
2:47says
2:47it's model from my point of view it's
2:48modified in my if my state is modified
2:50means that i have the up to date copy
2:52and my cache is update copy it's changed
2:56it's dirty and what dirty means is i'm a
2:58i'm using a right back system so the guy
3:00behind me
3:00sacramento is out of date and
3:04no other cache has a copy we don't mind
3:06this is like
3:07this is like um vanilla right back
3:09caches a right-back cache is that
3:11i have the possibility that my value is
3:13out of date with memory that's no
3:14trouble i can reads and writes i don't
3:16think a memory and only when i kick this
3:17guy out or
3:18i'm paged out or something i need to
3:20then flush that back and push it back to
3:22memory so i only go to sacramento when i
3:23need to
3:24so that's a but the key here modified is
3:26nobody else can have that
3:29okay so that's the idea this is for a
3:32bop block by block basis there are two
3:36additional perform directional states
3:38for performance optimizations
3:40we're going to add the idea of exclusive
3:43an exclusive says
3:44it's similar to modified but exclusive
3:48differs in that memory
3:49is up to date so if i'm exclusive that
3:52means that
3:52nobody has a remember modified meant
3:54nobody has a copy exclusive means nobody
3:56has a copy but in the exclusive case
3:58memory is up to date
3:59and modified it is not up to date okay
4:02so this is great i know from exclusive
4:04that means if i if the blocks replace i
4:06don't have to write to memory because i
4:07know that in a way my dirty bit is not
4:09flagged so it's a little exclusive kind
4:10of replaces the dirty bit in that sense
4:12of it
4:12um and i supplies data on a read if i'm
4:15going
4:15if i'm making it read obviously i have a
4:17copy so i can just read from that fine
4:19okay and members up to date so i don't
4:20have to kick it out if i ever kick this
4:21block out i don't need to go to memory i
4:23like exclusive as well
4:24owner owner's a little bit more
4:26complicated so we'll spend some time
4:27talking about it
4:29owner says my copy is up to date i'm the
4:31owner and what that means is
4:33other caches can have a copy but
4:37i'm the owner and they have to be in a
4:39shared state
4:40so when you have the shared state i have
4:41to be the owner so let's think about
4:43that
4:46what it means is the fun part and i'll
4:49read this to make sure there's a lot of
4:50details let me make sure i read them to
4:51make sure you understand all the pieces
4:52of this
4:53so i'm one with several with a valid
4:55copy the other copies are shared
4:57but i have the exclusive right as the
4:59owner i have the exclusive don't get
5:01this confused with the word exclusive
5:02i have the i'm the only one who has a
5:04right to make changes to it
5:07but how do i make those changes this is
5:08the fun part this is the optimization
5:10i make changes if i let's say the value
5:12is 20. we all have 20. we're all good
5:13but i'm the owner
5:14i want to make it to 40. okay
5:18one model if i use this i
5:21and by the way um
5:26memory is consistent here so we're not
5:30talking about remember being
5:30inconsistent the only so far the only
5:32remember consistent is inconsistent
5:33is in the modified state okay
5:37sorry memory might be inconsistent i'll
5:39say this again memory might be
5:40inconsistent
5:41i'm the owner i have the updated copy
5:44memory might be inconsistent
5:45okay now watch this other caches
5:49are shared and but i'm the owner i'm the
5:53one who owns really it sums up the
5:54memory spot
5:56and now if another copy
6:03if i make a change it was 20 for
6:05everybody but i'm the owner
6:07how do i make it 40. really but they're
6:10shared
6:11what i could do is i could
6:14share my 40 with the other caches
6:18so watch this i pushed it it pushed the
6:2040 to my cache now it's a 40 that's the
6:22right value
6:23and i push it to the other caches via
6:25the interconnect
6:26now they all have 40.
6:30now here's the catch what happens if
6:32there's if there's a core
6:33that never had in their cache at all and
6:35they go to read the value remember it's
6:3640 and all the people who are using it
6:38i'm the owner they're shared and they're
6:40all reading the 40 correctly
6:41and i want to go grab the current value
6:43i'm not going to go to memory first of
6:44all i'll never go to memory if i can
6:45help it
6:46it would be great if when i went to read
6:48this value i could ask the other guys do
6:50you have this block in your cache
6:53and who's the owner somebody asked guys
6:55hey folks
6:56could the owner please tell me what the
6:57value of this anybody have it
6:59so you can pass this to the other course
7:01and they
7:02say the other caches say hey i'm the my
7:05cat i'm the owner now i would say
7:06i'm the owner it is 40. and i'm
7:08basically passing
7:10the 40 to another core and never had it
7:14then they become shared and then they're
7:16fine so this is nice look at this
7:18so it says owner cash blast line says
7:22must
7:22this is this the key here owner cash
7:25lines must
7:26respond to a snoop request with data so
7:30that that's the snoopy idea
7:31i didn't have it i want to read a value
7:34it's a 40 but i don't know that
7:35my cash is empty i ask does anybody else
7:37have it and the
7:38owned cash has to respond with the 40
7:41i'd load the 40 put it in my guy i'll
7:43become another shared
7:44family okay another model is
7:49if i wanted to modify it
7:52i could i could change it to the
7:54modified state if i wanted to
7:56my cache line can be changed to the
7:57modified state member modified means
8:00modified means it's out of date but
8:03i'm nobody else has it so they're all
8:05invalid
8:06so you could hear this this line says
8:08the cache line may be changed to the
8:09modified state after invalidating
8:11all shared copies or
8:14change to the shared state by writing
8:16the modifications back to my memory
8:18so two ways to kind of get out of this
8:20if i'm the owner other people have the
8:2240 memory is wrong
8:24okay that's what we got i could either
8:27write my data all the way to memory go
8:29to sacramento write the 40. now that's
8:31consistent
8:32all the 40s have it they all had the 40s
8:34anyway that was fine and now
8:36we're all shared so i go from owner to
8:38being shared again anybody else can now
8:39grab the owner if they want to change it
8:41so i could do that
8:42i could also decide you know you had the
8:4440s but why not just inval if i
8:46invalidate you
8:47then i can now be changed to modified
8:50now modified means
8:51still inconsistent with memory i've got
8:54a 40 memory is something else
8:56but i'm modified i can invalidate them
8:58as well so there are two kind of options
9:00you can
9:00as you're thinking about how to
9:01transition there's a whole trend is a
9:03very complicated transition state
9:05diagram
9:05that talks about all these states and
9:07how you move for each of the states we
9:09don't teach n61c we teach an
9:10architecture class you learn about in
9:12other classes you'll learn
9:13but there are ways to think about how
9:14you move from owner
9:16to how do you move from owner to shared
9:18i just told you you can move forward to
9:20share by writing to main memory
9:21now the memory is consistent and now it
9:23can be part of the shared family
9:25or how to move from owner to exclusive
9:27if i wanted to
9:28by doing that i would just invalidate
9:29the other copies and now i'm the only
9:31exclusive one
9:32it's still not in main memory it's still
9:34modified not not it's inconsistent with
9:36main memory but i'm
9:37but i'm in the model not exclusive but
9:39i'm in a modified state
9:40so all those things are there
9:42complicated state transition diagram
9:44here's the picture here are all the
9:47valid
9:48pairings this is me
9:51i'm on the left i'm going to change pen
9:53real fast here
9:54i'm on the left
9:57and here's me and here's all the others
10:02others and so here's me
10:05i can be in the modified state remember
10:07the modified state
10:09and nobody else there's no other states
10:10that can be for them they have to all be
10:12invalid modified means nobody else in
10:14any other state modified means i have it
10:15everyone else
10:16doesn't have a copy at all of that block
10:17we're talking about a block on a block
10:18level
10:20or i could own it i talked about before
10:23if i own it other people could be
10:25invalid you cannot have it at all that's
10:26fine you never did anything i'm a core
10:28that's asleep
10:29fine you're invalid you don't i don't
10:30care about you your cash is empty or
10:32cold
10:33but other people could have a shared
10:34version they're all shared
10:36while i'm owned okay there's that one
10:39or i have exclusive rights and then
10:42nobody else can have it that's what
10:43exclusive means
10:44or again i can be the shared copy and
10:48somebody else is the owner
10:49or we could all just be doing reads and
10:52have a shared copy and you have a shared
10:53copy too so that's it
10:54very simple case but you can never have
10:56for example you can never have two
10:57two people this is x you can never have
10:59two exclusives you can never have two
11:01owners
11:02you can never have two modifieds this is
11:03very clean this is a very clean way of
11:05thinking about the states of the cash
11:07but in a clever way the owner is a very
11:09clever way that
11:10people could be without having to go to
11:12sacramento be reading for me very
11:14interesting
11:15to think about how did this stupid
11:16protocol where you could be poking and
11:18talking to
11:19it's almost like like sacramento's far
11:20away and like we're talking it's almost
11:21like the teachers at the front of the
11:23room and we're kind of talking to the
11:24neighbors hey
11:24did you do you want a piece of cash out
11:26here here's the value wanna go do you
11:27have it yeah let me grab it from you
11:28you're the owner i'm sure okay grab it
11:29now
11:30that the conversation's happening along
11:32in the back row
11:33as the memory is all in the front as
11:35kind of as the instructor in some way
11:37so let's actually look at one of these
11:38models so now
11:41let's go back in time now i've got two
11:42caches that have a
11:44memory location a thousand have a copy
11:46of the value 20.
11:47and i want to write a 40. it's not
11:50processor zero it's not in my cache
11:52so i check my interconnect network and i
11:55decide to
11:56invalidate the other copies i evaluate
11:59their copies
12:00and now i'm going to read the 40 i'm
12:01going to store the 40 to my cache
12:03store it in memory and we're all
12:05consistent so
12:06this is a way that we can we can make
12:08sure that we never have the problem
12:10where i wrote a 40 and you still keep
12:11your 20s but i have a 40. and so two
12:13blocks are very
12:14you'll never have that case um where two
12:17blocks
12:18don't have the same value ever um if i'm
12:20going to do a right to a 40 i'm going to
12:22either invalidate them
12:23or grab owner and pass my 40 to them and
12:26update them for 40 but you're never
12:27going to have
12:28a kind of a resting photograph of the
12:29state where this guy thinks it's 1040
12:32and this one thinks it's a thousand
12:33twenty never going to happen
12:35either i'm writing a 40 and i invalidate
12:37everybody else and nobody else has it
12:38and they just had copies anyway that's
12:39fine caches are just copies they were
12:41just read only copies not write
12:42writ written copies not out of sync they
12:44were synced with memory that's fine
12:46or i have a 40 and i'm going to pass the
12:4940 to other people over there we can
12:51still
12:51whether memory is inconsistent or
12:52consistent is all there but the owner's
12:54job
12:54is it to finally connect with memory if
12:56it gets kicked out make sure to write
12:57that 40 eventually memory that's the
12:59part that's interesting here
13:00really fun and really interesting if you
13:02if you dig deeper into
13:03what the the snoopy uh state state
13:06diagram is and how you move from state
13:08to state kind of fun
13:10now let's bring up a really big issue
13:11and this is something that we're gonna
13:12we're gonna see
13:13often as we have more and more cores
13:15dealing with really big blocks
13:18so what's the problem here looks this
13:20looks fine i've got a block size of 32
13:22bytes no problem
13:23i've got cross two processor two caches
13:26and you can maybe already see there's an
13:28issue here
13:29processor zero is reading and writing
13:30variable x that happens to live
13:32at address four thousand processor y is
13:36reading writing variable y
13:37that happens to live at address forty
13:41twelve
13:43well x is it four thousand why is it
13:46forty 12
13:47these are independent these are totally
13:48independent i'm really writing here
13:50you're reading writing there
13:51well what's going to happen can you can
13:53you already see what's going to happen
13:55well that block is going to ping-pong
13:58between those two caches as
13:59each one thinks they're accessing the
14:02same
14:02information and you want to make sure we
14:04don't have those issues and so
14:05only one person is going to own it even
14:07though in theory you could build a
14:09system
14:09that both of them could write to just an
14:11area of it but because you only checked
14:12at the block level
14:14you can't have that it'll just ping pong
14:16in and out in and out in and out
14:17from the two areas and and each one
14:19thinks that i have it no you have it no
14:20i haven't now you have it
14:22and this is a problem so how do you
14:24prevent it how do we let's see
14:25how do we prevent it well one way to
14:27already pause the video and think about
14:28it well one way to reduce the
14:31possibility of is i have smaller block
14:32sizes
14:33the larger the block size the more the
14:34chance of i'm going to be writing to
14:36areas of the array and multiple areas of
14:37the processor might do that
14:39you could also think from the
14:40programming standpoint if you knew the
14:41size of the block
14:42you could make sure that you never if
14:45you did this really well
14:46that you never have a processor um
14:50share any space at all on the same block
14:53line as anybody else just make sure that
14:54you own this part of memory and i'm down
14:56here and you're done there and you're
14:57down there and you have that issue as
14:58well
14:58um so let's think about how to resolve
15:01this let's think about
15:02let's see let's this is our review three
15:05c's these were the three kind of misses
15:07you had with caches you have a
15:08compulsory miss
15:09these are a cold start miss you've got a
15:11block never seen before
15:12everyone has to do first access to the
15:14block you got to take this the solution
15:15for a cold start miss
15:17is for compulsory misses you increase
15:19the block size
15:20um certainly have more penalty to go to
15:22sacramento but when you're there
15:23now you're loading in more of it and now
15:25you have less of memory
15:27the larger the block size less of memory
15:29has to take
15:30to kind of from a block point of view
15:32have to take that hit i grabbed it and i
15:34grabbed a huge block that's great
15:36and while i was the second i loaded now
15:38all of those guys don't have to have
15:39compulsory misses because they're loaded
15:41in
15:41so that's nice capacity misses
15:44which means not compulsory but at
15:46capacity capacity miss well
15:48i can't i can't if i only if i only had
15:52a larger cache
15:53i wouldn't have that capacity we'll make
15:54the cash larger solutions make the cash
15:56larger
15:56okay or a conflict miss we saw that so
15:59not compulsory or capacity but a
16:01conflict miss
16:02the solution is well think about more
16:04associativity
16:05don't have a direct map or 2a make it
16:07four-way or make it fully associative
16:08think about that so either increase the
16:10cache size increase the sensitivity or
16:13incl
16:13work on the replacement policy maybe
16:15look at the workload you're having
16:17be smarter about your replacement policy
16:20the fourth c this is the fourth c
16:22it's called a coherence miss it means
16:25within one block two different
16:28cores think that they have that these
16:31variables that may be distinct
16:33are actually shared and so now you're
16:35going to have them loaded in and out
16:37as we saw before i have to invalidate
16:39the other copies because i'm making a
16:41reading to write to this and have to
16:42evaluate the other copies but no way the
16:43other guy isn't actually modifying that
16:45verb i modified this part in the block
16:46i'm modifying here your modifying there
16:48sorry the rules say that if i own this
16:51block
16:51nobody else can have it so that we don't
16:53have the wrong copy so i have to
16:54invalidate your copies and so you end up
16:56having these things ping pong here
16:57so this is also known as a communication
16:59myth we don't this is really hard it's
17:01really really hard
17:02and in some sense coherence misses can
17:04dominate total misses overall with
17:05parallel programs that's really
17:07interesting
17:07you had these three c's you thought that
17:08was the world i'm telling you there's a
17:09fourth c and i'm telling you not only
17:11that that the fourth c actually can be
17:13the biggest
17:13problem the biggest number of misses in
17:15this case
17:17all done last slide on thread level
17:19parallelism
17:21in conclusion openmp is a beautiful
17:23parallel extension to see there okay all
17:25right
17:25let's step back even farther and this is
17:27off off script
17:28you don't have to program in c you can
17:30program a lot of other languages that
17:31may be easier or harder or
17:33more useful for your particular problem
17:35if you're living in c
17:36though openmp is a great solution to be
17:38able to bring parallelism to your c
17:40code you've got these pragmas you've got
17:42private variables reductions parallel
17:44four parallel fours this will get you a
17:45long way so play with that
17:47we know this is easy to learn but not
17:48high level so you can get you into
17:50trouble
17:51thread level parallelism one of the
17:52issues as you're building a system for
17:54it as you're one of the now the
17:55architects below the hardware line
17:57is dealing with cache coherency coming
17:59up with protocols ways you can have it
18:01and mention it there's a state diagram
18:02where you label every block with these
18:04tags and
18:04think about that that you want to reduce
18:06this that you want to first of all make
18:08sure that your system always works
18:09so cache coherency first at the base
18:11level make sure that your cache doesn't
18:13give the wrong value
18:14that's part of the hard part of this and
18:16false sharing is a concern
18:17the larger a block size this sharing
18:20these two variables these two areas of
18:22memory are not being shared
18:24across these two processors that trust
18:26these two cores there's two threads
18:27working on these two cores
18:28but in fact there is a false sharing
18:31that says nope sorry
18:32it's the same block it must be the same
18:33one no it's not they're at different
18:34areas sorry
18:35we're not really the hard way to solve
18:36that so that's a problem and that causes
18:38these coherence misses
18:40that's it watch out for the block size
18:42for there we're done we're done with
18:43thread level parallelism
18:44we will see you next lecture where we
18:46talk about drum roll piece
18:49warehouse scale computing and map
18:51produce we'll see you there

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 35.3 - Thread-Level Parallelism III: Cache Coherency by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 4,095 words across 646 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.