1 00:00:04,540 --> 00:00:09,315 So we started last time, this is where we left off was talking about topologies. 2 00:00:09,315 --> 00:00:14,272 Now we went through this really fast, but I wanted to go into a little more detail 3 00:00:14,272 --> 00:00:17,053 here. So far, we've, in this class, we've been 4 00:00:17,053 --> 00:00:20,257 talking about buses. And actually buses are a type of 5 00:00:20,257 --> 00:00:24,126 interconnection network. So a multi-drop bus, where everyone just 6 00:00:24,126 --> 00:00:28,055 sort of screams, is a broadcast network. And it is, it is a type of 7 00:00:28,055 --> 00:00:31,924 interconnection network. But it may not have the best properties. 8 00:00:31,924 --> 00:00:36,366 It may not have the best bandwidth, and it might impact your clock frequency, 9 00:00:36,366 --> 00:00:40,167 so it might even impact your latency, depending on how you go about 10 00:00:40,167 --> 00:00:44,410 implementing one of these things. So sort of the next step away from 11 00:00:44,410 --> 00:00:48,487 something like a, a bus is actually something like a pipeline bus, 12 00:00:48,487 --> 00:00:51,624 where you start to put registers in along the way. 13 00:00:51,624 --> 00:00:54,886 And now you can have nearest neighbor communication. 14 00:00:54,886 --> 00:00:59,465 Let's say one is talking to two, and three is talking to four at the same 15 00:00:59,465 --> 00:01:02,226 time. But you couldn't do that when everyone 16 00:01:02,226 --> 00:01:08,089 was shouting to each other, as only one, one, entities allowed to talk on this 17 00:01:08,089 --> 00:01:10,840 network at a time. We'll say. 18 00:01:10,840 --> 00:01:15,356 So we start thinking about that. And we can actually make some more 19 00:01:15,356 --> 00:01:20,074 advanced versions of these. We can start to think about things like 20 00:01:20,074 --> 00:01:24,118 toruses, where we'll take the end here and connect it around. 21 00:01:24,118 --> 00:01:28,769 And this is a one-dimensional torus, or many times is known as a ring. 22 00:01:28,769 --> 00:01:34,095 one thing I wanted to point out about this is if you look at the naive ring 23 00:01:34,095 --> 00:01:39,352 implementation, and if you think of these are, as wires, you would say, 'Well, this 24 00:01:39,352 --> 00:01:43,060 is interesting. If I have a thousand nodes in my ring.' 25 00:01:45,940 --> 00:01:49,742 All of let's think about that. One, two, three, four. 26 00:01:49,742 --> 00:01:53,260 Yep, okay. If you have 1000 nodes per ring. 27 00:01:53,260 --> 00:01:58,618 999 of'em are going to have very short links, and then one of the links is 28 00:01:58,618 --> 00:02:03,826 going to be super, super long, it's going to go from this end all the way to 29 00:02:03,826 --> 00:02:07,184 that end like this is drawn. Hm. 30 00:02:07,184 --> 00:02:15,719 Well that's, that's not super great. communally, people have actually thought 31 00:02:15,719 --> 00:02:23,443 of fancy ways to fold tauruses into the, let's say if this is a 1-D torus into a 32 00:02:23,443 --> 00:02:26,748 1-D space, and minimize the wire lay, lengths. 33 00:02:26,748 --> 00:02:29,984 So actually I drew a picture here to show this. 34 00:02:29,984 --> 00:02:34,046 If you remember and stagger the you connec-, the nodes here. 35 00:02:34,046 --> 00:02:37,420 This is the exact same 1-D torus as we drew here. 36 00:02:37,420 --> 00:02:42,239 Except now all the lengths are equally equidistant or equal length. 37 00:02:42,239 --> 00:02:45,820 Except they're twice the length as they were before. 38 00:02:45,820 --> 00:02:50,539 So, you can actually fold a torus into the same oh, oh, for instance, an 39 00:02:50,539 --> 00:02:55,932 n-dimensional torus into n-dimensional space, by doubling each the lengths, by 40 00:02:55,932 --> 00:03:00,551 doing this cool inner leaving trick. And this also applies for 2D, 3D, 4D 41 00:03:00,551 --> 00:03:01,364 Tauruses. Etc. 42 00:03:01,364 --> 00:03:05,622 You can, you can come up with some ordering and numbering which will 43 00:03:05,622 --> 00:03:09,628 actually, interleave like that. Now having said that, it may be 44 00:03:09,628 --> 00:03:13,510 challenging to build a four dimensional Taurus in three space. 45 00:03:13,510 --> 00:03:17,829 And fortunately, I live in three dimensional space, and I'm hoping you 46 00:03:17,829 --> 00:03:21,085 guys do too. and if you, if you're like me, and you 47 00:03:21,085 --> 00:03:25,091 live in three dimensional space. It can be hard to go build five 48 00:03:25,091 --> 00:03:27,971 dimensional things in three dimensional space. 49 00:03:27,971 --> 00:03:32,408 We'll talk about that in a minute. But I just want to show this cool trick 50 00:03:32,408 --> 00:03:36,720 that you can actually. Full day. 51 00:03:36,720 --> 00:03:42,640 1-dimensional Taurus into 1-dimensional space and not have a super long link. 52 00:03:43,660 --> 00:03:49,031 Okay so now we can start to think about. Actually before, before we go on to that 53 00:03:49,031 --> 00:03:52,052 lets, lets think about the, the limits of this. 54 00:03:52,052 --> 00:03:55,822 If we start to go to a 1,000. Long torus. 55 00:03:55,822 --> 00:04:07,238 Or a thousand 1d ringed or 1d torus. Unfortunately this does not, the amount 56 00:04:07,238 --> 00:04:13,238 of sort of bandwidth that you cut through here, let's say these two links here does 57 00:04:13,238 --> 00:04:18,220 not go up as we add nodes. And a good property of a network or inter 58 00:04:18,220 --> 00:04:22,358 connection network, is that as you add more people communicating on the network, 59 00:04:22,358 --> 00:04:26,444 or more entities communicating on the network, you probably want to be able to 60 00:04:26,444 --> 00:04:30,893 add more bandwidth. And you can say, well I can make the, the 61 00:04:30,893 --> 00:04:34,068 links wider, but that only helps so much. 62 00:04:34,068 --> 00:04:37,340 I can make the link faster, but it only helps so much. 63 00:04:38,580 --> 00:04:43,727 So this makes us think about having different topologies. 64 00:04:43,727 --> 00:04:48,695 So we can start to go to higher dimensioned topologies. 65 00:04:48,695 --> 00:04:52,849 So we can start to use 2D topologies, or 3D. 66 00:04:52,849 --> 00:04:59,804 and you can see here, here as we have lets say 16 nodes arranged in a 67 00:04:59,804 --> 00:05:04,428 2-dimensional mesh, versus, here we have a 2D torus. 68 00:05:04,428 --> 00:05:10,749 And the difference between the 2D mesh and the 2D torus is that there's what's 69 00:05:10,749 --> 00:05:16,991 called end around in our, in the torus. And that makes the routing from here to 70 00:05:16,991 --> 00:05:22,048 there much, much faster, and effectively, we'll cut the, average 71 00:05:22,048 --> 00:05:25,366 routing time, or average routing, excuse me, 72 00:05:25,366 --> 00:05:31,055 average, hop count by a half. Because you can go either way now, and go 73 00:05:31,055 --> 00:05:35,832 around the ends. Sometimes, these 2D toruses are called, a 74 00:05:35,832 --> 00:05:39,386 2D mesh with end around. That means it's a torus. 75 00:05:39,386 --> 00:05:44,900 just, I just wanted to throw that nomenclature out there, because sometimes 76 00:05:44,900 --> 00:05:49,455 you'll see, you'll see both. A good example of a simple routing 77 00:05:49,455 --> 00:05:54,596 protocol is if you're at this node here. And you want to communicate some data you 78 00:05:54,596 --> 00:05:58,321 can send the data in all directions. And then everyone else sends it in all 79 00:05:58,321 --> 00:06:00,556 directions. And everyone else sends it in all 80 00:06:00,556 --> 00:06:02,941 directions. And it'll just flood the network, and 81 00:06:02,941 --> 00:06:06,020 it'll get everywhere. And you're guaranteed that it's going to 82 00:06:06,020 --> 00:06:09,498 at least get to the receiver, and you have some guarantee that when it 83 00:06:09,498 --> 00:06:13,024 gets to the receiver, the receiver sees the, the packet and takes it off. 84 00:06:13,024 --> 00:06:15,309 Now that may not be what you want to do. [LAUGH]. 85 00:06:15,309 --> 00:06:19,035 That's, that's probably not low power, and it's probably going to cost a lot of 86 00:06:19,035 --> 00:06:21,965 congestion on your network, but you may want to think about a 87 00:06:21,965 --> 00:06:28,900 flooding protocol. Okay, so wherever there is 2D we can 88 00:06:28,900 --> 00:06:34,234 start to go to 3D. So here we have a 3-dimensional cube. 89 00:06:34,234 --> 00:06:36,953 Sort of. It's the best I could draw. 90 00:06:36,953 --> 00:06:42,623 It's, it's hard to draw 3-dimensional things on 2-dimensional space. 91 00:06:42,623 --> 00:06:47,440 And if, if we had 3D space I could have drawn this much cooler. 92 00:06:47,440 --> 00:06:52,890 so this is a hypercube. Hope these are actually hypercubes. 93 00:06:52,890 --> 00:06:59,979 So, all the hypercube is, is it's saying that the number of the mentions you have 94 00:06:59,979 --> 00:07:03,700 [COUGH]. is equal to the number, or the degree or 95 00:07:03,700 --> 00:07:07,464 the outbound links of a, of a, of a node in the, in here. 96 00:07:07,464 --> 00:07:12,065 So, if you look at this node, we have a three dimensional hypercube. 97 00:07:12,065 --> 00:07:16,318 So it can go this direction, that direction, or that direction. 98 00:07:16,318 --> 00:07:21,220 Every node has a out degree of three, or a connectivity of three. 99 00:07:21,220 --> 00:07:27,006 Here, we have a four dimens, a four dimensional cube, but this is, by 100 00:07:27,006 --> 00:07:31,827 definition, a hyper cube. So, because, if you look at any given 101 00:07:31,827 --> 00:07:35,765 point here. So, we're going to define a hyper cube as 102 00:07:35,765 --> 00:07:41,712 the out degree, of the nodes is equal to the dimension of, of the, the links. 103 00:07:41,712 --> 00:07:47,900 And, you can't go build here a, if you were to add one more node to the system, 104 00:07:49,020 --> 00:07:53,222 [COUGH] or some other. Let's say you were to scale this out in 105 00:07:53,222 --> 00:07:56,746 some direction, you would actually be increasing, the 106 00:07:56,746 --> 00:07:59,661 degree of a node by adding more, more nodes. 107 00:07:59,661 --> 00:08:03,253 But not to everybody, equally, so not be a, a hypercube. 108 00:08:03,253 --> 00:08:09,224 So if you were to build on a, something like this network here, this is, this is 109 00:08:09,224 --> 00:08:14,691 not strictly a hypercube because the degree of I'll say this note here is not 110 00:08:14,691 --> 00:08:19,280 equal to the degree of, well actually you could just stick with that. 111 00:08:19,280 --> 00:08:24,410 The degree is equal to the degree of the other places, but we've effectively 112 00:08:24,410 --> 00:08:28,537 increased the diameter of one of the dimensions such that there's not the 113 00:08:28,537 --> 00:08:31,462 routing distance is longer now for this number of nodes. 114 00:08:31,462 --> 00:08:35,589 If you were to go to a higher dimensional design, you could actually reduce the, 115 00:08:35,589 --> 00:08:39,246 the latency for each one of these nodes in something that's got three 116 00:08:39,246 --> 00:08:43,060 dimensional, three area three q, which we'll talk about in a minute. 117 00:08:44,120 --> 00:08:51,483 But here we have a four dimensional cube, and what's nice about this is the number 118 00:08:51,483 --> 00:08:56,422 of hops to get from here to anywhere else is quite low. 119 00:08:56,422 --> 00:09:02,080 So let's, let's, let's think where the farthest point in, in this. 120 00:09:05,340 --> 00:09:12,325 Cube is going to be. So it's going to be, let's think, is it 121 00:09:12,325 --> 00:09:14,613 here? Or is it here? 122 00:09:14,613 --> 00:09:23,520 One, two, three. No, it's the other one. 123 00:09:23,520 --> 00:09:30,000 Okay, so it's going to be one, two, three, four to get to there. 124 00:09:30,000 --> 00:09:33,460 Is going to be the farthest number of hops. 125 00:09:38,300 --> 00:09:43,880 So we can think about having these higher dimensional systems. 126 00:09:43,880 --> 00:09:52,691 Now, as may be readily apparent but I'll say it anyway, if you try to build a five 127 00:09:52,691 --> 00:09:58,425 dimensional hyper cube in three dimensional space some of the wires are 128 00:09:58,425 --> 00:10:02,534 going to get long. Because you can't fold five dimensional 129 00:10:02,534 --> 00:10:08,239 space into three dimensional space. You might be able to span a 4-dimensional 130 00:10:08,239 --> 00:10:11,709 space into a 3-dimensional space with not, not too bad. 131 00:10:11,709 --> 00:10:16,979 But there's kind of this good rule of thumb when you're building networks that 132 00:10:16,979 --> 00:10:19,871 you probably don't want to be building a N, 133 00:10:19,871 --> 00:10:25,077 you probably want to a map let's say an N-dimensional network into N-dimensional 134 00:10:25,077 --> 00:10:27,519 space. Trying to map higher is painful, 135 00:10:27,519 --> 00:10:30,540 trying to map much, much higher is very painful. 136 00:10:31,560 --> 00:10:36,801 The benefits though is that, you have to have fewer routing, hops to get to be 137 00:10:36,801 --> 00:10:40,780 able to get wherever you're going, in the higher dimension cube. 138 00:10:43,900 --> 00:10:48,030 Now, I want to just throw this one up here because this is an interesting 139 00:10:48,030 --> 00:10:51,620 topology. Just connect everything to everything. 140 00:10:54,220 --> 00:10:59,634 This seems great, we should all build these networks, [COUGH], unfortunately 141 00:10:59,634 --> 00:11:04,978 let's think about trying to put this network in three space if we have 1000 142 00:11:04,978 --> 00:11:09,195 nodes. Well, what that means is, if you have 143 00:11:09,195 --> 00:11:11,897 1000 nodes. You're going to, each node is need, 144 00:11:11,897 --> 00:11:15,178 you're going to need to have 999 outbound connections. 145 00:11:15,178 --> 00:11:19,488 And 999 inbound connections. So when you go to build this, you might 146 00:11:19,488 --> 00:11:23,025 be able to build this, sort of, in a, outside of a sphere. 147 00:11:23,025 --> 00:11:25,792 Or, sort of, a big wiring mess on the inside. 148 00:11:25,792 --> 00:11:29,780 that's pretty hard to do at, for, for large numbers of nodes. 149 00:11:29,780 --> 00:11:34,476 For smalls numbers of nodes, something like a fully connected crossbar, or 150 00:11:34,476 --> 00:11:38,400 what's also known as a star topology, will probably work fine. 151 00:11:39,820 --> 00:11:42,420 But And in fact if you cut it sort of across 152 00:11:42,420 --> 00:11:45,997 the middle of the network here, which we'll talk about in a second. 153 00:11:45,997 --> 00:11:52,234 It has very good bandwidth. Okay, a few other things you guys should 154 00:11:52,234 --> 00:11:55,480 know about from a terminology perspective. 155 00:11:55,480 --> 00:11:58,885 [COUGH]. The networks that I've drawn to this 156 00:11:58,885 --> 00:12:03,320 point. On what are called direct networks. 157 00:12:03,320 --> 00:12:09,780 Which means that the nodes have some type of router built into 'em. 158 00:12:09,780 --> 00:12:14,499 You could also, and people, plenty of people build this, is they build networks 159 00:12:14,499 --> 00:12:19,842 where the nodes do not have routers built into them, but there's a multistage 160 00:12:19,842 --> 00:12:23,316 network or some sort of network in between the nodes. 161 00:12:23,316 --> 00:12:28,691 So a good example of this actually is something like your Internet if you will. 162 00:12:28,691 --> 00:12:33,280 There you have computer nodes, and computers are not doing the routing 163 00:12:33,280 --> 00:12:36,164 themselves. Instead they send it out to a what we'll 164 00:12:36,164 --> 00:12:41,474 call an Ethernet switch, and the Ethernet switch is lets say one of these boxes 165 00:12:41,474 --> 00:12:45,927 here in the middle. And that makes a decision and sends it on 166 00:12:45,927 --> 00:12:48,827 further. It could be a, a internet router, could 167 00:12:48,827 --> 00:12:52,896 be in the middle here also. And the analog in computer architecture, 168 00:12:52,896 --> 00:12:57,273 of what we're building is, you can think of these, building these massively 169 00:12:57,273 --> 00:13:01,000 parallel machines. Something like a, massively parallel Cray 170 00:13:01,000 --> 00:13:05,200 machine, or something like that. They actually have multi stage networks 171 00:13:05,200 --> 00:13:08,986 in the middle here, and all the nodes kind of sit on the outside. 172 00:13:08,986 --> 00:13:13,600 Note the way I numbered this, this is the same thing as that, but I just didn't 173 00:13:13,600 --> 00:13:18,096 want to draw all the wires going around. So, here, we're sort of drawing as if 174 00:13:18,096 --> 00:13:20,960 data's flowing strictly from left to right. 175 00:13:20,960 --> 00:13:26,225 [COUGH] And what we did here is we have eight nodes. 176 00:13:26,225 --> 00:13:32,604 And, what you see here is there's, log two, number of stages here. 177 00:13:32,604 --> 00:13:37,761 If you have. Two to one switches along the route here. 178 00:13:37,761 --> 00:13:44,473 And something like an omega network actually has only one path between each 179 00:13:44,473 --> 00:13:50,780 point, so if you want to get form here, let's say form eight to three. 180 00:13:50,780 --> 00:13:54,359 You're going to have to go here, here. there, there. 181 00:13:54,359 --> 00:13:57,719 You can't, there's no other paths you can take. 182 00:13:57,719 --> 00:14:03,271 So let's say you routed straight at this first decision point, and went here. 183 00:14:03,271 --> 00:14:06,559 You went up, you never really got up to three. 184 00:14:06,559 --> 00:14:11,453 This is in contrast to some other multistage networks, where people 185 00:14:11,453 --> 00:14:15,960 actually put in extra stages in the middle here. 186 00:14:15,960 --> 00:14:20,799 And this gives you some path diversity so it'll allow you to route around in 187 00:14:20,799 --> 00:14:23,439 congestions or route around problem links. 188 00:14:23,439 --> 00:14:28,655 If you were to add, if we were to add one more stage it would look exactly the same 189 00:14:28,655 --> 00:14:32,804 as the rest of these stages. because if you look here all these stages 190 00:14:32,804 --> 00:14:35,946 have the same wiring in the middle, if you'll note. 191 00:14:35,946 --> 00:14:40,848 [COUGH] If we add an extra stage, we'd actually be able to have multiple links 192 00:14:40,848 --> 00:14:45,060 or multiple paths between the end points. And sometimes that's good. 193 00:14:49,860 --> 00:14:55,520 Another type of network here that you can build is a tree. 194 00:14:55,520 --> 00:15:05,979 I would say interesting topology. What, you probably want a tree though is 195 00:15:05,979 --> 00:15:08,674 and. If you, if you want to be able to 196 00:15:08,674 --> 00:15:12,731 communicate, let's say, from this half to that half of your machine, you're 197 00:15:12,731 --> 00:15:16,844 going to want to somehow make the links wider as they go higher up in the tree 198 00:15:16,844 --> 00:15:20,846 and that's what we call a fat tree. So a fat tree doubles the links each 199 00:15:20,846 --> 00:15:24,959 level up in the hierarchy and then you have, let's say, this node wanted to 200 00:15:24,959 --> 00:15:29,041 communicate with that node. There is enough bandwidth across this 201 00:15:29,041 --> 00:15:33,748 back plane here, to support lots of nodes over here, communicate with lots of nodes 202 00:15:33,748 --> 00:15:39,415 over there. One other interesting about a factory is 203 00:15:39,415 --> 00:15:44,647 if you go and try to implement this across a 2D space, we'll say. 204 00:15:44,647 --> 00:15:51,127 And you try to map this into 2D space, it actually starts to look pretty similar to 205 00:15:51,127 --> 00:15:58,040 a mesh at some level, except it looks like a mesh that you removed links from. 206 00:15:58,040 --> 00:16:03,247 So, think about that if you ever go to sit down to build a, tree, or a fact 207 00:16:03,247 --> 00:16:06,980 tree. It actually looks just like a mesh, 208 00:16:06,980 --> 00:16:12,052 except when you go to do the mapping of this you'll basically see that there's 209 00:16:12,052 --> 00:16:16,355 this node and this node are very close in the 2-dimensional layout. 210 00:16:16,355 --> 00:16:20,657 So you could just run on local wire, a sneak path between these two. 211 00:16:20,657 --> 00:16:25,794 And then you'll also realize that this one and this one will be really close, so 212 00:16:25,794 --> 00:16:30,546 you just run a sneak path between them. So to some extent some of these 213 00:16:30,546 --> 00:16:36,004 topologies make not make as much sense in a certain packaging or a certain layout 214 00:16:36,004 --> 00:16:41,282 in physical space. But if you, let's say, have multiple 215 00:16:41,282 --> 00:16:47,905 chips, some manufacturing may make sense. [COUGH] So I wanted to introduce a piece 216 00:16:47,905 --> 00:16:51,600 of nomenclature here that you'll see for mesh networks. 217 00:16:55,400 --> 00:17:01,206 That you'll hear sometimes people talk about things as K-Ary N cubes. 218 00:17:01,206 --> 00:17:07,696 And this using two numbers looking to completely describe a type of mesh 219 00:17:07,696 --> 00:17:13,113 network. And we're going to use two numbers here. 220 00:17:13,113 --> 00:17:19,629 The first one is K. So if you say phi vary, what that means 221 00:17:19,629 --> 00:17:26,120 is, this is the number of. Nodes in any one dimension. 222 00:17:27,660 --> 00:17:32,862 And, the n here in our n cube is the, number of dimensions. 223 00:17:32,862 --> 00:17:39,192 So we can, this'll give us a way to describe things that are not strictly 224 00:17:39,192 --> 00:17:43,008 hypercubes. So we can describe, sort of, other 225 00:17:43,008 --> 00:17:47,083 shapes, but that are still some sort of, cube. 226 00:17:47,083 --> 00:17:53,500 So, for an example here, we'll look at a three by three by three cube. 227 00:17:53,500 --> 00:17:57,947 So this is kind of like a Rubik's Cube, or something like that. 228 00:17:57,947 --> 00:18:03,542 And each one of the, the blocks in the Rubik's Cube corresponds to a node that 229 00:18:03,542 --> 00:18:08,419 wants to communicate. And this is actually a three ary, three 230 00:18:08,419 --> 00:18:14,240 cube mesh with no end around. And 231 00:18:15,520 --> 00:18:26,740 we can see that the worse case path-link in here is going to be from here to here. 232 00:18:26,740 --> 00:18:31,730 So it's going to be 1, 2, 233 00:18:31,730 --> 00:18:34,040 4, 4, 234 00:18:34,040 --> 00:18:40,440 5, 6, is that right? 2, 3, 4, 5, 6. 235 00:18:42,520 --> 00:18:46,522 That's how many links we need to traverse to get from here to the farthest way 236 00:18:46,522 --> 00:18:47,840 other point in the system.