So we started last time, this is where we left off was talking about topologies.
Now we went through this really fast, but I wanted to go into a little more detail
here. So far, we've, in this class, we've been
talking about buses. And actually buses are a type of
interconnection network. So a multi-drop bus, where everyone just
sort of screams, is a broadcast network. And it is, it is a type of
interconnection network. But it may not have the best properties.
It may not have the best bandwidth, and it might impact your clock frequency,
so it might even impact your latency, depending on how you go about
implementing one of these things. So sort of the next step away from
something like a, a bus is actually something like a pipeline bus,
where you start to put registers in along the way.
And now you can have nearest neighbor communication.
Let's say one is talking to two, and three is talking to four at the same
time. But you couldn't do that when everyone
was shouting to each other, as only one, one, entities allowed to talk on this
network at a time. We'll say.
So we start thinking about that. And we can actually make some more
advanced versions of these. We can start to think about things like
toruses, where we'll take the end here and connect it around.
And this is a one-dimensional torus, or many times is known as a ring.
one thing I wanted to point out about this is if you look at the naive ring
implementation, and if you think of these are, as wires, you would say, 'Well, this
is interesting. If I have a thousand nodes in my ring.'
All of let's think about that. One, two, three, four.
Yep, okay. If you have 1000 nodes per ring.
999 of'em are going to have very short links, and then one of the links is
going to be super, super long, it's going to go from this end all the way to
that end like this is drawn. Hm.
Well that's, that's not super great. communally, people have actually thought
of fancy ways to fold tauruses into the, let's say if this is a 1-D torus into a
1-D space, and minimize the wire lay, lengths.
So actually I drew a picture here to show this.
If you remember and stagger the you connec-, the nodes here.
This is the exact same 1-D torus as we drew here.
Except now all the lengths are equally equidistant or equal length.
Except they're twice the length as they were before.
So, you can actually fold a torus into the same oh, oh, for instance, an
n-dimensional torus into n-dimensional space, by doubling each the lengths, by
doing this cool inner leaving trick. And this also applies for 2D, 3D, 4D
Tauruses. Etc.
You can, you can come up with some ordering and numbering which will
actually, interleave like that. Now having said that, it may be
challenging to build a four dimensional Taurus in three space.
And fortunately, I live in three dimensional space, and I'm hoping you
guys do too. and if you, if you're like me, and you
live in three dimensional space. It can be hard to go build five
dimensional things in three dimensional space.
We'll talk about that in a minute. But I just want to show this cool trick
that you can actually. Full day.
1-dimensional Taurus into 1-dimensional space and not have a super long link.
Okay so now we can start to think about. Actually before, before we go on to that
lets, lets think about the, the limits of this.
If we start to go to a 1,000. Long torus.
Or a thousand 1d ringed or 1d torus. Unfortunately this does not, the amount
of sort of bandwidth that you cut through here, let's say these two links here does
not go up as we add nodes. And a good property of a network or inter
connection network, is that as you add more people communicating on the network,
or more entities communicating on the network, you probably want to be able to
add more bandwidth. And you can say, well I can make the, the
links wider, but that only helps so much.
I can make the link faster, but it only helps so much.
So this makes us think about having different topologies.
So we can start to go to higher dimensioned topologies.
So we can start to use 2D topologies, or 3D.
and you can see here, here as we have lets say 16 nodes arranged in a
2-dimensional mesh, versus, here we have a 2D torus.
And the difference between the 2D mesh and the 2D torus is that there's what's
called end around in our, in the torus. And that makes the routing from here to
there much, much faster, and effectively, we'll cut the, average
routing time, or average routing, excuse me,
average, hop count by a half. Because you can go either way now, and go
around the ends. Sometimes, these 2D toruses are called, a
2D mesh with end around. That means it's a torus.
just, I just wanted to throw that nomenclature out there, because sometimes
you'll see, you'll see both. A good example of a simple routing
protocol is if you're at this node here. And you want to communicate some data you
can send the data in all directions. And then everyone else sends it in all
directions. And everyone else sends it in all
directions. And it'll just flood the network, and
it'll get everywhere. And you're guaranteed that it's going to
at least get to the receiver, and you have some guarantee that when it
gets to the receiver, the receiver sees the, the packet and takes it off.
Now that may not be what you want to do. [LAUGH].
That's, that's probably not low power, and it's probably going to cost a lot of
congestion on your network, but you may want to think about a
flooding protocol. Okay, so wherever there is 2D we can
start to go to 3D. So here we have a 3-dimensional cube.
Sort of. It's the best I could draw.
It's, it's hard to draw 3-dimensional things on 2-dimensional space.
And if, if we had 3D space I could have drawn this much cooler.
so this is a hypercube. Hope these are actually hypercubes.
So, all the hypercube is, is it's saying that the number of the mentions you have
[COUGH]. is equal to the number, or the degree or
the outbound links of a, of a, of a node in the, in here.
So, if you look at this node, we have a three dimensional hypercube.
So it can go this direction, that direction, or that direction.
Every node has a out degree of three, or a connectivity of three.
Here, we have a four dimens, a four dimensional cube, but this is, by
definition, a hyper cube. So, because, if you look at any given
point here. So, we're going to define a hyper cube as
the out degree, of the nodes is equal to the dimension of, of the, the links.
And, you can't go build here a, if you were to add one more node to the system,
[COUGH] or some other. Let's say you were to scale this out in
some direction, you would actually be increasing, the
degree of a node by adding more, more nodes.
But not to everybody, equally, so not be a, a hypercube.
So if you were to build on a, something like this network here, this is, this is
not strictly a hypercube because the degree of I'll say this note here is not
equal to the degree of, well actually you could just stick with that.
The degree is equal to the degree of the other places, but we've effectively
increased the diameter of one of the dimensions such that there's not the
routing distance is longer now for this number of nodes.
If you were to go to a higher dimensional design, you could actually reduce the,
the latency for each one of these nodes in something that's got three
dimensional, three area three q, which we'll talk about in a minute.
But here we have a four dimensional cube, and what's nice about this is the number
of hops to get from here to anywhere else is quite low.
So let's, let's, let's think where the farthest point in, in this.
Cube is going to be. So it's going to be, let's think, is it
here? Or is it here?
One, two, three. No, it's the other one.
Okay, so it's going to be one, two, three, four to get to there.
Is going to be the farthest number of hops.
So we can think about having these higher dimensional systems.
Now, as may be readily apparent but I'll say it anyway, if you try to build a five
dimensional hyper cube in three dimensional space some of the wires are
going to get long. Because you can't fold five dimensional
space into three dimensional space. You might be able to span a 4-dimensional
space into a 3-dimensional space with not, not too bad.
But there's kind of this good rule of thumb when you're building networks that
you probably don't want to be building a N,
you probably want to a map let's say an N-dimensional network into N-dimensional
space. Trying to map higher is painful,
trying to map much, much higher is very painful.
The benefits though is that, you have to have fewer routing, hops to get to be
able to get wherever you're going, in the higher dimension cube.
Now, I want to just throw this one up here because this is an interesting
topology. Just connect everything to everything.
This seems great, we should all build these networks, [COUGH], unfortunately
let's think about trying to put this network in three space if we have 1000
nodes. Well, what that means is, if you have
1000 nodes. You're going to, each node is need,
you're going to need to have 999 outbound connections.
And 999 inbound connections. So when you go to build this, you might
be able to build this, sort of, in a, outside of a sphere.
Or, sort of, a big wiring mess on the inside.
that's pretty hard to do at, for, for large numbers of nodes.
For smalls numbers of nodes, something like a fully connected crossbar, or
what's also known as a star topology, will probably work fine.
But And in fact if you cut it sort of across
the middle of the network here, which we'll talk about in a second.
It has very good bandwidth. Okay, a few other things you guys should
know about from a terminology perspective.
[COUGH]. The networks that I've drawn to this
point. On what are called direct networks.
Which means that the nodes have some type of router built into 'em.
You could also, and people, plenty of people build this, is they build networks
where the nodes do not have routers built into them, but there's a multistage
network or some sort of network in between the nodes.
So a good example of this actually is something like your Internet if you will.
There you have computer nodes, and computers are not doing the routing
themselves. Instead they send it out to a what we'll
call an Ethernet switch, and the Ethernet switch is lets say one of these boxes
here in the middle. And that makes a decision and sends it on
further. It could be a, a internet router, could
be in the middle here also. And the analog in computer architecture,
of what we're building is, you can think of these, building these massively
parallel machines. Something like a, massively parallel Cray
machine, or something like that. They actually have multi stage networks
in the middle here, and all the nodes kind of sit on the outside.
Note the way I numbered this, this is the same thing as that, but I just didn't
want to draw all the wires going around. So, here, we're sort of drawing as if
data's flowing strictly from left to right.
[COUGH] And what we did here is we have eight nodes.
And, what you see here is there's, log two, number of stages here.
If you have. Two to one switches along the route here.
And something like an omega network actually has only one path between each
point, so if you want to get form here, let's say form eight to three.
You're going to have to go here, here. there, there.
You can't, there's no other paths you can take.
So let's say you routed straight at this first decision point, and went here.
You went up, you never really got up to three.
This is in contrast to some other multistage networks, where people
actually put in extra stages in the middle here.
And this gives you some path diversity so it'll allow you to route around in
congestions or route around problem links.
If you were to add, if we were to add one more stage it would look exactly the same
as the rest of these stages. because if you look here all these stages
have the same wiring in the middle, if you'll note.
[COUGH] If we add an extra stage, we'd actually be able to have multiple links
or multiple paths between the end points. And sometimes that's good.
Another type of network here that you can build is a tree.
I would say interesting topology. What, you probably want a tree though is
and. If you, if you want to be able to
communicate, let's say, from this half to that half of your machine, you're
going to want to somehow make the links wider as they go higher up in the tree
and that's what we call a fat tree. So a fat tree doubles the links each
level up in the hierarchy and then you have, let's say, this node wanted to
communicate with that node. There is enough bandwidth across this
back plane here, to support lots of nodes over here, communicate with lots of nodes
over there. One other interesting about a factory is
if you go and try to implement this across a 2D space, we'll say.
And you try to map this into 2D space, it actually starts to look pretty similar to
a mesh at some level, except it looks like a mesh that you removed links from.
So, think about that if you ever go to sit down to build a, tree, or a fact
tree. It actually looks just like a mesh,
except when you go to do the mapping of this you'll basically see that there's
this node and this node are very close in the 2-dimensional layout.
So you could just run on local wire, a sneak path between these two.
And then you'll also realize that this one and this one will be really close, so
you just run a sneak path between them. So to some extent some of these
topologies make not make as much sense in a certain packaging or a certain layout
in physical space. But if you, let's say, have multiple
chips, some manufacturing may make sense. [COUGH] So I wanted to introduce a piece
of nomenclature here that you'll see for mesh networks.
That you'll hear sometimes people talk about things as K-Ary N cubes.
And this using two numbers looking to completely describe a type of mesh
network. And we're going to use two numbers here.
The first one is K. So if you say phi vary, what that means
is, this is the number of. Nodes in any one dimension.
And, the n here in our n cube is the, number of dimensions.
So we can, this'll give us a way to describe things that are not strictly
hypercubes. So we can describe, sort of, other
shapes, but that are still some sort of, cube.
So, for an example here, we'll look at a three by three by three cube.
So this is kind of like a Rubik's Cube, or something like that.
And each one of the, the blocks in the Rubik's Cube corresponds to a node that
wants to communicate. And this is actually a three ary, three
cube mesh with no end around. And
we can see that the worse case path-link in here is going to be from here to here.
So it's going to be 1, 2,
4, 4,
5, 6, is that right? 2, 3, 4, 5, 6.
That's how many links we need to traverse to get from here to the farthest way
other point in the system.