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.
Scalability of Directory Coherence
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 Multiple Logical Communication Channels.
What we just talked about with all these different message types here, thus like,
the ten not drawn. Can't all go on the same network at the
same time. If you have one interconnection network
or one logical, excuse me, logical network here.
You can end up with cases where you have responses that get qued behind requests
that will create more traffic. So, in these protocols we have multiple
phases of, of communication. We send messages from point A to point B,
then from B to C, then from C back to B, and then B back to A, or something like
that. So, if you try to over lay this onto an
inner connection network, and you do head of line processing. So you process the
message which is at the head of the que first It's very common to have something
where you have a new response that sneaks in.
Which is dependent on some other transaction that's happening somewhere
else in the system. And you're waiting for excuse me a new
request comes in that gets qued behind a response.
Or excuse me, you have a new request that comes in that is in front of a response
and all of a sudden you're going to have a deadlock.
So, one way people go about solving this is you look at all the different types of
messages that you have, message types that you have, and you figure out which
types can coexist on the network at the same time.
so good example here is a I think if you look at a relatively basic cache
coherence protocol there's maybe twelve different message types.
You can try to shrink that down to maybe four, three or four different classes of
traffic. That those classes of traffic when
intermixed will never introduce a deadlock.
If you would be really safe you'd just have twelve separate networks or twelve
different networks, or twelve logical different networks.
But that's expensive to build, so people try to come up with equivalence classes
of different traffic and then only have that number of networks.
But you're going to have to segregate these flows in different, logical or
physical channels to make sure you don't have deadlock happening.
[COUGH] Another thing that I wanted to point out here is we just distributed our
memory. So we need to start worrying about the
memory ordering point or for given memory address, where do you go and what order
do memory operations happen in? So just like in a bus space protocol you
have some sort of arbitor which determines the transaction or who wins
the bus. In a directory based system, typically
the forth given address is the ultimate other.
So two messages are coming in from different course you go for right access
to a particular address. One of them is going to get to the
directory first and what if we gets the directory first, could win or estimately
will win. You could think of, sometimes this could
be unfair. So some of these systems you try to have
something which prevents the core, which is close to the directory, always winning
access to that contended line we'll say. So may have some sort of back off
protocol playing into effect there. But this is what effectively guarantees
our atomicity is the directory allows, guarantees that a particular line can
only be transitioning from one state to another state at a given time.
So we have the directory as the ordering point.
And whichever message gets there, gets to the home directory first let's say wins.
Subsequent request for that line are going to lose so what do you do on a
lose. Well you probably, the directory's
probably going to want to send a negative acknowledgement, or NACK.
It's going to say, or send a retry. It's the same thing here.
It's going to say, I can't handle this right now.
This line is currently being transitioned already.
Someone else won the transitioning of this line.
Go retry that transaction, the memory transaction again in the future.
Now, this gets pretty complicated back at the cache controller.
because it's going to get a retry, or a NACK back.
It could potentially have a message coming in for that exact same cache line.
It needs to give the directories message priority in this case over the pipeline
the main processor. So it's going to have to order that
after, it because the directory one the directory is the ultimate ordering point
for the memory location. Finally, you have to worry about forward
progress guarantees. What I mean by this is, it's pretty easy
to build a memory system that you pull the data into your cache.
Your cache control pull means your cache. But before you're able to do load or
storage at that actual address, it gets bumped out f your cache.
At all sign you have a cash line just sort of bouncing between two cashes and
its a live lock scenario. So you believes directory based coherence
systems and this also happens with bus space protocols plus usually it'll be
less likely. you have to have some sort of forward
progress guarantee. And the reason is less likely is because
in a directory based system the communication time is usually longer.
So the window of, of vulnerability is longer.
We afford progress guarantee means that once you get into your cache you need to
at least do one memory operation to it, to guarantee you have won bef, before you
relinquish the memory back to the directory control.
So, if you do, if you doing a load you're actually reading your cache shared to the
actual one load. And then you're allowed to cough it up,
so you don't respond back with a reply. To, let's say, an invalidation request
from the directory control until you've done your one memory transaction.
Or likewise, if you bring in a modify. Do that one store before you, you cough
the data back up or release the data back into the memory controller.
That's really important, to make sure you have some forward progress in the system,
and don't end up with a live lock. Okay so we're going to get into the, the
more futurey for future looking stuff here.
We've been talking about what's called, a full map directory, where there's a bit
processor core. If you have 1,000 cores in the system,
that's a very large bit map. And, it's pretty uncommon that a thousand
core in the system will all be reading all of the data, or all of one particular
cache line. So there might be wasteful and your
directory in a format directory grows at order N.
So that's, that's not particularly good. Hmm, so, people have looked into
different protocols here. I just want to touch on this, this is
largely the area sort of research and future directions of this.
One, one idea here is to have a limited pointer based directory.
So instead of having a bit mask of the share of list.
So its right this is the share of list. So its sort of a bit mask of the share of
list you have base two encoding numbers up to some, some point.
This is why its called limited directory or limited point of directory, because
you can't have all the nodes in the system on the list.
There is none of entries here. But you can name them because you have
base two encoding of the actual number. And if you get bigger this in this entire
list, so lets say you'll have one, two, three, four, five entries an over sense
six sharers, six mead owing copies of the list want to be taken.
Usually this is an overflow bit here which says its more than six and when its
more than six and it will share and also in a transition to modified.
You're going to just send a broadcast message or send a invalidate every single
of cache in the system. But usually this could be a good trade
off, because it's pretty uncommon to have extremely widely shared lines.
So it's an interesting trade-off. There are storage space, versus sending
more messages in the system. Like wise there's interesting protocol
here called limitless. Where same idea, it's a limited directory
and overflow bit, but if it overflows you start to keep the directory, or you start
to keep the sharer list in software in a structure in main memory.
And this requires you to basically have very fast traps such that when this
happens because your, your servicing cache line here you interrupt the main
processor and the main processor provides the rest of the sharer list for instance,
if the sharer list gets overflowed. So, there's, and there's a bunch of stuff
in between in some future, future research that's still being done actively
in this space. Beyond simple directory coherence, we
have some pretty cool on-chip coherence. This is why this is actually being
studied a lot right now, is people built this massively parallel directory based
machines in the past. They got some use, they were very good
for some applications. But now we are starting to put more and
more cores on to a given chip, so we start to see on-chip coherence.
And figuring out how to leverage, the fast on-chip communication alongst
directories to make more interesting coherence protocols.
There is something called COMA systems or Cache Only Memory Architectures, where
instead of having a data in main memory, you don't have main memory ever and the
directories move around. before beyond scope of the scores worry
about the KSR one if you want to go about that kind a score research one and then
also this real had a scale of the sharer list is active.
Briefly wanted to talk about the most up-to-date versions of these things.
We have the SGI UV 1000 which is a descendant of the Origin and the Origin
2000 machines from SGI, lots of cores here,
2560 cores that are all kept cache coherent.
They use a directory based coherence protocol here.
It's very non uniform, and it's all connected together by a multi-chassis
treaty tour. So, this is one chassis, there's actually
up to eight of these. Princeton has one of these in the HPCRC
centre, that I think is four chassis, which is sort of half the size of the
maximum. [COUGH] An on-chip example here is the
TILE64Pro had 64 cores. And each of the cores, itself is a
directory home and it runs a directory based protocol.
And I was talking about dividing communication traffic into different
flows. Well there were three different memory
networks here. So we had to do, come up with three
different classes of traffic, that themselves would not deadlock themselves,
if you will. And also there's four memory controllers,
which is connected into our interconnect system.
And because of this, the communication lane sees different.
A core here talking to the American controller is very fast, whereas a core
there takes longer. But maybe this core is close to that
memory controller. So non, non-uniformity here.
Okay, so this is our last slide of the term
here, Beyond ELE 475.
If you want to go on and do more. [COUGH] Well start reading some papers
from different computer architecture conferences.
The proceedings of International Symposium on Computer Architecture, ISCA
is a good place to start. That's probably the top, major
architecture conference in the field. The International Symposium on
Microarchitecture is the top Microarchitecture conference.
So if you're trying to look inside of a processor, and some of the smaller
microtechtectural details. ASPLOS, Architectural Support for
Programming Languages and Operating Systems has lot of different processor
between software and hardware's radio conference.
And HPCA looks at or used to look up at a higher performing high, big computers,
high performance computer systems. but now lot of normal computer operation
ends up in a compensawsive. I would have CD audio.
Well go to research. Built in chips, built some test
[INAUDIBLE] FPGA learn more about parallel computer architecture and, in
deed you can come back in the Fall. and take ELE 580A which is going to be a
graduate level primary sources paper reading course.
More traditional graduate course where you'll learn about all the different
parallel computing systems. So this is called parallel computation
because it's both parallel computer architecture and some programming models
that hook together without in parallel programming together with the
architectures cause they go, they go very hand in hand.
So let's stop here for today. And stop here for the course.
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.
