So, we're gonna look at, two, ways to go
about implementing Snoopy cash coherence.
Update protocols, and validation
protocols. And we're gonna be focusing
today's lecture on what are called writes
invalidation or write invalidate
protocols. They're, they're more common
today. but I did want to bring up right
update or what are called right broadcast
protocols. In this other sense they kind
of, mirror something like, a write through
cache, versus a, write back cache. But
it's not, it's not the same thing. You can
actually mix and match write back and
write through with these different ideas
here. But let's, let's look at what these,
these two, ideas in the Snoopy protocols
are. So in a write update, whenever a
processor does a write and broadcasts it
across the bus to every other processor.
And every other processor can have data
in. Cache, it just updates the data in
place, because the broadcast, it has all
the data, it has the data up, up to date.
validation on the other hand, we're gonna
look at when a occurs it'll actually
invalidate other cache copies, the other
caches. Okay so, these two cases update ,
update . . The first case is the processor
takes a write miss. So, it takes a write
miss. Well, it's gonna broadcast the data
onto the bus, and update everybody. So
it's just sort of writing through. But not
just writing through to main memory. It's
also writing through to everyone else's
cache. What's nice is, when someone goes
to do a read. Well, there's no real. Like,
the, there, there's a read miss if you
just go out to main memory. And you're
guaranteed that main memory always has the
most up to date version. if it was in
your. The cache before. And other cores
and other caches broadcast will update
your value. So it's in your cache. You
have the to be a also in these update
protocols. Not the case with invalidation
protocols. So, our right invalidation
protocols. We're gonna have a, let's say
there's a right miss. Well, on a right
miss, you actually go in and validate. All
the other caches, copies of it, before you
can go get the data. So if another cache
had the data, it's going to cough up the
data and put it back in the main memory.
And then you're gonna go off to main
memory and get the data from there, in,
our, our naive invalidation protocol. So,
first step is if you want to do a write
and it's not in your cache, and, you don't
have Let's say a certain has access to it.
You're going to yell out to the bus, I
want to ride to this address. The caches
are going to. If someone responds and says
I have that data already. You have to wait
for them to put it on main memory, and
then once it's on main memory you can go
get that data. By repeating this.
Something kind of similar. you are
basically, when you yell does anyone have
it. Someone's data is not in your cache it
might be in someone else's cache. Someone
might pipe up and say I have that data and
I have it dirty. So I'm willing to take it
and put it back to main memory and you can
go get it from main memory but there's
other cases that can happen in this
protocol or in invalidated protocols. So
other things that can happen here are you
can say that who has that data? Does
someone else might have that data but they
might not have a legal copy of the data so
they might not pipe up. It might not say,
I have a copy of it. And instead, you
might just be able to get that data from
the other. So, let's go through a couple
different cases, another, a couple
different protocols that drop out of this.
The first one we're gonna look at is
called MSI, and it just stands for the
three states that each cache line is gonna
be in. so for these cache coherence
protocols, we typically try to track what
state they're in and whether they're
shared or not, on a per-cache-line basis.
Not on a per word basis. similarly, it's
like how we, you know? We only track the
tag bits and the valid bit and the dirty
bits, per a cache line basis. Because it's
just less bookkeeping to keep around. So
here we have our cache l-, or our cache
tag. And before, we had, let's say, a
valid bit and a dirty bit. And then the,
address portion of the tag. . Or the tag
portion of the address, rather. And in
this step, what we're gonna do, is,
instead of having a valid bit and a dirty
bit. . We'll use these bits to encode a
state. There's a little state machine in
there, practically. And, first off,
there's three different states here.
Modified, shared, and . Before we go
through the protocol, why don't you just,
say what these three different states,
roughly, roughly mean. So, in NSI
protocol, means for that particular line.
You don't know anything about it. It's not
in your cache. This is the equivalent.
Though it did not be valid you know, so a
caption so about, not, not, not here. Just
because one coster is cash as it me
bellasty does not mean a different mustard
can't have any different states. So I want
to make the big point here that the states
are not vocal. It's not like per cash line
the state is in the, the cash log is in
the end state we'll say. No, instead. Each
cache keeps track of a line. And it might
say whether it's actually in the cache,
not in the cache, and what state it's in.
And it can be different states. Now there
are some cross, products of cases which
are just not allowed. So we'll see, In
this protocol, two caches to not have the
same cache line and modified statement at
the same time, the modified state. Cuz
that would basically mean that two caches
are trying to modify the same piece of
data. And that's, that's what we're
basically using the . protocol . Okay? .
Okay. So, three of the states here. I is
invalid. It means you don't really know
anything about that line. S is shared,
which means that you have a read only
copy, or processor one here. Processor one
has a read only copy of that data. And
other caches can also have read only
copies. That data. Hence the, the term
shared. Because shared. But only in a
sense. So if everyone around here has
copies, we're not gonna have any coherence
problems. We start to have problems when
multiple people have writable copies. So
in this protocol, we're gonna have this
modified state here. Meaning that, that
line is now writable by a particular
cache. And we will actually have to
transition to this state. Before we can do
any rights. And everyone, as I said
before. If one processor has, or one cache
has, a cache state. It's modified state.
Everyone else needs to have an invalid
state. Or, have not in the cache. And this
is gonna guarantee us in hardware, that
the cache line is effectively, only being
read by one cache or one processor at a
time. Okay, so let's, let's look at some
of the, the edges here in this stage
transition diagram here. So the first
thing that we're going to look as is
cluster one, we'll say starts out with a
line not being in its cache, or turns out
with a line being of its cache. So our
first state arrow here is that cluster one
wants to read. It doesn't wanna write the
data, so it doesn't read here. And.
Invalid before or wasn't in the cache. So
it'll do a read from main memory. And
reading the cache and sharing. Now, we
have other trying to read this. And in our
protocol. What the other are gonna do is
when they. They're gonna actually issue a
request for that line. And if someone else
has something to say about it, they have
to pipe up during that, during that time.
And we'll see how that happens. Later. But
right now, other processors try to read
the data. Read that, read that line. No
one pipes up. And even the first guy, who
has this, this data in the shared state,
doesn't say anything. So the other
processor's gonna still read it from main
memory. And their transitions effectively
look the same. They're just going to load
it into their cache in the shared state.
So pull it in, and share. Okay. So now,
we're gonna look at this from a
perspective of P1. If you want, had it in
the shared state. And some other processor
wants to do a write. So they do a request
for exclusive access of that line. Because
processor one's cache only had it in the
shared state. It doesn't need to actually
say anything in response to that request
for exclusive access. But what it does
need to do is it needs to self invalidate
its own data. So . But instead, what it
has to do is transition. From s to invalid
because the data ends' catch is no longer
good because someone else is about to go
write it. So before it can write that
other coster issues its intent to write
and at that time it actually does its
state transition in its own catch. Okay so
let's look at the flip side of that let's
say processor one thinks that it wants to
do a write. Well so what processor one's
gonna do is its going to issue this
request to write or intent to write
transaction across the bus. And everyone
else is gonna do that transition. And
after it does this intent to write
transaction here, it's going to transition
from the S state to the M state. And only
at that time is it able to do the write,
once it gets into the M state. And it can
also do further reads and writes. It
doesn't have to ask anybody. So this is
pretty cool . invalidation protocol, you
can do reads and writes. We don't have to
broadcast any information across the bus.
It has the modified state. This processor
can read the data. It can write the data.
now everyone else can't read or write or
do anything to it during this time. But
that's okay, because typically in our
shared memory applications, one
processor's doing most of the writing. And
sometimes processors can go read it. And
typically that, you know, everyone's not
trying to fight for the same piece of
data. Okay. So now let's Look at the case
where in the, the modified state and some
other processor wants to write the data.
Well, this is a little bit more complex
because now the other processor is going
to issue this intent to write across the
bus, a request for to cross the bus, . And
I think someone else wants to move to the
modified state, so before they can move to
the modified state they need R, . Runs
most up to date data. So what's gonna
happen is p1 is actually going right back
to data at that point to main memory i n
our, in our basic model and assigned model
here. So get it right back to main memory.
And then the other processor is going to
be able to get it from main memory. And
transition into the m state from the
invalid state. And we'll, we'll see that
arc in a second. You could think about
optimizations here where you try to pass
the data from one processor's invalidate.
Or, one processor's , and another
processor's read. We're not gonna look at
that quite yet. optimization. But, right
now, if you're in the m state, you're
gonna write it back to main memory. And
the other processor's gonna delete it from
main memory, in this, in this state. Okay,
so this brings us to, another important
transition. Here is that, if you have it
modified, and someone else wants to read
the data, you don't actually have to
transition to validate it. You can just
transition to the shared state. And you
probably want to do this, because you're,
otherwise when some other processor tries
to read the data that you just wrote. You
know, like a producer-consumer, style
computation. You would just be effectively
invalidating your, processors cache. And
that would be pretty bad because, you're
effectively fighting locality at this
point. You're fighting. temporal locality.
And so instead when another processor
tries to read the data, we need to write
back that data to main memory. Another
processor has to go get it from main
memory. But you have the most up to date
version. And they only want read access to
it. So you're gonna transition down to the
shared state. So someone else has it
readable, and you have it readable also at
the same time. And finally we're going to
validate back up to, to M. This edge, and
that edge, basically, look around trying
to validate, invalid here. and we're gonna
look at. If you have , if you have a cash
line invalid. And you want to go get, want
a brightness. You're going to scream on
the bus. I want you to get this . And in
the meantime, the other cashiers might
have to do what you had to do in the same
cas e, so they may need to go to a write
back and they may need to say I have that
right now. . And the next Right. You sort
of wait around a little bit and then you
go get it from . And so, do we, do we need
an . yes. You need your own key that for
any given line, that the transactions,
the, the transactions in the bus are
common. And the way you do that is by
having . So people trying to invite lets
say the same line at the same time. So
we'll take two and both have an S. Share
data, and, and copies. And exactly the
same time they both wanna do a write. This
is why we need to issue this intent to
write. And we're not able to do a write
until we successfully get into the M state
here. So what's gonna happen is two
processors are gonna try to issue intent
to write. But the arbiter is only allow
one of those two to occur bus, on the bus
at the same time. It's just, you know,
arbiter says one thing can happen. And the
bus only has, you know, one, one thing can
happen at a time. Someone's gonna win. And
that might be based on sort of priority
encoding, or it might be round-robin,
depending on how you go about doing that,
or make some fairness guarantee. Someone
is going to, one of the two clusters is
gonna win. And when that one cluster wins,
they're the one that is able to take the
bus and issue this request, inu2014,
intent to write, and everyone else has to
play by that. So what's gonna happen is
the, if cluster one wins and sends this
intent to write, and cluster two is about
to send the intent to write. Now that it
sees someone else's intention to write, it
has to basically abort its intention,
attention, attempt to write and instead go
on this transition. And then what they're
gonna do is they're gonna retry the write
again in the future. And when they retry
the write to the future, they're going to
basically come in on this arc here, which
is gonna bump processor one from M to I
after the write has happened. But,
typically if you're careful about, forward
progress guarantees, so you have to be. Be
very caref ul.
You go to implement these things that, if
a cluster goes to do a write and you have
sort of retries happening in the system,
and let's say you get the data modified
into your own cache, you have to guarantee
that, that lobe that's gonna be a store
operation actually posts. Because a very
subtle mistake that's very easy to have
happen here is, you decouple the memory
system from the main processor, to some
extent, and two people are trying to do
writes at the same time, and you just have
lines basically bounce back and forth
between modifying the one cache and
modifying the other cache, modifying. Five
one cache five one daily cache is back and
forth forever, but no one's actually able
to do it in stores. So you have to make
sure you pull in your cache, atomically
though like everything else get it
modified. You are able to post at least
something till at least you have a four or
five year guarantee, and then you have a
processor . Oh. So yeah. Stick a of the
stage transitions relative to the other
stage transitions before that same line
there . Now, for right now we're gonna say
the bus only. Has one transaction
happening at a time. And that's arbitrated
by, some . So, we're not gonna be able to
see other cache lines transition . But you
can think about cases where you can have,
let's say, n transactions happening at the
same time. Number of transactions
happening at the same time. But, the
arbiter, guarantees that none of the same
address or the same , for instance. And
that actually happens in some of these
distributed protocols we'll look at in .
In two lectures, we're gonna look at. We
build these for multiple people to
basically be transitioning their state
diagrams simultaneously, at the same time,
but to different addresses. Okay, hm.
Okay, we're running a little bit low on
time here. I think I'm gonnau2014 Oh,
we'll, we'll go through this example, yes.
though this is basically reiterating what
we said before. Okay, so we have Processor
one, we'll say it has a read. So we're
gonna show two state d iagrams here. For
the same cache line. Officer one does a
read, he's gonna get it . So get the data
from memory. Officer one is right. He's
going to issue an intent to right, get it,
and then in a modified state . Officer two
now must do a read. So the first thing is
it's going to try to read this data, and
that's going to cause officer one to
transition. Does the request for reading
this data as it's trying to transition to
S here. And, and, it's not able to
transition to S until it knows that the
other processor has done the following
transition. It is basically going to do a
write back to main memory because
Processor two is reading. So it's going to
transition from here to there. And now
this modified data is up-to-date in main
memory and Processor two is going to read
the updated state. Okay, so now say
Processor two tries to write. Well, it's
gonna wanna. Transition from here to m. So
issue this intent to write. And at that
point, processor one is going to
transition to the down state. And
processor two gets it modifiable in its
cache. And it's actually to the right.
Okay. So we're gonna look at processor one
now doing a read. It's in the imbalanced
state right now. So it's basically just
going to enter in on this arc here. Though
processor two has it in a modified state.
So to transition. Here down to I. Or,
excuse me. Actually, there back to S. I
guess it's, We're gonna have . So
processor one does the read. Processor two
is gonna do the write back. And it's gonna
transition to the shared state here.
While, processor one transitions from I
back to S. Processor one does the write.
We're sort of back to where we were
before. It's going to issue its intent to
write. And the, processor two here is
going to transition. Transition from S to
invalid at that point. So this is a basic
NSI protocol, at this point. I think
that's the end of this. Yeah. Okay, so now
The last two minutes, we're gonna talk
about more advanced cache coherence
protocols. . . Okay. So quick, quick
observation here. I think we already said
this, is that, no two processors. This
protocol enforces that no two processors.
You can have a line in the m state
simultaneously. Two processors can have a
line in the S state simultaneously.
Everyone can have a line invalid. It's
just invalid. But we can't, can't . And
this really helps us keep coherence of our
memory. Because we're not going to allow
any processor to be able to have a line
exclusive. Or, have a line, and another
processor be able to read that data in the
meantime. But, be careful. This does not
necessarily imply sequential consistency.
This might be an input model, depending
on. Sort of, ordering a lot of things that
you're really not interested in. Okay, so,
we're gonna look at a more complex kind of
performance protocol. And the, the insight
that this protocol is growing out of is
that you don't necessarily need to issue,
how do I put this? in all cases, you may
not. You need to tell everybody that you
want to do it right. So we'll, we'll,
we'll go through this, But the, the basic
idea here is that we can pull in data into
our cache, into this new state here that
we're adding. Because we, we still have M,
S, and I, but we add an E state here,
which stands for exclusive. Exclusive is
actually a read-only state. But it's a
read-only state saying that no one. else
can read it either. And why we add this,
is. If, let's say we do a read, or trying
to do a write to that data sometime in the
future. We can pull it in, in this state,
and not have to ask anybody. We can
guarantee that we don't have to ask
anybody in order to transition to go to a
write to that data. So that's the, the
insight. So, same, same idea here. point
out that, This, you'll see some sometimes
in books, they'll have, they'll call this
the Illinois protocol. It was, developed
at the University of Illinois Champaign.
which is why they call it that. or
sometimes people call it . It's probably
more widely known now as the MESI
protrocol. It's a four-state protocol. It,
and one of the nice things about this is,
if you hav e sort of two state bits, it
doesn't side have three states. Well, we
need two bits to encode that anyway. So it
doesn't actually add any extra storage
space to have an extra state bit here in,
in this protocol. And as I said, this is
effectively the same load of bits we had.
Or we get a valid bit and a dirty bit
before we get cache coherence. Well we now
have sort of notions of dirty and notions
of invalid. And so these other states are
all valid. So we, we can use those exact
same key bits, and we don't need to add
any more storage space to our cache to
implement this actual variance protocol.
So something to think about. So let's,
let's walk, let's walk through all the
different arcs in this diagram. But as I
said the main difference here is we took
before we, we, we took what was before,
the shared state, and we split it into two
states. A new shared state, and an
exclusive state. Which means that it's a
read only copy. But, no one else, will
have a copy of it. sort of guaranteed that
no one else will have a copy of it. And,
by default, when we bring in a cache line
from main memory, and we do a read this,
in this protocol, we're most likely going
to. Bring it into the E state, o let's see
if I can this protocol. We're just gonna
bring it into the E state. So if one cache
does a read of . Instead of having it in
the shared state. Instead, it's going to
bring it into the exclusive state. So
that, that same processor, in the future,
write. It will transition over to this
state with no messages on the . So we, we
effectively in a few, a few sub states.
And it's pretty common for someone to do a
read . Somewhere in a cache line, and then
do a write. . So let's say you're try to
increment that, variable. You're gonna
read it, add one to it, and then write
that same value right back. . Okay. So,
this is gonna look pretty similar to what
we had before. And we're gonna say that a
read miss, can still happen. So, if you're
processer one, and the read miss. And the
data is in someone else's cache, we
transition. into the shared state. So when
you're reading this, you don't get
exclusive for this, this state. But
instead, because since someone else's
cache, they pipe up and say. Oh, this is
already shared. Pull it in as shared. So
we're gonna transition from invalid to
shared out of read miss. But we're also
gonna have another arc, here, which is a
read miss, but it's not shared, it just
came in from main memory. Sort of given
that idea that it's likely that we're
actually going to have a read and then a
write. And you just pull it in without
making contact, anybody . But otherwise,
this actually looks pretty similar to the
MSI that we had before. If it's read
shared, you start off with an s here. any
other processor. Someone responded back,
and says they had it shared. So they know
not to go straight to the E. . But you're
just gonna stay in this, this state. Now.
When, let's say, you have attention right,
you're going to probably . Mm. And they're
going to transition valid. So similarly,
like, before, only one cache is ever gonna
happen in M. But, unlike before, we're
going to say that only one cache can
happen either in M or V. That's what E
means, it's exclusive. . So can read and
write in this, in this state. Now,
exclusive here.
Exclusive.
Processor one can read it, but if anyone
else tried to read it. Oops. Where'd it
go? There we go. If other processor tried
to read it, we're going to actually
transition from E to S, to our shared
state here. But if we have a cache line E,
and we want to do a write, we don't have
to invalidate anybody. We don't have to
arbitrate on the bus. Instead we can just
transition from E to M directly and do the
write. Because we had exclusive already.
the rest looks pretty similar to NSI.
You're unsure, no person wants a fuel
rise, we're in transition from S to I. And
likewise, if we were in the exclusive
state of no possible rise in fuel price.
We're going to transition the I. And note
the difference between this arc and this
arc. So, going to read, we can just
downgrade to shar e.
Other processor's going to write, we need
to make it invalid, from these read only
exclusive stage. . So, what are we . We
added other processors. Reads, this is the
same thing we had down the side here. That
protocol. We had a, we had it modified.
And the other processor wants to do a
write. We need to write back the data, and
transition to shared. And another
processor wants to do a write. We
transitioned from the modified stage to
right back to data. We need to transition
to analyses. So, it looks pretty similar
to SI Except we visioned the shares state
into two different states. , So far. Okay.
So I'm going to stop here today and just
say next time we're gonna dish up, from a
[??]. coming around here and we have
another stage [??]. What is actually used
in the called [??]. And this actually
allows us to start to use cash transfers.
Without having to go out and read memory
to get the data all the time. and then
we'll also talk about what's used in the
sort of, standard Intel processor, which
also allows us to . But effectively adds
another state which functions the same as
our shared state. But allows us to sort
data. Okay, let's stop here for today.