Okay. So lets move up the physical implementation of buses. And move to some
more logical problems. With sequential consistency mixed together with coherent
protocols. So we're gonna look at them all here, we have two processors. Cpu1 and
CPU2. And we are going to introduce caches into our SMP, or Symmetric Multi
Processor. So we have two caches here. And looking to address A. So there's two
caches in this memory. Let's look what happens. Oh, let's say, if we have a right
back cache. And at the beginning of time, everyone has the 100 for address, when,
when, address A. So cache one, cache two and the memory all agree that address A
has value 100. Okay. So now, we see that, let's say. Cpu one wants to update A when
it's 200. Okay. In a write back scenario, it's just gonna do a store here into this
location. But it's write back. So this data doesn't show up anywhere else over
here, until it actually gets invalidated. Now, all of a sudden, if we don't have any
sophisticated protocols. Cpu two here, let's say, does a read of address A. All
it's gonna get. 100 and not 200. It's gonna get the wrong out of date value.
Well that, that's not super great in fact that easily violates a bunch of
consistency now that might have easily had some other problems like trying to let it
roll backwards like you also might have you're just completely out of, out of sync
here relative to everything. In a right through cache you can have the same
problem here and just slightly different math so let's say you have a right through
cache CP1 does the store and it puts 200 here and 200 there . And CPU2 doesn't ever
see that value. Because there is nothing to tell CPU2 to update its value. So in
our coherence protocol, we have to think about how, how this works. So we have two
questions at the bottom of the slide here. Do these stale values matter? Well, if you
want to communicate to CPU1 to CPU2. At some point, something needs to have some
mechanism to actually move that data over into CPU 2's cache, otherwise it'll never
see the new val ue. So values really, really do matter. And,
and what is our view of shared programming. there are some, this brings
up an interesting question here. If you, if you want full sequential consistency,
this clearly is not your . It's just consistency. Now, one of the questions
that comes up is, what does the programmer expect? Do they expect full sequential
consistency? Or do they expect something weaker? Cuz you can think about having a
model like this. But then having special instructions, we will say, which somehow
have CPU's two invalidated data. Such that it will pick up, you know, a new, new
value. Or maybe special instruction to push a store out to the main memory. So
depending on your programming model You could think about having a very hard to
use programming model. Which would have data find where it needs to go. But then
you're effectively just doing messaging, instead of doing shared memory here. be
effect-, effectively sending a message from CPU one to CPU two, if you were
trying to push the data back and forth. So a little something to think about there,
is that. If the programmer assumes that when they write a value, the other
processors will see it. Caches, muck that all up. Okay. So let's, let's look at a,
a, walk through a example, in a little more detail. This is actually the example
we had from last class. The two programs. Or two, two threads. T one and T two here.
T one stores, one to x. T two stores eleven to y. Program two loads effectively
x and y, and then stores them right off into x private in wi-fi. Sorry it doesn't
in the flip board. Okay so let's look at a right back cache. . So we'll start off.
With memory here having initial value of zero and ten in x and y and we execute t
one and well, we'll say that writes one and eleven to x and y respectively but its
right back so this doesn't actually have to get out to make memory okay. Now let's
say the cache in coster one you know they've. And it needs some space for, the
cache line that y is in. But not x. the cache lines. And, the one just happens to
get invalid it needs the space for the next piece of code that's going to
execute. So what's going to happen here is, let's say y gets pushed out here from
the main memory. As we've shown in the, in the red there. But x is still zero. Ooh,
does anyone see problems coming up here? We just all of the sudden, had code, we
had something that was sort of in order, and you effectively have it out of order.
Data in main memory. Okay, now we go and execute thread two. Thread two is going to
read what is in main memory, pulling into its cache. And then write right back write
right back to its own cache. So we get eleven and zero from y and x. And then
we'll say, cache one writes back x. So the main memory now has one and eleven. And
then. Finally cache two writes back, X prime, Y prime, of zero and eleven. So a
couple of things to note here. X, the Xs any Ys in the X prime and Y prime don't
match , but more importantly this is one of our, sequentially, consistent,
inconsistent test cases. This is what Casy said, shouldn't happen. So we've just seen
something where we have write back caches, and we're trying to see if it can . bunch
of consistency. in its naive case. And the answer is no. It's not sequentially
consistent. This also, just to make a point here, can happen with write through
caches, . So let's, You need to sort of carefully sort of construct a case where
this happened. But the same case here. because it's write through. We first of
all, execute T1, , T1 here. So actually push up to main memory one and eleven.
What you notice is an interesting little thing here that we have X in our cache. So
lets just say there was some false sharing where there was some blow that happens,
that pulled it into cache too early. Well right through push from cache one to main
memory. But there was no guarantee. There was no (compares) for result to push it
down into validate or somehow notify. Cache two here. So this scale value is
still in cache one in our basic write through case. Now, we have thread two x
cubed. And it just copies its x to x prime. Its y to y prime. And it's right
through. So that shows up memory also here. Oz is, main memory is effectively
inconsistent now. And this is also one of our cases that, we had shown was not
sequentially consistent. So about something to guarantee that we have
consistency, we can very carefully have our hardware get out of consistency when
we introduce cache. Because there's different places to effectively store
stale data. It can be in main memory, it can be in someone else's cache, or it can
be in your own cache. So you can have the stale data in multiple places. I want to
make a point at, at this point of the lecture to. Differentiate a cache
coherence from a memory consistency model. There's a lot of words in this slide. But
the main difference is what I'm trying to get across is that. In a, a catch
coherency model. Or a cache coherence protocol. Is some algorithm to try to keep
data coherent. So that when you rewrite memory. Everyone's seeing something they
agree on. But it's the protocol that's trying to keep it coherent. In contrast, a
memory consistency model is the thing that our memory coherence is trying to enforce.
It is a abstract set of rules about how memory should act. So sequential
consistency is one example of that. Another example, as we talked about last
lecture, was cold store ordering, or process store ordering, or ordering . So
those are memory. consistency models. And then you actually have different cache
protocols which try to imp-, excuse me. Implement those prospective consistency
models. In last lecture, I said that I didn't think there were any processors
sequentially consistent semantics. And he, and he proved me wrong. Because there's no
absolutes in life. the MIPS R 10,00 architecture. the out of work processor.
And they . Sequential consistency. like, switching sequentially consistent memory
consistency model, I think also probably before 86, in some simpler processors
probably were sequentially consistent. Just'cause it was ki nd of easy for them
to do. But once you start to put it out of order, it gets, gets much harder. Which is
why the, the R10000 was actually interesting. Is'cause it was a super
scour, which had some limited to it. But they, they effectively the ability to
replay all their . . And so if they found something that was not supposed to
consistant, that effectively go back, and restart one of the programs much earlier
and replay all the code. It was interesting, interesting . About ,, .