© Distribution of this video is restricted by its owner
Transcript ×
Auto highlight
Font-size
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

-
+