Okay, so that's high level programming models. Or our, our second high level
programming model, which is not, shared memory, and the contrast with shared
memory, of messaging or message passing. And today we're gonna start talking a
little bit about the gory details on how to build interesting interconnects. Before
we get started, I wanted to introduce, sort of the agenda that we are going to
talk about. We are not going to cover all of this today. We're, this is, today's
lecture and next lecture we will be talking about interconnect design. So a
couple of different, things that you have to worry about in interconnect design.
First one is what's called switching. So when I say switching, what I'm trying to
say by that is, there's different ways to organize the communication. And you can
think about his probably the best example is the old telephone system versus the
modern day Internet. So in the old telephone system, there's switching, the
way it worked is, you try to make a phone call and the first you did is you picked
up the, the receiver on the phone, and you sort of turn the crank, and there is some
switch board operator in your local town who would hear the bell ring, and take the
plug, plug the wire in and pick up and say hello, where, who you trying to call. And
you would say I'm trying to call such and such in next town over. Well the
switchboard operator would say, okay that's good, I'm going to take a wire
from, the wire that runs from your house to this location, plug one wire in there
and then we'll go and plug the other wire into a wire which runs to the next town
over. So then you'd be connected to the next town over, and the switchboard
operator in the next town over, and you'd say, oh I'd like to talk to the same
person you're trying to talk to. And they would say, okay that's great. I'm going to
patch a wire from, my patch board from, the out of town wire, to the destination
location, and I'll turn a little crank to ring the, the ringer on the, on the
destination phone. Okay, so that's one ide a.
And that is actually called circuit switch networks, cuz you're building a circuit.
You're building a wire all the way from one location, all the way to another
location. Alternatively we can do what we do in the network internet today. In the
internet today there is, we don't generate, we don't have a wire directly
from one location patched together the, you'd actually patch wires from one place
to another place. in contrast, in our switching systems you'll actually
packetize the data. And then we'll hand the packets from different locations, and
people and resources can be used for other things. So, it's much more akin to
something like a mail system. So, in a mail system, you take the data you want to
send. You fold it in half, you put it in an envelope. You put a stamp on it, and
you, you set it going. The road that goes from your house to the post office is not
reserved, for that one piece of mail, until it gets all the way to the
destination, like in a circuit switched, to apology. Instead in a packet switched,
you are going to some of the message, and you are to put a stamp on the physical
envelope, and the, your postal carriers may come pick it up. They are going to
take that, take it to some place else, and then there is taken to some place else,
take to some place else, but you can set another piece of mail on that same link,
or other people can be using the same roads to send another packets, or other
messages. So switching is the type of network we have here, and how we connect
together the different networks and how we do the switching. And there's a couple
other things in the middle between circuit switched and packet switched networks.
Okay, so next thing we are talking about interconnect design is topology. So this,
how do we physically connect things together, in our world. How do we run
wires between the different nodes in the system? Do we run wire between every
person in the classroom, I run a wire between myself and every other person, and
everyone runs with a wire between everyone else. Or do we build a nod in the middle
of everything to, or do we really connect to our nearest neighbours, and then, we
have to send it to them in native sens of X people. So there's a lot of different
apologies for given size graph. . Routing, routing is figuring out what path to take
through the network to get from one point to another. So, we can actually build a
nearest neighbor network in this classroom, or we run wires between all of
our neighbours, but not lets say, we all, each, each of us connects to three
different people, but not to four, and there's gonna be multiple paths from any
one point to another point. So we need to come up with a routing decision to figure
out how to get from that one point to another point, and that affects our
interconnect design. And then finally flow control, and there's two types of flow
control. There is local flow control, which is communication from one node, to
the next the next node over, and making sure that you don't lose data on that
local link. But its also, how do you rate limit, round trip throughout the entire
network. and we are going to study that next time in more depth. Okay. So let's
move on to some fun pictures here. High quality pictures. So first thing we're
going to look at here is the anatomy of a message. . A message is our fundamental
primitive of some piece of data we want to send. At the top here, we show a message
which has, let's say, some number of bytes in it. These delimiting points here do not
delimit a byte, they delimit some chunk of data. And we're actually going to fragment
this message into smaller pieces which we're going to call a packet. Now I know
that I want to make a big difference between a message and a packet. A packet
is a piece of data that we're going to be sending through the network, and the
network natively understands this packet and the packet is routable through the
network, so it has routing information. So, a good example of this is, if you are
trying to use MPI, and you want to send 1000 words, and let's say the maxi mum
message you can and, receive, or maximum package you can send on a network is 100
bytes. You're going to packetize the data, packetize the message into 100
individually roundable packets. So let's look inside of one of these packets.
Typically, because the packet is roundable, it needs to know where its
going. It might need to know where its coming from. So at the beginning of a
packet, you will typically have something like a source. You might have a
destination, or its going to be you definitely need to have a destination, you
might have a source. You might have a length. If your, network allows for
variable length packets. , and we call this the header. And we call the rest of
the packet the payload. And we're going to introduce an interesting term here. Flit
Now this is a term actually that was coined by, I believe Bill Dally, who is
now a Stanford professor who, he did a lot of work in message passing and other types
of parallel computers. A flit is a flow control digit. It's kind of like a bit,
but it's the, the, flow control ball unit and. The reason we bring this up,
sometimes a flit is actually equal to the whole packet. Sometimes it's a smaller
piece of the packet, depending on how you build your network. . But a flow control
digit is what you were flow controlling on from one node to the next node. So this is
what you track the flow control on. So, it's very possible that your, you don't
actually track, sort of send and receiving of messages on the byte level, or on every
single cycle, but instead you do it in bigger chunks. So a good example of this
is, you have a network, which is one byte wide, the link is one byte wide, but you
are, so, the minimum thing you can send is a 32 bit word. As the minimum piece of
data that is full control, then you need to always send let's say, four bytes. The
full control will be on the order of the flit, which is the four byte unit. But the
link is narrower than that. So you don't actually, you can't actually stop in the
middle of the message, and say. Oh, I on ly got or you can't stop in the middle of
a flit and say stop. you gave me three bytes, and I can't take the fourth right
now. No. It's not allowed. It's, it's flow control based. So the flow control says
this is the minimal unit for flow control. So there's four bytes, that is what you
are allowed to send. And you need to send in chunks of basically four bytes. And
that's our flit size. No we can split inside a flit, and we can actually call
this one a phit, or a physical transfer digit. And a phit is what I was talking
about with, you had, if you had for instance, four bytes that you're trying to
transmit, and your flow control on those four bytes. Each of those bytes is a phit,
or the physical transfer that you transfer in one cy-, in one clock. cycle. . Many
times the phit and the flit will be the same, if you have what, if you have wide
networks, but if you have very narrow networks, sometimes these will not be
matched. Okay, it's just a nomenclature so far. Our first topic we want to discuss is
switching, how to get from point A to point B. Oh, okay. It's not routing, it's,
it's rather the model of how to connect different locations together, and we're
going to talk mostly about three here. We already talked about circuit switched.
Circuit switched is like the old telephone network. You pick up the phone and somehow
there's a wire patched all the way from where you pick up the phone to the
destination location, and you reserve that location the whole time. Packet switched
networks, or what is sometimes called store and forward networks or probably
more commonly called store and forward networks, are things like the Internet,
where you'll actually generate a packet, hand that to someone else, and they'll
store it. And at some point, when the link is free, they'll forward it onto the next
hop. And when the next link is free, they'll store it on to the next hop, and
it'll continue until it gets to the destination. Thus in contrast to cut
through networks, which are sometimes called wormhole networks. Cut thr ough
networks still have packetization. But they'll actually. Worm, through the
network. So instead of having to, send the data from one location. To the next hop
over. An it waits for the entire message to receive. Before it sends it on to the
next node. A wormhole network. Will actually allow. Or a, a cut-through
network. Will actually, start to send the beginning portion of a message. From, one
node to the next node. Along the hops. Before the tail has been received. Hence
it's actually worms through the networks. You can actually have a message sort of
streamed through a multiple different nodes. And this is where we have as cut-3
networks. So I just wanna introduce those, those three ideas and think about them as
we go onto to build networks. we'll talk about cut-3 networks, when we get to,
rounding. So before we break for today I want to just introduce a couple different
topology. And just come up with different topologies where we'll pick up next time.
But in our networks, we talked about buses. Multiple entities on one shared
medium. You can think about building a segmented bus, where you actually have
flip flops along the communication path here. And this would allow, for instance,
this node, maybe, to communicate with that node at the same time as three
communicating with four. sometimes this is called pipeline bus. You can have rings.
Which are like the segmented bus, but they connect the two ends together. You could
even, implement rings in a way, that minimizes wire length. We'll talk about
that next time. You could have crazier things like 2D meshes, 2D toreses. If you
have cubes and hyper cubes. You can have fully connected topologies. You can have,
things called omega networks, which are multi stage networks. Where you can
basically communicate from anyplace to any other little place in multiple stages, in
multiple clock cycles. You can build, trees. or, things called fat trees, where
the lengths at the top of the tree get fatter or wider. And we'll talk about this
next time, but the generalized case of this meshes, you end up with things that
are called k-ary n-cubes where you can very concisely with two numbers, describe
a network topology. Okay, let's stop here for today.