In this course, you will learn to design the computer architecture of complex modern microprocessors.

Loading...

From the course by Princeton University

Computer Architecture

241 ratings

In this course, you will learn to design the computer architecture of complex modern microprocessors.

From the lesson

Multiprocessor Interconnect 2

This lecture covers the design of interconnects for multiprocessor and network topology.

- David WentzlaffAssistant Professor

Electrical Engineering

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.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.