| 00:03 | right. So the dates new dotage to connection networks, which is almost |
|
| 00:13 | integral part and an important part. . So I decided Thio Society early |
|
| 00:22 | in the lectures, too. Give coverage off clustering to connection networks. |
|
| 00:33 | the reason is, I guess, to motivate it on this particular slide |
|
| 00:41 | in some ways it's the weakest part terms of performance on clusters. So |
|
| 00:48 | know that then harping on memory charity done throughout the course is that on |
|
| 00:56 | is reasonable. Okay, between caches functional units. Once you go off |
|
| 01:01 | onto the main memory or the then, um, it becomes considerably |
|
| 01:08 | by se is a rule of thumb the two orders of magnitude on When |
|
| 01:15 | start to go off the notes, interconnect other notes. Then it's again |
|
| 01:20 | capabilities drops by wanted two or even orders of magnitude. So understanding the |
|
| 01:30 | is an important aspect. And of , it depends upon how much communication |
|
| 01:36 | application actually needs. So that's clearly little room. Caveat. Eso the |
|
| 01:46 | platform. Okay, uh, codes if the notes are not so |
|
| 01:56 | sort of needs you need a lots notes for them. A lot off |
|
| 02:01 | performance will be impacted by the network the network traffic. Um, |
|
| 02:09 | this is a We talked a little NPR, sometimes some NPR implementations or |
|
| 02:14 | of the resource managers used by P. I tried to be clever |
|
| 02:21 | the placement off petitions if you're defined like we talk about in the last |
|
| 02:29 | or they can try to force um, yourself. So depending on |
|
| 02:35 | kind of network can have its widely what capabilities are as well as the |
|
| 02:41 | . So today I want to give some sense for what different networks are |
|
| 02:46 | used and relative merits. So that's of the background from today. So |
|
| 02:55 | is. But I'll talk. But I was spend time on the network |
|
| 03:06 | just to remind me a little bit communication. Protocol will talk very briefly |
|
| 03:10 | it and some previous lecture until when got in to start to talk about |
|
| 03:16 | , about the protocols that are being . There is one aspect software |
|
| 03:23 | Other things that affect the behavior is this network has built an acceptable uni |
|
| 03:30 | some kind of switches. And then a whole lot of different type off |
|
| 03:37 | that has been used and are used uh huh, doing month to process |
|
| 03:43 | systems. But and I'll try to you I'll give you a very simple |
|
| 03:49 | model that this gives you some intuition the relative expense as well as some |
|
| 03:59 | the merits off the different networks. , um, if you ever had |
|
| 04:06 | discrete math class and talking about they may talk about sort of distance |
|
| 04:12 | diameter. Um, I'm sure but it's not so common in many |
|
| 04:20 | the indiscreet classes to look at what's in the computer system. There is |
|
| 04:25 | by section with I'll talk about This a few unique networks that has been |
|
| 04:31 | or are used in building clusters. then, of course, another important |
|
| 04:38 | of how there are in this I don't plan to get into that |
|
| 04:42 | , and maybe all make some comment lecture, but so here is kind |
|
| 04:49 | locked. They are kind of today a background remind your first about |
|
| 04:56 | sorry question. Yeah, I had question. While we're on the motivation |
|
| 05:01 | interconnection networks. Um, is there that at the conceptual level makes this |
|
| 05:07 | different than just being another level of ? Yeah. Yes, because, |
|
| 05:22 | , if I want to kind of about no stuff like cash, the |
|
| 05:31 | it kind off notion would be that causes a lot of numa effect non |
|
| 05:38 | memory accesses. So the properties of network becomes important. Okay, that |
|
| 05:52 | sense. Not that is just And that's what I hope to try |
|
| 05:55 | convey when we talk about this apologists particular. So first I talk, |
|
| 06:07 | I won't get into them. But remind you on a very high level |
|
| 06:11 | of what kind of protocols are common networks being used for giving computers, |
|
| 06:17 | or clusters than networks tend to be as director indirect. I'll try to |
|
| 06:26 | that clear what it is. It's intuitive. Hopefully then things a little |
|
| 06:31 | more tricky and, well, just a little about the evolution on switches |
|
| 06:38 | how it effects our networks, has built or is built, and then |
|
| 06:44 | very simplistic cost model That's kind of you a rule of thumb Bors to |
|
| 06:49 | to expect. Um, that's just , fully interconnected network is to be |
|
| 06:55 | very nice because everybody can talk directly everybody else, but the cost becomes |
|
| 07:01 | . In doing so, someone needs sort of figure out trade offs between |
|
| 07:08 | , um, benefits and doing their on. That comes when I talked |
|
| 07:13 | apologies, and I'll try to I wrap it up a little bit hopeful |
|
| 07:19 | the in the lecture. Just recall about Internet. And this is and |
|
| 07:28 | known as if in a band uh, both system and interconnections are |
|
| 07:34 | used in building clusters and, depending your application needs how relative calm communication |
|
| 07:44 | terms of they are one not be to do with the Net the common |
|
| 07:51 | widely used in protocol for communication Typically, when you use in local |
|
| 07:57 | networks and in recent years, years in wide area networks, regional, |
|
| 08:04 | national scale tech networks, Internet and this way pretty much into every aspect |
|
| 08:10 | networking. The drawback has nothing. before is that yeah has a relatively |
|
| 08:20 | overhead in terms of protocol stack. when Leighton see is important the Internet |
|
| 08:27 | usually not used as far as I . For those of you use, |
|
| 08:34 | were very systems that tend to. being a probably has Internet. If |
|
| 08:39 | remember correctly, he could have and an advantage in the bands. This |
|
| 08:44 | standard and focused on Hi Bamut and See, and it's also relatively costly |
|
| 08:57 | with Internet. Except that's not entirely when it comes to very relatively higher |
|
| 09:06 | of the line Ethan s standards, is maybe a little bit cheaper about |
|
| 09:11 | significantly cheaper. Um, and this will have some of the data points |
|
| 09:19 | terms of the data has been used well as Layton sees to get through |
|
| 09:25 | and execute routing protocols, whatever that be. Eso if you see you |
|
| 09:32 | , it's for them. If in band switches, they are in the |
|
| 09:38 | of tends still maybe about 100 And as you probably remember, you |
|
| 09:45 | , processors operate, you know, the range of 2 to 4 |
|
| 09:50 | So that means it's a couple of few 100 CPU cycles to get through |
|
| 09:58 | single switch. And then this was of the bus that is used for |
|
| 10:07 | the network, whether it's done based the Ethernet transgendered anti protocol. Now |
|
| 10:14 | other thing waas this notional direct forces direct network and is just a |
|
| 10:20 | um so in the Interact Network that on the left side of the |
|
| 10:25 | it's essentially the the think off notes Compute notes as being at the in |
|
| 10:33 | sense, that the leaves of the of the networks and whereas in the |
|
| 10:39 | into connect every compute note may have routing switch that connects to rotten switches |
|
| 10:48 | other notes. On this for simplicity the cartoon picture my sort of hey |
|
| 10:56 | leaning in the sense it kind off infer that there will be like two |
|
| 11:01 | former mesh or related in To Connect this is by normals, the way |
|
| 11:07 | tends to be built and now exemplify as we go. So I'm just |
|
| 11:13 | that don't infer that this is kind playing or type into connected that is |
|
| 11:19 | used. Um, so and it on this fairly general before I dive |
|
| 11:29 | talking a little bit about switches switch so switch capabilities has improved over the |
|
| 11:46 | like very much following, uh, capabilities. That means improving more or |
|
| 11:54 | according to Morse law, in terms , not just density of transistors but |
|
| 12:01 | in terms, off capabilities. And this case, is capability moving bits |
|
| 12:10 | talk a little bit. I think that was capable. Is one talked |
|
| 12:16 | the had the Empower eight or nine the past? So now what it |
|
| 12:27 | on the right hand side of like the graph on the left, |
|
| 12:31 | somewhat old. I'm sorry I haven't them in good statistics are more recent |
|
| 12:36 | , except under the both graphs. is sort of a line on state |
|
| 12:43 | the art switch capabilities that is pretty in terms off, getting up to |
|
| 12:50 | bits per second capability off passing bits input to output. Now, one |
|
| 12:59 | the choices are important. ISS How use this bandwidth on one can |
|
| 13:09 | as is kind of illustrated on the side of the slide. Thio, |
|
| 13:17 | you no one really fat um, channel, if you like, or |
|
| 13:26 | can split it up into a number channels, or sometimes also called lanes |
|
| 13:32 | it comes to, um, computer systems. There was also many thing |
|
| 13:39 | in the PC Express bus from talks planes or links or channels so that |
|
| 13:46 | is the trade off in terms off degree that is the number of inputs |
|
| 13:54 | outputs you create from they're all rapping , um, forwarding capability or a |
|
| 14:10 | . So talk a little bit about on the next slide. So here |
|
| 14:18 | very, somewhat simplistic. You are to figure out what the trade off |
|
| 14:25 | and how well trade off between sort few fat channels and many saying less |
|
| 14:35 | channels. And so the premise of line is that we have a network |
|
| 14:44 | and compute knows in this case, then you build an interconnection network using |
|
| 14:54 | on. Really, if you can a gentle crossbars, which then can |
|
| 15:03 | connect all the nodes than that would great. But that doesn't really work |
|
| 15:10 | large number of nose. So then need to form some kind off hierarchical |
|
| 15:18 | multi station network that I will talk in the next several slides. The |
|
| 15:25 | is that you have a switch, with okay um, inputs and K |
|
| 15:34 | also enormous heretics or the victory off switch. So the total bandits of |
|
| 15:42 | switch the Capital B, then gets into some language for channel that is |
|
| 15:51 | lower case B in this case. then the notion is that look has |
|
| 15:58 | off What I like. It was best worst case has such delay, |
|
| 16:05 | the premise to do this very simplistic is that you find out the maximum |
|
| 16:14 | or diameter on the networks. if messages need to go between notes |
|
| 16:20 | the furthest away respect to the next then it takes a number of Hobson |
|
| 16:27 | or links and switches, the message to go through in this case assumes |
|
| 16:32 | there's no congestions or don't worry about traffic from Just look at kind of |
|
| 16:40 | best worst case in the worst the maximum distance and the best aspect |
|
| 16:47 | there's no congestion, and another aspect that the network behaves as if it |
|
| 16:54 | circuits switch Woman is actually circuits switched not, but it means that just |
|
| 16:59 | of set up pathway between the two . And once the pathway is set |
|
| 17:06 | , then the payload just gets strained source to destination. So that's the |
|
| 17:13 | model for circuit switching. So when basically you get time for doing this |
|
| 17:22 | , that is proportion to the number hops or age in this K |
|
| 17:26 | links and switches traversed. And then assumed kind of action time to Savar |
|
| 17:34 | going through each Lincoln switch. And it's the time for the payload that |
|
| 17:40 | , l divided by the capability for one of it channels the lower trees |
|
| 17:49 | . And then, given this notion building sort of a hierarchical or multistage |
|
| 17:57 | , the depth of the network is than to the log on the fan |
|
| 18:02 | or degree on the switches. Thio in on this expression and they try |
|
| 18:08 | figure out what is, uh, K that minimize his best worst case |
|
| 18:19 | . And it is a function of band with per switch and the time |
|
| 18:24 | links, which a swell a societies the network and then the payload. |
|
| 18:31 | for a fixed Palin l. And fixed sort of network size than our |
|
| 18:42 | guess a za bandwidth growth or as product of the bandit and this |
|
| 18:49 | This horizontal access in the lower hand graft and shows that basically, as |
|
| 18:55 | a fixed network, um, payload the capabilities of the switch is |
|
| 19:00 | it's I am ratings of the degree . The switch that minimizes this quantity |
|
| 19:10 | been growing, and it's still So basically, as again, |
|
| 19:15 | So silicon has increased over time. degree or their family infant out of |
|
| 19:23 | on for minimizing this best worst case , uh, should have should be |
|
| 19:30 | . And it has been increasing, I believe is on the next |
|
| 19:36 | Yes, so that shows a little , you know, are things have |
|
| 19:40 | over time and this is again a bit old. But it chose it |
|
| 19:46 | in fact, has been the case the number of ports, if you |
|
| 19:50 | , of the degree and put out the switches, has been growing over |
|
| 19:55 | . And by now they're even potentially larger than 1 2018 putting out purports |
|
| 20:01 | order to get, um so the of the network of the maximum distance |
|
| 20:09 | the smaller so one doesn't. So tends to favor narrower and more channel |
|
| 20:19 | reduce the maximum distance in the network to using a deeper network in |
|
| 20:27 | channels. So that was kind of notion I wanted. Thio convey about |
|
| 20:38 | technology has been changing at capabilities has growing following what has happened on sick |
|
| 20:47 | on the processing silicon. It is same silicon being used to build |
|
| 20:53 | Um and then it tends to be the channel with so the capability per |
|
| 21:03 | has not improved us rapidly. Someone more. China's instead off uses more |
|
| 21:10 | rather than more capable channels. Now switch onto the cost model. |
|
| 21:27 | , all right, um, so the cost model and I'm talking about |
|
| 21:32 | very simplistic model, and it just you kind of the big old sense |
|
| 21:40 | the cost off building networks. The was actually proposed by I grabbed the |
|
| 21:50 | Charles license on, uh, also and melon eight years ago. And |
|
| 21:56 | waas made sense when this was made it essentially assumes kind of a plainer |
|
| 22:04 | to the uh huh space for implementing network. Obviously, many networks are |
|
| 22:12 | in normal three dimensional space, at when it comes to clusters. But |
|
| 22:18 | it comes to doing things, the piece of silicon plane on is |
|
| 22:24 | much still the case as well as good things on circuit board, |
|
| 22:29 | circle sports. Sometimes it's new. 2.5 day and circuit board is obviously |
|
| 22:35 | the, but it has a bunch layers. So but the quality of |
|
| 22:41 | aspect or what? The simple the sound sin. It's still valid |
|
| 22:47 | three spending 33 D space. So the model, that's it says here |
|
| 22:55 | Z unlike things up when you see lines and Andi things on power poles |
|
| 23:07 | the cities and landscape on wires on piece off circuit board and silicon or |
|
| 23:14 | , um, individually insulated. So basically make it murder so they can't |
|
| 23:24 | without crossing on different layers or run tracks. You know, different segments |
|
| 23:31 | causing shortcuts. So, um so is kind of the idea from this |
|
| 23:40 | that he assumed basically was known as Manhattan layout, that things are running |
|
| 23:49 | and vertically, and whenever there is cross point, then where that's where |
|
| 23:55 | can play some logic transistors of more powerful components. If it's on |
|
| 24:01 | circuit board, it would be some of a check for more macro oriented |
|
| 24:08 | than the transistor. So this is very simplistic model. And again, |
|
| 24:17 | , the vertical track can be used one more than one interconnect as long |
|
| 24:24 | there are different locations in the vertical . But they cannot overlap on the |
|
| 24:30 | segment of a vertical track because then creates too short. So that is |
|
| 24:36 | very simplistic model. I got some of interesting results. So the interesting |
|
| 24:48 | that should be easy to remember. that's using this notional by section |
|
| 24:57 | which is basically in a very simplistic . The number off connections wires, |
|
| 25:09 | that, if you cut them, network set Price Institute roughly equal |
|
| 25:18 | So that's a notional by section. the network, and you try to |
|
| 25:23 | out, in reality the cut that kind of the smallest cup to make |
|
| 25:35 | by section toe happen. So then ? It says that the area off |
|
| 25:40 | network then is proportional to the vice with square, so understanding something about |
|
| 25:49 | network topology on Despite section with, give to some notion of how expensive |
|
| 25:56 | network is to build because it tends be, as the first approximation custody |
|
| 26:04 | is more or less proportional to the . It's not the same thing for |
|
| 26:12 | circuit board. It's not just because the circuit board. It's largely dominated |
|
| 26:18 | the size of the circuit board and so much I want to put |
|
| 26:24 | So that's the one thing Thio want to try to remember in terms of |
|
| 26:31 | to the cost benefit. And this the cost side off doing networks, |
|
| 26:39 | , some other interesting part of this exercises that the time for doing certain |
|
| 26:48 | in particular to think about sorting. if you have number of compute knows |
|
| 26:56 | distribute the data recently evenly so either or compute notes number in, in |
|
| 27:04 | case on and sort of in It's on the worst case scenario when |
|
| 27:13 | want things sorted. Everything is kind in their own half of the networks |
|
| 27:17 | things needs to cross this by section on the network, so that means |
|
| 27:24 | time to do the computation then becomes to decides of the data set to |
|
| 27:31 | number of knows divided by the by . And then you got this very |
|
| 27:38 | relationship that this 80 squares is proportional the square off the size of the |
|
| 27:46 | of the process. So the interesting about that things as well. If |
|
| 27:54 | want something to be fast, that you want t to be small, |
|
| 28:01 | the 80 square is bounded from below end squared. So the fix problems |
|
| 28:09 | . If you try to reduce the , then the area is bound to |
|
| 28:15 | . Conversely, if they want a be small, um, the time |
|
| 28:22 | bound to increase. So that's kind a well known uh, often cited |
|
| 28:30 | on networks. That gives you some that there is this take off between |
|
| 28:36 | and size off networks, and the thing is a little bit, |
|
| 28:44 | that is related to him, Leighton , And it also gives some idea |
|
| 28:52 | the so the minimum maximum wire That's somewhere in the design or construction |
|
| 29:02 | your network that there will be a or cable whose length is proportional to |
|
| 29:09 | square root of the area divided by diameter off the network. Mhm. |
|
| 29:18 | home. Okay, so those are very simple things to remember that came |
|
| 29:25 | of this. I'll make a two model. It has been, |
|
| 29:33 | extended to doing things in free space the numbers. Keep changing a little |
|
| 29:38 | , but basically this very simple to model. It's a good sense for |
|
| 29:43 | come toe happening in the trade off time and performance or an area |
|
| 29:51 | the network now the length of the . They often think in terms all |
|
| 29:59 | stuff across wire as being one lower is obviously the time of flight or |
|
| 30:06 | of light for things going from And so the wire. But it's |
|
| 30:14 | and, um, see most If we look at things on |
|
| 30:21 | it's on. Sometimes. Also on circuit boards is I think I tried |
|
| 30:26 | point it up in one early In terms of the most technology, |
|
| 30:30 | a charge transfer technologies such just basically electrons around And yes, the time |
|
| 30:41 | get a single electron from point a point, please, the function of |
|
| 30:48 | speed of like, but that doesn't the states you need to get a |
|
| 30:53 | of them from one point and But even in that scenario, the |
|
| 30:59 | length, because such reflects resistance and wires. So this very length, |
|
| 31:06 | they won't use the charge transfer model the speed of light model is the |
|
| 31:10 | measure in terms of understanding, how latest it can be effective and |
|
| 31:20 | So you can. Either it then in terms of number of clock cycles |
|
| 31:25 | , if you want to have some design, is the length of the |
|
| 31:29 | cycle that gets determined by this. , violence is, I think that's |
|
| 31:38 | I had in mind for the cost . So very simple model. But |
|
| 31:44 | kind of gives an idea on trade between time and area, as well |
|
| 31:50 | some worst case type of latency or on clock cycles. Okay, I'll |
|
| 32:03 | to start to talk about that. apologies. And there's all kinds of |
|
| 32:10 | apologists and has been China are So I'll go a little bit slowly |
|
| 32:18 | this one because it's simple and see I can get you to participate a |
|
| 32:23 | bit. So this is a picture a fully interconnected network. Eso We |
|
| 32:30 | clearly say every point is connected to other point, so that means the |
|
| 32:36 | . I think it's easy to see there's nothing that is everything is |
|
| 32:42 | So that doesn't, um no. I want a volunteer. The number |
|
| 32:55 | family and fan ox. No How maney links to get to know |
|
| 33:17 | , the animals in the network writers be and minus one. And |
|
| 33:24 | So they told Manuel links on the and squared. Now, since that |
|
| 33:30 | section with is an important measure, the performance and cost. So if |
|
| 33:38 | split this network into two halves in case, four nodes in each or |
|
| 33:44 | over two notes in each half, many links do you need to |
|
| 34:01 | No volunteers. Well, each node has, and one is one connections |
|
| 34:17 | other notes. So if you kind do the by partake, graph is |
|
| 34:25 | end of the two nodes on one , and then of the two nodes |
|
| 34:28 | the other side, each on the song, so in the left side |
|
| 34:38 | to every note on the other So that means each one note has |
|
| 34:46 | , and of the two links to other half on their end of the |
|
| 34:52 | knows in each half. So basically en squared over four links that needs |
|
| 34:58 | be cut to make this eso that's by section with. And then he |
|
| 35:06 | , using this very simplistic to the that I mean, the area is |
|
| 35:12 | proportion to the number of those to fourth power. So that is becomes |
|
| 35:23 | expensive network to build for large Event for small, and it's not |
|
| 35:30 | to do. But at some point becomes for everything expensive, and I |
|
| 35:36 | also figure out what thio mean. very length this and it turns out |
|
| 35:40 | be in squared now just because I this is expensive to build. It |
|
| 35:48 | expensive to be in for large but for a modest number, notes |
|
| 35:51 | can be done Here's an example, a computer system that is still this |
|
| 35:59 | 30 by great computers is a few old by now, but to still |
|
| 36:03 | it in there. Current generation computer that they use fully interconnect among the |
|
| 36:13 | number of notes in their system, when they've been long systems, you |
|
| 36:20 | a number off this fully interconnected Some notes. We'll talk more. |
|
| 36:25 | they actually make the whole system But so it can be done and |
|
| 36:30 | is given. Currently Houston Systems. other extreme is just the linear, |
|
| 36:39 | notes and clearly, in this the by section with this very |
|
| 36:44 | So just cut one wire and or that's done somewhere sexually. The smalls |
|
| 36:49 | this case Yes, based on number links capture would get wonder where bond |
|
| 36:55 | just sort of one, but cleaner need also the host. All the |
|
| 36:59 | were basically it's border and area, it's very cheap in terms of |
|
| 37:05 | But in terms off by section with pretty poor should have means in terms |
|
| 37:11 | potential running between endpoints. Things needs go through. En hops are not |
|
| 37:17 | . Man is one, not just . So that is low bus sample |
|
| 37:24 | hampers some applications and, of function. Do the wrap around and |
|
| 37:30 | the ring. Um on. That change much. So here's examples. |
|
| 37:38 | bring networks has been used, silicon. So this are from I |
|
| 37:46 | all intel examples are the Syrian Also, that's a four honor |
|
| 37:55 | the nice landing that is used on set of the nose in Stanford, |
|
| 38:02 | . Not just that we've been using glass and on the lower right hand |
|
| 38:06 | on this land. It's Intel Sandy . That was an eight core chip |
|
| 38:14 | was introduced, I think, about . And so so they used ring |
|
| 38:21 | . They tried to use two rings interconnect the or call eight course. |
|
| 38:32 | yes, so but the rings that us a number off either compute nodes |
|
| 38:42 | connect or course in the case off on a piece of silicon, a |
|
| 38:48 | core count goes up. It's hard get the ring than with to be |
|
| 38:54 | to keep up when the need to send messages will treat data from So |
|
| 39:02 | cashes on other cause. So together a little bit better. And |
|
| 39:11 | next thing is to look at instead linear and connected use to the mesh |
|
| 39:18 | this case, the by section. this, we can be proven |
|
| 39:23 | One is just take precise perpendicular to of the access basically Um, and |
|
| 39:32 | diameter is to go between corners or it's not totally square. So in |
|
| 39:36 | case, resume their rectangular one. let's just go from one corner to |
|
| 39:41 | diagonally opposite corner, so it's basically and then a square root of the |
|
| 39:48 | of nodes in the network. The panel is very limited, so that's |
|
| 39:52 | good part by section with It's not bad, right, because it's more |
|
| 39:59 | less proportional to the square root of number of those if it's with the |
|
| 40:06 | and the area then is based in to the size of the network. |
|
| 40:11 | that's a good thing that, like linear interconnected, the area is proportion |
|
| 40:19 | the number of those such a do in the network. But, |
|
| 40:24 | and the fan out is just marginally of higher than in the linear, |
|
| 40:31 | connect was from 2 to 4. the network diameter is goes from proportionate |
|
| 40:37 | the number of notes or to being square root. So that's distance dime |
|
| 40:43 | goes down fairly quickly by going from day to two weeks, and they |
|
| 40:49 | back in time Severity. It's not And then I can figure that best |
|
| 40:54 | of doing things up and, of , functions wrapped around. And then |
|
| 40:58 | becomes the tourists until the So there something that Zimmerman old by now we |
|
| 41:08 | see system that was known as the Paragon and Delta until, as you |
|
| 41:19 | do, you know, is not as a kind of platform or computer |
|
| 41:26 | company. It's a component company, chips, CPUs and all kinds of |
|
| 41:32 | chips, but it doesn't produce. instance, clusters. However, infants |
|
| 41:39 | model is when they start to advance and measure waste the changes or how |
|
| 41:48 | chips are being used. They tend build reference systems or prototype to demonstrate |
|
| 41:54 | and buildings. And these two system and Paragon Waas, two generations that |
|
| 42:02 | built before the left, the markets the football by these from, |
|
| 42:10 | income. But then they stepped out the way and let IBM, |
|
| 42:16 | Dell and others compete for how to systems they don't want to compete |
|
| 42:21 | Area their customers anyway. So it's d mesh was used. So this |
|
| 42:29 | now again there was more than tens nose or in a single visit knows |
|
| 42:34 | is about 2000 notes. There's things were done actually, on this is |
|
| 42:42 | silicon again by in tow. Two these cases and one is for another |
|
| 42:47 | company at TVA. Uh, that still around that build the 64 processor |
|
| 42:55 | of silicon. But for and both these three cases what was implemented wa |
|
| 43:02 | mesh on the silicon. The Polaris was a research ship. So waas |
|
| 43:11 | SCC chip that intel. But there never a product. At the |
|
| 43:17 | though, is the product that punching and the two mesh was also used |
|
| 43:25 | the name nice landing ship. That Afghanistan putative. So this is again |
|
| 43:32 | the note count goes up, rings support effectively for many applications. The |
|
| 43:42 | , of course, that he even in a single die. That's so |
|
| 43:49 | medicals, of course. Go to the measures and then things gets. |
|
| 43:59 | these are not planers. All Want to look at this play normal |
|
| 44:06 | one need to try to figure out to lay it out in the plane |
|
| 44:12 | . That's what the kind of little here tried to show so. But |
|
| 44:18 | the diameter it's again the go between corners on the tube effects too |
|
| 44:25 | Assume for this crafts about 10 cents proportion to the Cuban group of the |
|
| 44:32 | of those not square, the family the fan out. They're still very |
|
| 44:37 | . That goes from you know, to six. It's fairly obvious, |
|
| 44:42 | for the 10 points. And there's the three links for every note that |
|
| 44:48 | unique now by section with in this now is basically looking at the plane |
|
| 45:02 | plain, then, basically, is square off the number notes and instruction |
|
| 45:12 | , assume is kind of cubic. you get especially mhm, not quite |
|
| 45:20 | to number old but disco square on tube route. So it's better than |
|
| 45:27 | yeah to the mesh because the to mesh waas square root around right for |
|
| 45:34 | mesh. So now it's yeah, 2.72 3rd instead of 0.5. So |
|
| 45:43 | section with So it has better capability stuff around, and but the area |
|
| 45:51 | no longer than proportion to the number nose. So now, both for |
|
| 45:56 | linear. Until the image when you it into space is proportionate to the |
|
| 46:01 | of notes. So this is a when you actually build things in three |
|
| 46:05 | , then you still have a chance get proportional to the number of notes |
|
| 46:09 | doesn't need to grow like in displaying layer. Oh, and so then |
|
| 46:17 | can also figure out planer layout with maximum. Why you like this? |
|
| 46:25 | here's on. Of course, the you got. That's all the the |
|
| 46:33 | , and some examples again, computers been built using, uh, not |
|
| 46:40 | three D forest networks, but so am built. This sequence are computer |
|
| 46:51 | known as the new gene sequence of . They were specifically designed to be |
|
| 46:58 | energy efficient. So this were the one design in terms of energy efficiency |
|
| 47:10 | , I think, at least five in terms of what you can buy |
|
| 47:14 | any vendors, not just from and it used, both known as |
|
| 47:19 | car PC chip, was a joint in green Motorola, an idea way |
|
| 47:29 | . So the first two generations off flu J in sequence off systems used |
|
| 47:37 | three D tourists network and there was them too young. Increase the number |
|
| 47:45 | notes that you can interconnect by more an order of magnitude compared to what |
|
| 47:52 | used in the Intel, Delta and Systems that again used the two |
|
| 48:02 | Now for the follow on system to LMP bluejeans system that was known as |
|
| 48:08 | G. Q. I am, fact, decided to use the five |
|
| 48:16 | tours Thio again. In this technology has improved. So again how |
|
| 48:23 | use the bandits. Use a higher for the nodes. Thio. Make |
|
| 48:29 | that the maximum distance in very large systems, uh, was better than |
|
| 48:35 | using a three d next. Another aspect that I mentioned briefly at some |
|
| 48:45 | in some class classes that some of clusters they have more than one networking |
|
| 48:53 | then. Most of them are at two networks, and on comes to |
|
| 48:59 | Blue Jean system. It, in , three networks. So they have |
|
| 49:04 | fight day tourists that is used for data communication to send data between notes |
|
| 49:13 | the system. Then they have another first there is known as the broadcast |
|
| 49:22 | or combining network that In fact, a form of tree structure that was |
|
| 49:34 | for synchronizing notes and necessary to be to do reduction effectively. It did |
|
| 49:41 | use the fire day tours, and there is yet another network that is |
|
| 49:50 | in most computer systems in that's and of control networks that is also used |
|
| 49:57 | this systems. Unfortunately, the looting computers Waas abandons. I think the |
|
| 50:06 | year that was produced was probably built 2016. I didn't find exactly when |
|
| 50:13 | last system was produced. There's still of them around that there that you |
|
| 50:18 | use. And here's, I a little bit. Anyone interested in |
|
| 50:28 | out how you actually build this systems a larger number of notes can take |
|
| 50:36 | look at this slide and unwanted. have been too, too much, |
|
| 50:42 | the large system they lived was known this acquire system. That alone is |
|
| 50:48 | National Labs had 96 tracks on I they love to play out the |
|
| 50:57 | of notes, but I guess it , I guess, uh, and |
|
| 51:06 | can multiply artist, too. In lower right time graph in the corners |
|
| 51:14 | 96 Greatest configures 12 the roles of , each roll containing eight tracks and |
|
| 51:23 | but all that you can see the of those actually being used in the |
|
| 51:29 | . Um, the coloring tried to how the fighting tours is wired to |
|
| 51:36 | . And so some of the wiring , in fact, on the circuit |
|
| 51:41 | implementing nodes. And then there are things that are traveling between circuit bold |
|
| 51:46 | inside racks and then between reps. , um, and then the extreme |
|
| 51:59 | from 1 to 2 d to three to fight the extreme and to doing |
|
| 52:06 | known as binary measure and cubes for words. Basically on the two knows |
|
| 52:15 | each dimension. And so that's And as a grown a number of |
|
| 52:21 | , you go the number of So what's good about this kind of |
|
| 52:29 | is the following that the diameter than logarithmic in the number of notes. |
|
| 52:36 | it z certainly better than if you there even three or five. The |
|
| 52:44 | um, now that means the degree each note is local, ethnic, |
|
| 52:50 | the number of else as you can of infer from the sequence off images |
|
| 52:58 | left to right. That's nine. way you construct this by narrative, |
|
| 53:04 | kind of detective off like Side Cube connect correspondent notes. So every time |
|
| 53:12 | number of those doubles you get one link for now. So it has |
|
| 53:18 | very nice by section, with that proportion to the number of notes that's |
|
| 53:22 | capable off bra things. Messages for . Too much contention. But it's |
|
| 53:30 | expensive so soon the area now because and square number of notes. So |
|
| 53:40 | it has been used in notes and on off the series. Another |
|
| 53:48 | They have a picture. I have these things, and now there's are |
|
| 53:52 | off Binary Cube connect the system that been built over time. The first |
|
| 54:00 | , uh, has kind of been as a little bit historic, and |
|
| 54:05 | will find it had the name of cosmic Cuba was built. That's Caltech |
|
| 54:12 | the two fellow since Geoffrey Fox and on the left on this picture of |
|
| 54:16 | two fellows in the upper left hand and chuck sites that is the developed |
|
| 54:22 | this picture. There were both air contact on and Geoffrey Fox is |
|
| 54:30 | longer can take it is uh oh University and has written all on the |
|
| 54:39 | and is by training is Trees But it's gonna really become a computer |
|
| 54:47 | . Jack Science, and it's a scientist. And he founded one on |
|
| 54:55 | networks, Switch Technologies and is also advisor all Bill Dolly, whose name |
|
| 55:01 | may have seen on some signs that and build on. It has been |
|
| 55:05 | professor at MIT and Stanford and this I think, BP for research and |
|
| 55:13 | 10. NVIDIA. I'll talk more that later. And then there's a |
|
| 55:22 | of other examples. One is known the End Cube. That's a company |
|
| 55:27 | is not no longer around. Neither the company that put the connection machine |
|
| 55:35 | on cue. Waas. When it up on hard time, it waas |
|
| 55:43 | by Larry Ellison, the founder off . So they used it for a |
|
| 55:51 | on I wanted someone beers and, , the system on the left is |
|
| 55:58 | as a connection machine system. That's company I used to work for before |
|
| 56:02 | to you, which thank you missions these systems used binary tubes or any |
|
| 56:13 | to connect for their systems. And the way, the connection machine material |
|
| 56:23 | 64 que notes for 65 536 That is still very high compared to |
|
| 56:34 | process. The chance eso any questions that before I move on? |
|
| 56:47 | the next thing is a little bit of for, perhaps that was interested |
|
| 56:54 | theoretical aspect of computer science. It's interesting network that in itself hasn't been |
|
| 57:03 | that much produced, um, indirectly . Many of the networks have talked |
|
| 57:11 | for the rest of this lecture, but here's three kind of network it |
|
| 57:17 | services, stillness, shuffle exchange So the Y one construct these things |
|
| 57:23 | through a number of so called They're just in a number of exchange |
|
| 57:28 | and the way from construct this network Bye, basically taking an old address |
|
| 57:42 | then you do the sequence of cycle quotations off the note address and we |
|
| 57:48 | the new address and the set of that you get pointed in this |
|
| 57:54 | The twists on the address are connected this so called truffle edges. So |
|
| 58:01 | are the black edges and this scratch the exchange edges other one you get |
|
| 58:07 | flipping really significant bit in the So that's the kind of simple way |
|
| 58:12 | constructing this network and the nice part it. It's just a very small |
|
| 58:21 | . It has a very small lee by section with, and it also |
|
| 58:28 | . And that compared to, for , the binary cube that also has |
|
| 58:34 | diameter is log s Oh, this requires a lot less area because it's |
|
| 58:40 | the end square this and squared of love squared. Um, but of |
|
| 58:46 | , and the by section, which not quite as good eso it's kind |
|
| 58:52 | off by the longer it in But it's a reasonable trader for many |
|
| 58:58 | . And so Okay, so I then move on to the next |
|
| 59:05 | So there is, unfortunately what is . If you look at this slide |
|
| 59:10 | the next one there is not the , um, modularity, if you |
|
| 59:18 | in this case. So, when you increase the network size, |
|
| 59:24 | needs to be rewired. There's no structure that there can be reused and |
|
| 59:29 | obviously have prevented it from being used building Dark Skins networks. But |
|
| 59:41 | so this is something that was part the thesis for some of them on |
|
| 59:49 | Tom Leighton that in has written very . Um, I claimed and used |
|
| 59:56 | in terms of carol algorithms. He's the founder off. How come I |
|
| 60:04 | that some of you may have heard in terms off network cashing the And |
|
| 60:10 | is yet another one. Um, so the point of this thing, |
|
| 60:15 | turns out that this networks, can very effectively emulate a large number |
|
| 60:24 | the networks. That means if you're pattern in your application is kind of |
|
| 60:31 | like or some other kind off as we talked about in terms of |
|
| 60:40 | partitioning of data structure and interactions than court called Slowdown or the contention by |
|
| 60:50 | this type of interconnect is relatively But so this is why a deserved |
|
| 60:59 | computer science theoretical aspect. It is interesting network that I wanted you to |
|
| 61:05 | aware off, has played a role the evolution of network designs, but |
|
| 61:11 | more powerful networks. Not that I get to next. So trees are |
|
| 61:20 | very nice evening and easy, type of network to construct is a |
|
| 61:27 | binary tree on. You can have in each one of the notes of |
|
| 61:32 | binary trees, or one might considering using the leaves for as points where |
|
| 61:43 | notes are connected and rest of the being basically switch structure. So I |
|
| 61:58 | e. I guess you don't family , so the dire manner, hopefully |
|
| 62:05 | clear. Right? That's two terms basically the height of the tree, |
|
| 62:12 | . You need to go potential from left note on the a leaf, |
|
| 62:16 | on the left side off the road relief, not on the right side |
|
| 62:19 | the route. And then you have go from the left to the root |
|
| 62:23 | from the route back to leave. this twice the height roughly on the |
|
| 62:29 | . Mhm fan in the fan out very good in the binary tree |
|
| 62:34 | um, except for the root and notes, the degree is three. |
|
| 62:39 | of the size of the three year , the number of links is proportional |
|
| 62:44 | the number of notes is very The bad part comes to this, |
|
| 62:51 | there's only, you know, you at their own. Then if you |
|
| 62:55 | take away one of the links to rule done, the things get split |
|
| 62:59 | two half. So that means the section with this quite poor. So |
|
| 63:05 | why people that don't like trees interconnection intend to call it hierarchy or |
|
| 63:15 | So, um, in the area always the United States can get the |
|
| 63:21 | proportion of the number of notes. yes, compared to the linear interconnector |
|
| 63:27 | that we talked about before area and section is proposing is similar, but |
|
| 63:33 | diameter is logarithmic instead of proportionate to number of notes. So if you |
|
| 63:37 | to compare it to something a similar and by section with organizing things for |
|
| 63:44 | complete Pinetree certainly beats bring in to . Um, then if you try |
|
| 63:55 | lay it out, as you kind infer from this cartoonish picture is, |
|
| 64:00 | , some of the links there ends being long, which is not true |
|
| 64:05 | a linear interconnect. So you kind lose. But you don't lose too |
|
| 64:10 | military on this account. No. huh. when I was a |
|
| 64:16 | They also lived in addition to the . You will also did something called |
|
| 64:21 | Factory Machine on People are Columbia Also the violence system using please for |
|
| 64:31 | Internet. The next set. Those is kind of important to try to |
|
| 64:39 | out how you improve planetary into connect be and interconnection network. That is |
|
| 64:51 | hardly used today, and it's still off dominating on networks and Smith. |
|
| 65:00 | the next few studies I'll go through and trying to give you the essence |
|
| 65:07 | door backs and highly fix the problems binary trees to get them to be |
|
| 65:14 | versatile and desirable network. So, I said, one thing is |
|
| 65:23 | I assume, nuts. The leaf are actually representing the compute notes, |
|
| 65:29 | the other notes are representing the interconnection structure. Now, if that is |
|
| 65:39 | case, then and it's reasonable to about that, the notes, the |
|
| 65:46 | notes are actually laid out or connected the edge of some network area. |
|
| 65:59 | So this is, I guess, first thing if, um if you |
|
| 66:06 | them for force them to be on boundary than you are limited in terms |
|
| 66:19 | the area to being and long, I'll show that on the next |
|
| 66:24 | But if you relax the, treat them or hard replace the notes |
|
| 66:29 | you can do as it said in previous slide, you can get something |
|
| 66:34 | is proportional to the number of those and depending upon how you do the |
|
| 66:41 | you get, uh, correspondent or on the violin. So u s |
|
| 66:46 | of an illustration of what happens in of both violence and the area. |
|
| 66:52 | here's kind of a linear or not they you can fold it to be |
|
| 67:02 | like the square instead of this highly , but it doesn't really change the |
|
| 67:07 | outcome. So this is just trying illustrate how the principle of what happens |
|
| 67:15 | you forced relief notes to be on edge of an area. So in |
|
| 67:20 | case, I'm going to see that your double the number of notes, |
|
| 67:27 | , the height in the first Uh, it is whatever it waas |
|
| 67:31 | half the number of nose. Plus end up increasing the height by one |
|
| 67:36 | connect the two halves So that means height cross logarithmic e with the number |
|
| 67:43 | notes. Now we have the with up then obviously is also doubles plus |
|
| 67:52 | on the channels um, separate for new sort of interconnector the root off |
|
| 67:59 | new tree. So then you get winds and you get the height Sounds |
|
| 68:04 | that the area now And it can proven to that this is in |
|
| 68:10 | the optimum. And so even if allow more squares layup, it doesn't |
|
| 68:16 | . Yeah, kind of absent topic behavior. Now, on the other |
|
| 68:22 | , if you allow nodes to be and they were in the plane, |
|
| 68:28 | can use this so called h tree when you can kind of see these |
|
| 68:33 | and how the binary tree is laid . If you do this or allow |
|
| 68:40 | form or placing notes and the then you can actually show that it |
|
| 68:49 | area optimal. Andi, this is that The rickerson works easily. If |
|
| 68:58 | sort of quadruple the notes in each to you, double the notes notes |
|
| 69:03 | horizontally and vertically, and then you get sort of one more for every |
|
| 69:11 | of the number of notes. So things grows the linear dimension, respect |
|
| 69:17 | the square root. So that brings number of now the area is actually |
|
| 69:22 | to the number of moves. Then also trickery and trying to figure out |
|
| 69:28 | to make it, um, by , optimal. So these are known |
|
| 69:35 | a street layout that has been quite known on it forms, in |
|
| 69:43 | the basis for what's known as So fat, please. It's more |
|
| 69:52 | real trees except computer scientists, so them upside down. So normal trees |
|
| 69:59 | have root at the bottom and leaves the top kind off, but normal |
|
| 70:04 | that have a fat drunk. And you approach is the leaves, things |
|
| 70:08 | senior and thinner. So that is simple analogy, I guess was real |
|
| 70:15 | in terms of factories. So and particular factory, then I'm wrong. |
|
| 70:24 | can see that as you move from leaves towards the root. The number |
|
| 70:30 | links Aziz you move towards the root for every layer off the graph. |
|
| 70:34 | effectively, um, if you look the four leaf notes and the left |
|
| 70:44 | say on this subject. It's kind as if each Leachman had its dedicated |
|
| 70:51 | . So the route. So it's good and resolving contention. So it's |
|
| 70:57 | longer this hierarchical bottlenecks. So it's . But, you know, really |
|
| 71:04 | , they have the big trunk tech , um, transport the nutrients without |
|
| 71:11 | much contentions. Beliefs. So this the factory, and here is kind |
|
| 71:18 | hard one year actually construct what's known the four are factory where you can |
|
| 71:24 | kind off this for input on for for each layers in this particular switch |
|
| 71:35 | . So that seems kind of esoteric complex. And now you can actually |
|
| 71:40 | this history. They often built area wire length optimal factories. So this |
|
| 71:50 | kind of a major advance that was Hello. Innovated by Charles License and |
|
| 71:58 | students charge Slices on is a prophet in case you didn't know and the |
|
| 72:05 | of many awards. So this factory waas first used and this computer system |
|
| 72:18 | as the connection machine number five on model number five it was not a |
|
| 72:26 | unquote full factory. It was then little bit on in the sense that |
|
| 72:33 | section with was a quarter of the of nationals and not equal to the |
|
| 72:37 | of these notes. And this was built already 91. And just for |
|
| 72:48 | , including this thing. And I'm probably everyone knows about the movie Jurassic |
|
| 72:59 | . And in fact, they used systems to do the movie. |
|
| 73:10 | um, now here's a just a bit more detail or hardest thinking on |
|
| 73:16 | factory was done now here. So other vendors than also picked up on |
|
| 73:23 | this factories. This is in a from Silicon Graphics that it's no longer |
|
| 73:28 | it. Silicon Graphics was acquired by the tackle a few years back. |
|
| 73:35 | is an example. How did how did their factory? There's another picture |
|
| 73:40 | how they did factories again from Silicon Inc There's other systems. IBM used |
|
| 73:45 | factories, um, more than a later, for also largest can systems |
|
| 73:52 | to the system for liver Lawrence Livermore Labs, Onda. Since producing stamp |
|
| 73:59 | to Central, do you also use into connection and notes, and even |
|
| 74:05 | most recent system there from terror? is also using factories, so even |
|
| 74:13 | , 30 years later, after this First Factory was used in a computer |
|
| 74:20 | , it's still used for large scale because of its very good trade off |
|
| 74:26 | between by section with that folks um, and AR and cost in |
|
| 74:32 | the network. And as it says on this slide, it is a |
|
| 74:44 | of network that is known as a network, but theoreticians and computer science |
|
| 74:49 | means Universal Network is a network that emulate or assimilate any other network with |
|
| 75:00 | a lot of ethnic slowdown hopes. , so I will stop there for |
|
| 75:08 | and on this, and we'll wrap network next lecture. Um, take |
|
| 75:13 | questions in a few minutes. That So I guess the bottom line is |
|
| 75:25 | no camp has grown in some a degree on the network has grown |
|
| 75:33 | it comes to mention to connect of simple, there goes from one D |
|
| 75:38 | rings, too measures and tourists on , or you're in Binary Cube for |
|
| 75:46 | the kind of extreme high degree network terms of trade offs between by section |
|
| 75:51 | and cost and diameter, and try make something that is even better than |
|
| 76:01 | trees and formal and form of factories become the norm. Noticed it |
|
| 76:08 | It's not the only network, but than a network most vendors used to |
|
| 76:14 | large train systems and for interconnect on today, measures are a kind of |
|
| 76:25 | needed for high core concepts. And next time I'll talk briefly that most |
|
| 76:41 | as multi station and work and tell a little bit about some of the |
|
| 76:46 | ones, as well as on other that is used by one of the |
|
| 76:54 | large scale cluster vendors. Create computers there's much NHP company now and what's |
|
| 77:02 | as well, I can Fly network was invented by Build Ali, whose |
|
| 77:07 | I mentioned Wow before it was a to train. Okay, I'll stop |
|
| 77:29 | recording for the |
|
