We move on to our final topic of ELE 475 which is, directory based cached
coherence. It's a little bit of a warm up here. We remember the three Cs of caches.
We had compulsory misses, capacity misses, and conflict misses. Well, we're going to
think about adding a new miss type here, a coherence miss. So our coherence miss is
some other cache, or some other entity, reaching down into our cache and
invalidating something there. So this is strictly different then compulsory,
capacity and conflict. If anything it looks most closest to a compulsory miss
because you're effectively. It's like a first miss, but someone, some other entity
bumped it out of your cache. But it's not any of those either. So this communication
that's coming from other cores that is been in a snooping protocol or symetric
shared memory multi-processor that other traffic comes in and it will actually bump
things out of your cache. You need to worry about this. Now we're going to,
we're going to take these coherency misses and put them into two categories. True
sharing, we, we talked about this briefly at the end of two lectures ago, or three
lectures ago. Well we're going to, we're going to categorize this as two different
categories of misses. True sharing misses, which we're going to say, is that if were
to have a cache where each block length or cache line size is exactly what's a one
byte to the minimal size you can have on your machine, you would still have that
miss. So that's a true miss. And a true miss is if you're actually sharing data.
So if one cache, let's say, writes some data, and another cache wants to go read,
or another processor wants to go read that data, and needs to go pull it into its
cache, that's a true sharing misses. You need to do that communication. Now, to
contrast that, we talk about false sharing, or false sharing misses. And what
a false sharing misses is, is saying that if you were to reduce the, sharing size or
the block size down to say, one byte or one word and you run the same program and
that miss occurs, or the miss occurs when the block size is let's say one, versus
or, or excuse me, if the miss occurs in the larger block size versus when the
block size is one, then that is actually a false sharing miss. The block size was too
big and you had two pieces of data in the same cache line that are effectively
causing a sharing, even though there was no true sharing going on of the data. It
just so happens they're packed into the same cache line. Now it's a little bit
more then that we're also going to say that false sharing can happen when data
gets moved around or gets invalidated but it's not being, it may be shared later in
the program, but that exact miss was not because of data being communicated. So
it's a little bit broader then what we said last time. It, it, it does still
happen because there is two piece data packed in to the same line but effectively
what I'm, what I'm trying to get out here is you could have data's that bounce
around between different caches and the same instruction sequence or the same load
in store sequence will not cause then this is if you had a very small cache line size
but does happen of a large cache line size. So lets, lets look at a example here
and try to categorize these different misses. So let's, let's start off here.
The initial conditions are X and X2, or X1 and X2, which are two piece, two words of
data, are packed into the same cache block or the same cache line. P1 and P2 have
both read the data, and it's, it's, it's readable in both caches at the beginning
of time. Okay so all of a sudden we do a right to X1. And we have to, what do we
have to do? Well, we're going to have to invalidate. X1 and P2. And this, this is a
true miss because the data was in both. We need to pull it out of the one. We need to
actually invalidate it. cuz this is actual, actual real data. Okay. So next
thing we do is P2 goes and executes a read of X2. Well, what you may notice here is
at the beginning of time X2 is in the cache of P2, but it got bumped out, here.
If P1 never want to go right X2 so this is a false sharing mess. This got an
exclusive into P1's cache and this is going to pull it out of that cache and
invalidate it. So recall, say false miss because X1 was irrelevant to P2 for this,
for this miss. Okay, so now we see, another right to X1. Well, P2 didn't
actually touch X, X1, so likewise, this is completely false sharing. Now we see a
right to X2 well we didn't see any communication going on here. So this is
also a false sharing miss. Now finally we have something that is real here. We're
going to read X two. When we wrote X two there, we read X two here, we are actually
communicating data. So this is true sharing. And that's okay. But we want to
try to minimize these, these false sharing patterns. This is just a warm up. Some mo,
motivate us into directory based coherence, a little bit. Okay. So let's,
let's motivate this a little bit more. And let's look at something like a online
transaction processing workload. So this is a database workload. So it's a
multiprocessor database workload. It's using threads. And what we're going to see
here is we have. We're going to run the same work load on a four processor system
with four different cache sizes. This, this data is, taken from a paper from your
book. And. What you'll notice is as you increase the cache size, our false sharing
and our true sharing don't really change. You still need to communicate data and
your still going to get false sharing. Just cuz you make the cache size bigger,
didn't change the block size. You're still going to get the same false sharing
patterns. But, as you increase the cache size. The instruction. Misses the capacity
misses the conflict misses the cold the, the, the compulsory misses we call that
cold go down because the cache is getting bigger, So non-shared cache lines
performing the, the, the. . Number of memory cycles. The amount of time you take
memory misses there, is going down. But the rest of this is not changing. Hm.
Well, okay. This is, this is interesting, so the second question comes up as, wh at
happens if we increase the number of cores in our system? So this is a relatively
small system here. Let's, let's plot the number of cores here from one to eight, at
the same workload. And look what happens. So if we, we look at this. Something else
is in variant here. This is for a fixed cache size. We're going to plot the number
of processors down here now. The. Number of memory cycles per instruction, for
instruction misses, complex capacity misses, com, compulsory misses, doesn't
change, just stays the same because it's basically uni-processor based. But, as you
add more cores you get both, more true sharing and more false sharing. Hmm, well
this is a little scary cuz our performance is basically going down as we add more
course. So this is only up to eight, what happens if we're, you know way out here at
100 course? What do we think's going to happen? Well, we're probably going to, to
be dominated, our performance is going to be dominated by the sharing and the false
sharing and these misses. Huh, well, we're going to start thinking about that one.
Figure out how to, how to solve that and think about scalability of coherence