1 00:00:04,540 --> 00:00:09,557 So we started last time, this is where we left off was talking about topologies. Now 2 00:00:09,557 --> 00:00:14,272 we went through this really fast, but I wanted to go into a little more detail 3 00:00:14,272 --> 00:00:19,048 here. So far, we've, in this class, we've been talking about buses. And actually 4 00:00:19,048 --> 00:00:23,279 buses are a type of interconnection network. So a multi-drop bus, where 5 00:00:23,279 --> 00:00:27,874 everyone just sort of screams, is a broadcast network. And it is, it is a type 6 00:00:27,874 --> 00:00:32,891 of interconnection network. But it may not have the best properties. It may not have 7 00:00:32,891 --> 00:00:37,330 the best bandwidth, and it might impact your clock frequency, so it might even 8 00:00:37,330 --> 00:00:42,040 impact your latency, depending on how you go about implementing one of these things. 9 00:00:42,340 --> 00:00:47,672 So sorta the next step away from something like a, a bus is actually something like a 10 00:00:47,672 --> 00:00:52,377 pipeline bus, where you start to put registers in along the way. And now you 11 00:00:52,377 --> 00:00:57,521 can have nearest neighbor communication. Let's say one is talking to two, and three 12 00:00:57,521 --> 00:01:02,477 is talking to four at the same time. But you couldn't do that when everyone was 13 00:01:02,477 --> 00:01:08,675 shouting to each other, as only one, one, entities allowed to talk on this network 14 00:01:08,675 --> 00:01:15,019 at a time. We'll say. So we start thinking about that. And we can actually make some 15 00:01:15,019 --> 00:01:20,613 more advanced versions of these. We can start to think about things like toruses, 16 00:01:20,613 --> 00:01:26,141 where we'll take the end here and connect it around. And this is a one-dimensional 17 00:01:26,141 --> 00:01:31,870 torus, or many times is known as a ring. one thing I wanted to point out about this 18 00:01:31,870 --> 00:01:36,858 is if you look at the naive ring implementation, and if you think of these 19 00:01:36,858 --> 00:01:42,183 are, as wires, you would say, 'Well, this is interesting. If I have a thousand nodes 20 00:01:42,183 --> 00:01:50,619 in my ring.' All of let's think about that. One, two, three, four. Yep, okay. If 21 00:01:50,619 --> 00:01:57,109 you have 1000 nodes per ring. 999 of'em are gonna have very short links, and then 22 00:01:57,109 --> 00:02:03,298 one of the links is gonna be super, super long, it's gonna go from this end all the 23 00:02:03,298 --> 00:02:10,965 way to that end like this is drawn. Hm. Well that's, that's not super great. 24 00:02:11,289 --> 00:02:20,690 communally, people have actually thought of fancy ways to fold tauruses into the, 25 00:02:20,690 --> 00:02:25,991 let's say if this is a 1-D torus into a 1-D space, and minimize the wire lay, 26 00:02:26,197 --> 00:02:31,361 lengths. So ac tually I drew a picture here to show this. If you remember and 27 00:02:31,361 --> 00:02:36,731 stagger the you connec-, the nodes here. This is the exact same 1-D torus as we 28 00:02:36,731 --> 00:02:42,239 drew here. Except now all the lengths are equally equidistant or equal length. 29 00:02:42,239 --> 00:02:47,640 Except they're twice the length as they were before. So, you can actually fold a 30 00:02:47,640 --> 00:02:53,370 torus into the same oh, oh, for instance, an n-dimensional torus into n-dimensional 31 00:02:53,370 --> 00:02:58,610 space, by doubling each the lengths, by doing this cool inner leaving trick. And 32 00:02:58,610 --> 00:03:03,493 this also applies for 2D, 3D, 4D Tauruses. Etc. You can, you can come up with some 33 00:03:03,493 --> 00:03:08,376 ordering and numbering which will actually, interleave like that. Now having 34 00:03:08,376 --> 00:03:13,510 said that, it may be challenging to build a four dimensional Taurus in three space. 35 00:03:13,510 --> 00:03:18,142 And fortunately, I live in three dimensional space, and I'm hoping you guys 36 00:03:18,142 --> 00:03:23,276 do too. and if you, if you're like me, and you live in three dimensional space. It 37 00:03:23,276 --> 00:03:28,347 can be hard to go build five dimensional things in three dimensional space. We'll 38 00:03:28,347 --> 00:03:33,106 talk about that in a minute. But I just want to show this cool trick that you can 39 00:03:33,106 --> 00:03:41,409 actually. Full day. 1-dimensional Taurus into 1-dimensional space and not have a 40 00:03:41,409 --> 00:03:48,091 super long link. Okay so now we can start to think about. Actually before, before we 41 00:03:48,091 --> 00:03:53,597 go on to that lets, lets think about the, the limits of this. If we start to go to a 42 00:03:53,597 --> 00:04:05,986 1,000. Long torus. Or a thousand 1d ringed or 1d torus. Unfortunately this does not, 43 00:04:05,986 --> 00:04:12,129 the amount of sort of bandwidth that you cut through here, let's say these two 44 00:04:12,129 --> 00:04:18,220 links here does not go up as we add nodes. And a good property of a network or inter 45 00:04:18,220 --> 00:04:22,358 connection network, is that as you add more people communicating on the network, 46 00:04:22,358 --> 00:04:26,444 or more entities communicating on the network, you probably want to be able to 47 00:04:26,444 --> 00:04:32,895 add more bandwidth. And you can say, well I can make the, the links wider, but that 48 00:04:32,895 --> 00:04:39,302 only helps so much. I can make the link faster, but it only helps so much. So this 49 00:04:39,302 --> 00:04:45,985 makes us think about having different topologies. So we can start to go to 50 00:04:45,985 --> 00:04:53,843 higher dimensioned topologies. So we can start to use 2D topologies, or 3D. and you 51 00:04:53,843 --> 00:05:01,068 can see here, here as we h ave lets say sixteen nodes arranged in a 2-dimensional 52 00:05:01,068 --> 00:05:08,142 mesh, versus, here we have a 2D torus. And the difference between the 2D mesh and the 53 00:05:08,142 --> 00:05:14,542 2D torus is that there's what's called end around in our, in the torus. And that 54 00:05:14,542 --> 00:05:20,863 makes the routing from here to there much, much faster, and effectively, we'll cut 55 00:05:20,863 --> 00:05:27,263 the, average routing time, or average routing, excuse me, average, hop count by 56 00:05:27,263 --> 00:05:33,800 a half. Because you can go either way now, and go around the ends. Sometimes, these 57 00:05:33,800 --> 00:05:40,112 2D toruses are called, a 2D mesh with end around. That means it's a torus. just, I 58 00:05:40,112 --> 00:05:46,206 just wanted to throw that nomenclature out there, cuz sometimes you'll see, you'll 59 00:05:46,206 --> 00:05:52,128 see both. A good example of a simple routing protocol is if you're at this node 60 00:05:52,128 --> 00:05:55,838 here. And you want to communicate some data you can send the data in all 61 00:05:55,838 --> 00:05:59,762 directions. And then everyone else sends it in all directions. And everyone else 62 00:05:59,762 --> 00:06:03,437 sends it in all directions. And it'll just flood the network, and it'll get 63 00:06:03,437 --> 00:06:07,014 everywhere. And you're guaranteed that it's going to at least get to the 64 00:06:07,014 --> 00:06:11,186 receiver, and you have some guarantee that when it gets to the receiver, the receiver 65 00:06:11,186 --> 00:06:15,309 sees the, the packet and takes it off. Now that may not be what you wanna do. . 66 00:06:15,309 --> 00:06:19,035 That's, that's probably not low power, and it's probably gonna cost a lot of 67 00:06:19,035 --> 00:06:22,860 congestion on your network, but you may wanna think about a flooding protocol. 68 00:06:24,580 --> 00:06:32,758 Okay, so wherever there is 2D we can start to go to 3D. So here we have a 69 00:06:32,758 --> 00:06:38,739 3-dimensional cube. Sort of. It's the best I could draw. It's, it's hard to draw 70 00:06:38,739 --> 00:06:45,265 3-dimensional things on 2-dimensional space. And if, if we had 3D space I could 71 00:06:45,265 --> 00:06:51,840 have drawn this much cooler. so this is a hypercube. Hope these are actually 72 00:06:51,840 --> 00:06:58,404 hypercubes. So, all the hypercube is, is it's saying that the number of the 73 00:06:58,404 --> 00:07:04,606 mentions you have . is equal to the number, or the degree or the outbound 74 00:07:04,606 --> 00:07:09,625 links of a, of a, of a node in the, in here. So, if you look at this node, we 75 00:07:09,625 --> 00:07:15,272 have a three dimensional hypercube. So it can go this direction, that direction, or 76 00:07:15,272 --> 00:07:20,361 that direction. Every node has a out degree of three, or a connectivity of 77 00:07:20,361 --> 00:07:27,006 three. Here, we have a four dimens, a four dimensional cube, but this is, by 78 00:07:27,006 --> 00:07:32,952 definition, a hyper cube. So, because, if you look at any given point here. So, 79 00:07:32,952 --> 00:07:39,301 we're gonna define a hyper cube as the out degree, of the nodes is equal to the 80 00:07:39,301 --> 00:07:45,649 dimension of, of the, the links. And, you can't go build here a, if you were to add 81 00:07:45,649 --> 00:07:52,747 one more node to the system, or some other. Let's say you were to scale this 82 00:07:52,747 --> 00:07:58,102 out in some direction, you would actually be increasing, the degree of a node by 83 00:07:58,102 --> 00:08:02,575 adding more, more nodes. But not to everybody, equally, so not be a, a 84 00:08:02,575 --> 00:08:08,684 hypercube. So if you were to build on a, something like this network here, this is, 85 00:08:08,684 --> 00:08:14,421 this is not strictly a hypercube because the degree of I'll say this note here is 86 00:08:14,421 --> 00:08:20,023 not equal to the degree of, well actually you could just stick with that. The degree 87 00:08:20,023 --> 00:08:24,880 is equal to the degree of the other places, but we've effectively increased 88 00:08:24,880 --> 00:08:29,581 the diameter of one of the dimensions such that there's not the routing distance is 89 00:08:29,581 --> 00:08:33,656 longer now for this number of nodes. If you were to go to a higher dimensional 90 00:08:33,656 --> 00:08:37,835 design, you could actually reduce the, the latency for each one of these nodes in 91 00:08:37,835 --> 00:08:42,433 something that's got three dimensional, three area three q, which we'll talk about 92 00:08:42,433 --> 00:08:49,777 in a minute. But here we have a four dimensional cube, and what's nice about 93 00:08:49,777 --> 00:08:56,692 this is the number of hops to get from here to anywhere else is quite low. So 94 00:08:56,692 --> 00:09:07,026 let's, let's, let's think where the farthest point in, in this. Cube is going 95 00:09:07,026 --> 00:09:15,577 to be. So it's going to be, let's think, is it here? Or is it here? One, two, 96 00:09:15,577 --> 00:09:28,220 three. No, it's the other one. Okay, so it's going to be one, two, three, four to 97 00:09:28,220 --> 00:09:40,280 get to there. Is going to be the farthest number of hops. So we can think about 98 00:09:40,280 --> 00:09:49,426 having these higher dimensional systems. Now, as may be readily apparent but I'll 99 00:09:49,426 --> 00:09:55,240 say it anyway, if you try to build a five dimensional hyper cube in three 100 00:09:55,240 --> 00:10:01,482 dimensional space some of the wires are gonna get long. Because you can't fold 101 00:10:01,482 --> 00:10:06,889 five dimensional space into three dimensional space. You might be able to 102 00:10:06,889 --> 00:10:11,709 span a 4-dimensional space into a 3-dimensional space with not, not too bad. 103 00:10:11,709 --> 00:10:16,979 But there's kind of this good rule of thumb when you're building networks that 104 00:10:16,979 --> 00:10:22,442 you probably don't want to be building a N, you probably want to a map let's say an 105 00:10:22,442 --> 00:10:27,519 N-dimensional network into N-dimensional space. Trying to map higher is painful, 106 00:10:27,519 --> 00:10:33,580 trying to map much, much higher is very painful. The benefits though is that, you 107 00:10:33,580 --> 00:10:39,138 have to have fewer routing, hops to get to be able to get wherever you're going, in 108 00:10:39,138 --> 00:10:47,012 the higher dimension cube. Now, I want to just throw this one up here because this 109 00:10:47,012 --> 00:10:54,993 is an interesting topology. Just connect everything to everything. This seems 110 00:10:54,993 --> 00:11:01,392 great, we should all build these networks, , unfortunately let's think about trying 111 00:11:01,392 --> 00:11:08,423 to put this network in three space if we have 1000 nodes. Well, what that means is, 112 00:11:08,423 --> 00:11:13,569 if you have 1000 nodes. You're gonna, each node is need, you're gonna need to have 113 00:11:13,569 --> 00:11:18,844 999 outbound connections. And 999 inbound connections. So when you go to build this, 114 00:11:18,844 --> 00:11:23,862 you might be able to build this, sort of, in a, outside of a sphere. Or, sort of, a 115 00:11:23,862 --> 00:11:28,686 big wiring mess on the inside. that's pretty hard to do at, for, for large 116 00:11:28,686 --> 00:11:33,704 numbers of nodes. For smalls numbers of nodes, something like a fully connected 117 00:11:33,704 --> 00:11:40,416 crossbar, or what's also known as a star topology, will probably work fine. But And 118 00:11:40,416 --> 00:11:44,750 in fact if you cut it sort of across the middle of the network here, which we'll 119 00:11:44,750 --> 00:11:51,252 talk about in a second. It has very good bandwidth. Okay, a few other things you 120 00:11:51,252 --> 00:11:57,826 guys should know about from a terminology perspective. . The networks that I've 121 00:11:57,826 --> 00:12:05,144 drawn to this point. On what are called direct networks. Which means that the 122 00:12:05,144 --> 00:12:11,802 nodes have some type of router built into ''em. You could also, and people, plenty 123 00:12:11,802 --> 00:12:16,826 of people build this, is they build networks where the nodes do not have 124 00:12:16,826 --> 00:12:21,939 routers built into them, but there's a multistage network or some sort of network 125 00:12:21,939 --> 00:12:27,118 in between the nodes. So a good example of this actually is something like your 126 00:12:27,315 --> 00:12:32,100 Internet if you will. There you have computer nodes, and computers are not 127 00:12:32,100 --> 00:12:36,164 doing the routing themselves. Instead they send it out to a what we'll call an 128 00:12:36,623 --> 00:12:42,261 Ethernet switch, and the Ethernet switch is lets say one of these boxes here in the 129 00:12:42,261 --> 00:12:47,440 middle. And that makes a decision and sends it on further. It could be a, a 130 00:12:47,440 --> 00:12:52,127 internet router, could be in the middle here also. And the analog in computer 131 00:12:52,127 --> 00:12:56,682 architecture, of what we're building is, you can think of these, building these 132 00:12:56,682 --> 00:13:01,473 massively parallel machines. Something like a, massively parallel Cray machine, 133 00:13:01,473 --> 00:13:06,324 or something like that. They actually have multi stage networks in the middle here, 134 00:13:06,324 --> 00:13:10,701 and all the nodes kind of sit on the outside. Note the way I numbered this, 135 00:13:10,701 --> 00:13:15,552 this is the same thing as that, but I just didn't want to draw all the wires going 136 00:13:15,552 --> 00:13:20,285 around. So, here, we're sort of drawing as if data's flowing strictly from left to 137 00:13:20,285 --> 00:13:28,757 right. And what we did here is we have eight nodes. And, what you see here is 138 00:13:28,757 --> 00:13:36,789 there's, log two, number of stages here. If you have. Two to one switches along the 139 00:13:36,789 --> 00:13:44,032 route here. And something like an omega network actually has only one path between 140 00:13:44,032 --> 00:13:50,480 each point, so if you want to get form here, let's say form eight to three. 141 00:13:50,780 --> 00:13:56,770 You're gonna have to go here, here. there, there. You can't, there's no other paths 142 00:13:56,770 --> 00:14:02,541 you can take. So let's say you routed straight at this first decision point, and 143 00:14:02,541 --> 00:14:08,239 went here. You went up, you never really got up to three. This is in contrast to 144 00:14:08,239 --> 00:14:14,083 some other multistage networks, where people actually put in extra stages in the 145 00:14:14,083 --> 00:14:20,171 middle here. And this gives you some path diversity so it'll allow you to route 146 00:14:20,171 --> 00:14:25,010 around in congestions or route around problem links. If you were to add, if we 147 00:14:25,010 --> 00:14:29,975 were to add one more stage it would look exactly the same as the rest of these 148 00:14:29,975 --> 00:14:35,003 stages. Cuz if you look here all these stages have the same wiring in the middle, 149 00:14:35,003 --> 00:14:40,471 if you'll note. If we add an extra stage, we'd actually be able to have multiple 150 00:14:40,471 --> 00:14:50,588 links or multiple paths between the end points. And sometimes that's good. Another 151 00:14:50,588 --> 00:15:01,238 type of network here that you can build is a tree. I would say interesting topology. 152 00:15:01,238 --> 00:15:08,674 What, you probably want a tree though is and. If you, if you want to be able to 153 00:15:08,674 --> 00:15:13,065 communicate, let's say, from this half to tha t half of your machine, you're gonna 154 00:15:13,065 --> 00:15:17,733 wanna somehow make the links wider as they go higher up in the tree and that's what 155 00:15:17,733 --> 00:15:22,291 we call a fat tree. So a fat tree doubles the links each level up in the hierarchy 156 00:15:22,291 --> 00:15:26,460 and then you have, let's say, this node wanted to communicate with that node. 157 00:15:26,860 --> 00:15:31,681 There is enough bandwidth across this back plane here, to support lots of nodes over 158 00:15:31,681 --> 00:15:38,322 here, communicate with lots of nodes over there. One other interesting about a 159 00:15:38,556 --> 00:15:45,271 factory is if you go and try to implement this across a 2D space, we'll say. And you 160 00:15:45,271 --> 00:15:51,908 try to map this into 2D space, it actually starts to look pretty similar to a mesh at 161 00:15:51,908 --> 00:15:58,729 some level, except it looks like a mesh that you removed links from. So, think 162 00:15:58,729 --> 00:16:05,310 about that if you ever go to sit down to build a, tree, or a fact tree. It actually 163 00:16:05,310 --> 00:16:10,961 looks just like a mesh, except when you go to do the mapping of this you'll basically 164 00:16:10,961 --> 00:16:15,905 see that there's this node and this node are very close in the 2-dimensional 165 00:16:15,905 --> 00:16:20,914 layout. So you could just run on local wire, a sneak path between these two. And 166 00:16:20,914 --> 00:16:26,372 then you'll also realize that this one and this one will be really close, so you just 167 00:16:26,372 --> 00:16:31,830 run a sneak path between them. So to some extent some of these topologies make not 168 00:16:31,830 --> 00:16:39,207 make as much sense in a certain packaging or a certain layout in physical space. But 169 00:16:39,207 --> 00:16:46,293 if you, let's say, have multiple chips, some manufacturing may make sense. So I 170 00:16:46,293 --> 00:16:50,995 wanted to introduce a piece of nomenclature here that you'll see for mesh 171 00:16:50,995 --> 00:17:01,206 networks. That you'll hear sometimes people talk about things as K-Ary N cubes. 172 00:17:01,206 --> 00:17:07,696 And this using two numbers looking to completely describe a type of mesh 173 00:17:07,696 --> 00:17:16,638 network. And we're gonna use two numbers here. The first one is K. So if you say 174 00:17:16,958 --> 00:17:26,120 phi vary, what that means is, this is the number of. Nodes in any one dimension. 175 00:17:27,660 --> 00:17:34,423 And, the n here in our n cube is the, number of dimensions. So we can, this'll 176 00:17:34,423 --> 00:17:41,013 give us a way to describe things that are not strictly hypercubes. So we can 177 00:17:41,013 --> 00:17:47,950 describe, sort of, other shapes, but that are still some sort of, cube. So, for an 178 00:17:47,950 --> 00:17:54,862 example here, we'll look at a three by three by three cube. So this is kind of 179 00:17:54,862 --> 00:18:00,386 like a Rubik's Cube, or something like that. And each one of the, the blocks in 180 00:18:00,386 --> 00:18:05,909 the Rubik's Cube corresponds to a node that wants to communicate. And this is 181 00:18:05,909 --> 00:18:17,217 actually a three ary, three cube mesh with no end around. And we can see that the 182 00:18:17,217 --> 00:18:28,920 worse case path-link in here is going to be from here to here. So it's going to be 183 00:18:28,920 --> 00:18:42,499 one, two, four, four, five, six, is that right? two, three, four, five, six. 184 00:18:42,520 --> 00:18:46,826 That's how many links we need to traverse to get from here to the farthest way other 185 00:18:46,826 --> 00:18:47,840 point in the system.