In this course, you will learn to design the computer architecture of complex modern microprocessors. All the features of this course are available for free. It does not offer a certificate upon completion.
Implementation
Loading...
Del curso dictado por Princeton University
Computer Architecture
370 calificaciones
De la lección
Large Multiprocessors (Directory Protocols)
This lecture covers the motivation and implementation of directory protocol used for coherence on large multiproccesors.
Conoce a los instructores
David WentzlaffAssociate Professor
Electrical Engineering
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.
because the OS has absolute authority over where physical addresses 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.
[COUGH] 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, [COUGH] 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 because
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 uncached 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. [COUGH] 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 typically, 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. [COUGH] 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.
[COUGH] 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.
[COUGH] 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.
[COUGH] 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. [COUGH] 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.
[COUGH] 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. [COUGH] 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. because we have the most up to date copy,
because 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. [COUGH] 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 same as we would to the
normal invalidation message. Okay, so directory state transition looks
a little different here. We have uncached, shared, and exclusive.
[COUGH] 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 data. Well, we already have the data in the
exclusive state. So we're going to stay in this exclusive
state because 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.
[COUGH] 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.
because 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 [INAUDIBLE].
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
