Okay, so, now that we've gone through the beginning excersises of what a directory
based distributed shared memory machine looks like. Let's talk about how to
actually figure out where the directory is. So you have an address. And usually
these systems you don't want to do it on the physical address spaces. You're not
going to want to do this on virtual addresses. You don't want to have to run
this, This is because you're sharing data between lots of different systems. At this
point you're sort of, out of the system bus. Your address is no longer virtual.
You've gone, you've gone through the translation look inside buffer or then MMU
and you've figured out what the physical address is. So, to figure out what the
directory is, or sometimes called the, the if in a distributed memory machine the
home node. Or is the it's a number of which one of these directories to go to.
And there's a lot of different ways to do this. But one of the more common ones, is
to just use some bits out of the address. So you take the number of directories in
the system. Take the log base two of that. And then, you take that number of bits to
be the home node number. So when you take a cache miss, and it's not in your cache.
And you need to go figure out and do the load of that data, we'll say. You send a
message and the message ID and the destination of that message will actually
be the home node. And hopefully, your interconnect knows how to route the data
to that directory. Now, taking the high outer bits has some benefits. Lets, lets
take a look at that. As we discussed already in a, in a non-linear form memory
access architecture, the OS can control the placement. I can do this because based
on these high order bits, you can actually determine where, which node in the system
or which directory in the system you're going to. So you can actually basically
allocate memory, allocate your stack, allocate your instruction space, based on
the physical address and the OS commands that. Cuz the OS has absolute authority
over where physical a ddresses get doled out to. Downside is a directory or a home
node can become a hot spot. So let's say all of a sudden, all of the processors in
your system try to access one page of memory. There's like a, a hot page which
has all the locks in the system. And, you're in some threaded program and you
have to access those locks a lot. Well, if you look at that, that's all going to be
down here. It's going to be sort of low order addresses. It might be from sort of
here down, whatever your page size is will say. So even, even if you're not having
false sharing, anything like that. You typically would try to pack all the data
onto a page or a structure or something like that, and it's pretty hard to
interleave it based on the very high order bits of your, of your address. And
especially considering a program has effectively no control of the high order
bits of a physical address, that's managed by the OS. So if you do this, one node can
become a hot spot, because these are all alias to the same directory. So all, all
the messaging traffic goes to one node and this almost starts to turn back into a
bus. Now, we have one directory, all traffic has to go there. It's a little
better cause we don't necessarily need to invalid all other locations, but the
directory and the bandwidth in the directory starts to become critical. Hm,
well that's a tough one. The flip side is you can start to try to have the low order
bits determine where your directory is, or which home node you're using. So, you
still have the, the offset within a cache line. But then you have the number the,
the bits of the physical address that can determine what home node your going to be
the low order bits. Well, this ends up being very well load balanced, because
you'd choose different home nodes effectively atrandom depending on which
cache line it is. So you know two cache lines will same cache line will go to the
same home node or the same directory. But if you have certain different cache lines
in which it is pretty common because it is pretty hard to content all unwanted cache
lines. This is up much data in one cache line. You'll spread across the different
controllers and you'll effectively have some good distribution. Flip though is the
OS losses placement ability here. So it's, it's tricky, it's a tricky trade-off here
to think about. some people have even built systems where it's configurable.
this gets a little more advanced. And I touched on this in the last slide of, of
today's lecture. But, you could think about having some systems where, depending
on the actual address and depending what comes out of your, page table. Maybe
making different, choices of how to do the mapping. But everyone has to agree on the
mapping. Which gets a little bit tricky cuz the directory has to agree on the
mapping. And all of the caches in the system have to, agree on the mapping.
Okay, so let's take a look at what is inside of a directory. So we added this
new hardware structure, and whenever we add a new hardware structure I like to
look at all the bits inside of the hardware structure. So we add a new arbor
structure, and this arbor structure has an entry per cache line in, in that
particular memory connected to the directory. So if you were to look across
the entire system, there will actually be an extra piece of data for every single
cache line in the system. And the naive approach to this will habit such that
every single cache line in the system, whether it's. Sorry, not every single
cache line, every single memory line in the system. So if you've ten terabytes of
memory in the system, the naive approach is going to have a directory entry for
every single block size chunk of memory, a cache box size chunk of memory in the
system. And these are held in big tables, typically they're held in SRAM. You might
try to put them in DRAM. And what do we have here well the directory needs to know
what state the cache line is in and we're going to look at three different states in
our basic protocol here shared, uncached, and exclusive. So everything starts out as
uncache d it's out in main memory. When it gets pulled into a cache's read only, the
directory is going to okay that is now shared. If it gets pulled into a cache
read/write, the directory is going to note that as exclusive. Now, if it's in shared
or exclusive, we need to know what node, well if it's exclusively, you know,
uniquely what node has that? So we can go message it when we need, need to go
invalidate it. And if it's shared, we need to know the list of all possible places
that it could be, that we're going to have to send messages to. And this is better
then having to broadcast or send messages to all the nodes in the system. So we're
going to have what's called a sharer list here. Which is a, in a naive full map
directory is going to have one bit per core in the system, or per cache in the
system. And it's either just going to have one or a zero in it. So if it's a one that
means that core has a share or read only copy of the data. And when some other
cache goes to get it in writable in its cache it's going to have to invalidate,
let's say this one or zero with core's cache. Now if you're exclusive, your not
going to have multiple bit set here. Cause this basically means that, that core has a
writable copy and we can't have if we want to keep the data coherent we won't want
multiple, we don't want multiple copy writings in the system. So as you can see
here, denoted only one, one here. And if it's uncached, we don't need to track
anything there, we just got, don't cares. There's one other state here that I, I
have and it's pending. And this usually actually turns into a couple sub-states
there's different ways to track this. At the directory, these transactions take
multiple steps. You're going to send some data and start transitioning. Let's say,
you want to get a data, data writable. Well it, that, the directory's going to
have to invalidate all the other copies. It can't do this instantaneously, but we
want to provide the appearance of a atomicity or, or, or that the operations
are atomic in some way. So t ypically, you'll actually have some sub-states that
are shared, that are stored here, which are something like, oh this cash line is
currently transitioning from, I don't know, U to E. Don't allow some other
transaction to happen to it right now. Just kind of block that. Another way to do
that, the one way is to store it actually in the directory, as a state bit. Another
way is you have some fully associative structure, a side structure, which just
has all of the cache lines currently in flux. And, the directory's smart enough to
know that if some other request comes in for that line, while it's in flux just to
NACK that request, or negative acknowledge that request and tell the other cache to
retry. So you can do it either way. but it gets pretty complicated. We're not going
to talk about all the details of that but we'll talk about the high level
transitions assuming that they are somehow topic. So here we're going to look at how
MSI. It fits together with this. But you could actually think about doing this with
Mesi or some other protocol. It's a little bit simpler, emphasize a little bit
simpler so we're going to look at that. Also the benefit of something like a Mesi
protocol is lessened in a directory because if you pull something in, in the
exclusive state, which is unmodified at the beginning. And someone else wants to
get a read only copy. You're basically going to have to send a message to that
core. And that was inexpensive on a bus, because it could just see the transaction
going across. And it would just snoop it and would demote from E to shared or
something like that, E to S. But now, it actually turns into actual work. The
directory's going to have to generate messages. And you're going to have to wait
for responses coming back from a cache which had it in exclusive, so. full mezies
a little bit less common when you stretch grow these distributed shared memory
protocols. Okay, so this is a slide we had before. This is MSI on a bus. Well things
change a little bit when we go to MSI for directory coherence. And before we go
through this, I wanted to point out, that there is actually two different state
machines going on here. There's one state machine that is happening in the cache
controllers, so actually, in the cache of a respective processor. And then there's a
different state machine which is happening in the directory. And you'll see that they
have different letters here. This is SU and E versus MS and I. And, and we label
these differently on purpose just to, not, not get totally confused. And these state
machines interact by sending messages between each other, and as messages flow
between the directory and the cache. There will be both going through different state
transitions on this, on this two tables. Okay, so let's, let's jump into this. This
is the same modified, shared and invalid states that we have in our bus space
snoopy and aside protocol. We didn't change anything here. And the rules, the
rules the same. If you haven't modified, you can do a right to this and not to send
any messages. If you have a shared, you can read the data and not have to contact
anybody. If you have an invalid, and you want to do anything with it, you probably
need to contact somebody. Or you probably need to contact the directory. Before, we
would have to send the transaction on the bus. Likewise, the transition from S to M
or M to S where you, used to communicate it was the same. So think about this as
the same state machine running, except running on a bus where before we would
send transactions across the bus. Now we're going to take those transactions and
turn them into messages that we send to the directory and messages that we receive
from the directory that we have to respond to. So before when we were snooping
traffic crossed the bus which caused us to transition different locations. So here
other processor has intent to write and we saw that across the bus. So we had to
transition ourselves to the invalid state. Now, we're actually going to get a message
from the directory controller. So let's, let's walk through this. But it's, it's
almost exactly the same as what we saw before. So this is the, the cache date for
a particular line for processor P1. we'll start with the entry points. We start off
an invalid and let's say we want to get a read, a readable copy of this line. So
we're going to take a read miss. So what we're going to do is plus serve one is
actually going to send a read miss message through the directory controller. And
during that time, it does not have a readable copy. It cannot go and access the
data. It's, it's a, it's effectively still in the I state. Sometimes people will
actually have sort of a pending state here depending on how you go to implement this
depends if you have a side structure sort or something like a mishandling registrar
where you'll track that in. Or you can track that in the, the cache data itself.
So you're going to read miss. You send the read miss message, and you're waiting for
a response. This response is going to have the data that you need. And, it's going to
be synchronization points saying, okay you're safe to transition to S. Okay that
seems pretty simple. Similar sort of thing here for write miss if we're in the in
invalid state and we do a write we're going to send a write miss request to the
directory controller. It's going to do something and it may we may have to be
waiting for awhile here cause it may have to go invalidate all of the other lines in
the system. And then it gets a response and once it gets a response we have a data
that we can transition to the modified state. So as we said, these arcs are
pretty easy you can read by P1 and nothing changes or we can read or write from the M
state by P1 and we also communicate with anybody. But now we have a few different
messages coming in here. If we're in the shared state, we have to be responsive to
an invalidation message. Which is a little bit different than a bus snoop. So before,
we saw another processor trying to write. That's when transition goes to I, but now
the directory controller sends us a message which says, invalidate this line
and that will transition us to I here. Note, there will probably be a reply. We
will probably have to send a reply, because the director controller wants to
know. When all of the cache lines in the system have been validated and it may take
a variable amount of time and its sending messages so it wants to wait for a reply
to come back so we're going to have to send a reply. So this arc here is similar.
Except, we need to write back data, cause we had modified data. We had writable
data. We get an invalidate message from the directory controller. So we need to
write back the data, and then reply afterwards. Similar, similar sort of idea
here. Okay, so that leaves two arcs left here in the middle. We're in shared, and
we want to do a right to a, to that cache line. So, our cache we have in the shared
state. We want to do a write to it. Before we can actually do a write we have to send
a message to the directory saying, I'm doing a write miss here. I want to get
this data writable. And we have to wait for a reply before we transition here.
because we have to wait for the directory contror to communicate with all the other
cache's so that they don't have redoing copies and we can have a writable copy. So
it's going to invalidate all the other readable copies in the meantime. And then
finally, we have an edge coming this way which is from modified down to shared. And
this is a little bit different. well, it's the same idea here. Another processor is
tying to do a read. So we have in a modified state when another processor
tries to do a read. So we receive a read miss message. We don't need to invalidate
the data, but we need to write back the data. Cuz we have the most up to date
copy, cuz we had it modified. So we're going to go into write back the data and
that's going to be response, and then we're going to transition to share and
state. We can keep a read copy of this, because the other, the other core is, is,
is only having a, a readable copy of it also. Okay, so that's the. Any questions
about that so far? Okay, so two interesting arcs that we're going to add
in here is this one and this one. Which we didn't have in our base MSI protocol. And
you know, you may not need these. But what these correspond to is, if our cache has
the data in it and then because of let's say a conflict miss, or capacity miss it
gets bumped out. It might be a good idea to go update the directory, and tell the
directory that in the future if some other cache wants to go get that data, that it
doesn't need to go contact you again. So, if it's in the modified state we can write
back the data because we have dirty data we write back that the directory and then
we notify the directory saying we don't have a copy of this anymore you can
transition to having it uncached. Likewise here, if we have a read-only copy we may
or may not want to do this. If we, if there's, you know, extra bandwidth on the,
on the interconnect we might want to send a message when we do an invalidation here.
And this is not an invalidation because of an invalidation message, but this is an
invalidation, because it just gets bumped out of the cache. We may want to notify
the directory saying please remove us from the sharer list. And if the sharer list is
already empty, the, the directory might change the cache line from shared to being
uncached completely. but I do want to point out that these are not strictly
necessary. The reason they're not strictly necessary is, if we build the cache
controller system such that if you're in the invalid state for a particular cached
line, and you get some message coming in that would have been let's say this
message, or that message, or some other arc. We can just reply back saying yeah,
we don't have it anymore. We're invalid, you know, we don't really care about that,
that transition. So if you were, you were here, the only message that's going to
come really to you is an invalidation message that would just take you to this
state anyway. So, we can just ignore the message or just reply the s ame as we
would to the normal invalidation message. Okay, so directory state transition looks
a little different here. We have uncached, shared, and exclusive. As we said, shared
means there can be multiple read-only copies in the system. Exclusive means
there's only one cache in the system with that data. What's interesting here is if
you were to actually have a MESI protocol running, that would not change the
protocol running in the directory. Because exclusive here is effectively the same,
same state, with respect to how the directory sees the line you won't have to
do anything different. Okay, so let's walk through a few transition here of the state
of the cache line in the directory and this is not in the cache. Let's start off
uncashed and let's say we're getting a message which is a read miss from
processor P. Well, we should transition to S now. We should give it a readable copy
and we should reply with the actual data and we should put P on the sharer list, so
that we know that if someone else needs to go invalidate that line we need to go
contact P. Now that we're in the shared state, let's say there's other read misses
from other P's other processors here. Well were going to give it up the data and
we're going to add it to the sharer list so we're take sharers and add to it. The
processor the sharer list is just going to grow. Okay lets, lets start here and go
the other way where an un uncached in all the sun in we get a rightness from proster
P. Well we give it the data and the sharer list or the owner is going to get P
uniquely on to it, ever going to give it in these causes day because we're on cache
reform. We don't want to contact anybody else. let's look at this art here before
we go to these. So this is a little bit different. Quite a bit different than what
we had in these slides, because it's doing something different. But in this state
here, we know, let's say, processor P zero has the data exclusively. But all of a
sudden, a different processor, let's say processor two goes to access the da ta.
Well, we already have the data in the exclusive state. So we're going to stay in
this exclusive state cuz some other caches going to want to get it exclusive, but
it's different cache. So what has to happen here is we need to go invalidate
the data out of P zero. P zero is going to write back the data, it's going to
transition to the invalid state. The, we need to then provide the data to the new
processor P2 we'll say and add that P2 to the sharer list. So we can, we can
transition to this state and then finally let's look at the edges between these two
points oh, actually let's go this way first. if you've data that gets ridden
back. so this is that arc, which I said is similar to the arc here, which is
optional. Let's say you have data that gets right, ridden back here. Actually
this, this arc may not be optional, let's think about that for a second. This arc
may not be optional. no it's still optional. cuz you can just NACK the
message effectively, and, and tell it it's in main memory. okay, so let's hear, and
you see a data write back happening. So, message gets sent to you which is the
equivalent of this arg here. The data was writeable, was exclusive to some cache,
and it's no longer writeable. It's probably a good idea to go contact the
directory, write back the data, and clear the sharer list. The sharer list is empty,
so it knows that no one has a copy of it, at that point. Okay few other financials
here, okay we are in the shared state. So we have multiple read-only copies. And one
cache comes along and says,"Oh, I need to do a writeness message." I need to get a
writtable. Well, now we actually have to go through a pretty long process. We're
going to walk through the entire sharer list and send messages to all the sharers
in the sharer list saying, invalidate this copy and tell me when you're done. We're
going to collect all the responses at the directory. And once all the responses have
come back, we know no one else has readable copy. We can give the data value
to the requester. And add it to the sharer or owner list. Okay, last arc here is from
E to S. This orange arc and that happens if we have a particular line as writable
in one cash, and another cash wants to go read it now. Will send a read miss the
other cache is going to downgrade from E to S, excuse me from M to S in its vocal
cache. But the directory is going to transition from E to S here and we have to
go get the most up to date from the node. So, we're going to send a fetches and a
fetch request to the node that had it before and exclusive, once you get the up
to most up to date data you can forward that to the new reader and everyone and,
and we add their processor to the sharer list. Okay, so questions about that one so
far? These, these do start to get a little complicated because you have multiple
state machines interacting. Okay, so were going to speed up a little bit here. I
include this chart from your book just to give you an example of. We went through,
very quickly here, all the different messages. And, this chart here sums up all
the different message types. And from who they could go from and who they could go
to. And this is, this is in your textbook. and sometimes messages need to communicate
addresses. Sometimes they need to communicate data. Sometimes they need to
communicate which node the message is coming from. To add it to the, the sharer
list. But I'm not going to go through this into, to great detail. One think I did
want to say is, these message types here, do not include . So, when you go to
request something, there's replies that come back. These replies after, that's not
drawn in this diagram. We, we see data value reply but that's not, that's just
what of, actual data. There's not like a, response coming back from the sharer
acking the, the sharer, or acking the invalidator or something like that.
Another type of message that is pretty common, that is not drawn here is a
negative acknowledgement. So it's pretty common if you have a cache line that is
being transitioned, it's in a pending state, at the directory , and get a
request coming in. You might need to tell that cach retry later. I can't handle this
case later right now.