| 00:00 | Uh huh. Okay, yes. that composition is it says here |
|
| 00:07 | So the idea is basically for clusters you use the collection of notice solve |
|
| 00:15 | problem. So that means using this compute role, where most of the |
|
| 00:24 | associated with data is done on the where the recites and there is a |
|
| 00:30 | amount off data that may be needed the computation locally, that is elsewhere |
|
| 00:38 | the system. So this is basically of today how you than distribute or |
|
| 00:50 | what goes swear. And then another is, where does it go, |
|
| 00:56 | ? So it is kind off. methods has been out there that I |
|
| 01:01 | talk about today and yeah, I not even managed to get to the |
|
| 01:06 | of the list today. And then will continue with a few more |
|
| 01:10 | Um, next time so I'll start giving a bit of examples. And |
|
| 01:18 | mostly coming from ah, sign and application because that's sitting again. That |
|
| 01:26 | the whole process in terms off both clusters. Andi the type of problems |
|
| 01:33 | from them had today there is in larger type, problems done in relation |
|
| 01:43 | social networks that are not engineering type , as well as many other type |
|
| 01:51 | Internet computing type problems that I was to mention and talk a little bit |
|
| 01:59 | next time. Today, it's more less following the evolution of how this |
|
| 02:06 | structure petitioning mhm has been the methods they have pin interrupt. So it's |
|
| 02:16 | goals is one way to get a balance in some form, and that's |
|
| 02:26 | points out on the slides. There's two aspect is one is memory |
|
| 02:31 | So yeah, ideas get roughly about same amount of data on each one |
|
| 02:38 | the notes in a computing system and then hopefully balance the computation effort on |
|
| 02:50 | notes in the system. Now it's all, um, subsets off the |
|
| 03:03 | structures or parts of the data structure not necessarily require the same amount of |
|
| 03:08 | . So just because you, perhaps some measure use about the same |
|
| 03:14 | uh, parts of the data structure the different notes does not mean that |
|
| 03:20 | computation balance is good. So for the different methods, they account |
|
| 03:31 | this difference in terms off memory as as the complications associated with the parts |
|
| 03:37 | the data structure that is allocated you know. And while that in |
|
| 03:44 | is not easy, it's kind of when I can acknowledge the data communication |
|
| 03:50 | between the different notes and the clusters , and for that communication part one |
|
| 03:59 | to minimize the bandwidth, our best them out of data that needs to |
|
| 04:05 | communicated on. There are many different off that to where they want minimizes |
|
| 04:12 | worst case or the average case. in terms of the notes, what |
|
| 04:19 | require in terms of the communication. another part is the number of messages |
|
| 04:25 | you may need to send. And another one is the Leighton See in |
|
| 04:32 | among notes. Well, for some these aspects, it may be independent |
|
| 04:39 | the interconnection networks reduced between the In other cases, it's not so |
|
| 04:44 | that case, you know the interconnection properties needs to the accounted for when |
|
| 04:52 | comes to communication costs, including rounding sizes in the network, because that |
|
| 04:59 | the contention as well as potentially See um, so that's why this |
|
| 05:08 | and then be complete problems that's hard what is being used is all kinds |
|
| 05:14 | . Different jurist ICS and I were about the few of them, |
|
| 05:19 | and today and next time on Melissa's . So the normal uses that one |
|
| 05:27 | a Zeman E petitions as one as in the system. But it's not |
|
| 05:32 | the this case. Obviously, you like to have at least as many |
|
| 05:38 | or every note gets used in what using. But it's also a they |
|
| 05:45 | to do some over, petitioning the you generate more petitions than you have |
|
| 05:52 | that can sometimes improves a little and you can also use it, |
|
| 05:59 | zit says. On this slide, kind of try to generate petition that |
|
| 06:05 | , in a sense, a memory in each one of the notes. |
|
| 06:13 | . And that's what a little what we've done when we talked about |
|
| 06:18 | nation process in trying to do. that case, it was very simplistic |
|
| 06:23 | using loop, petitioning and blocking or of in a loop versus data that |
|
| 06:31 | in the various levels of the So here's no use to wrap it |
|
| 06:39 | through some of the things people. to give you an idea there scientific |
|
| 06:44 | engineering applications. This was something that the convictions on the magma inside our |
|
| 06:54 | . Here's another one as people similar flares and try to figure out this |
|
| 07:00 | happens in the sun in terms of shooting out, and it takes a |
|
| 07:05 | amount of um So these methods, , they use partitioning off the space |
|
| 07:15 | smaller and kind of cells. that maybe not so familiar to computer |
|
| 07:22 | . But if you work but somebody computational science, you know that there |
|
| 07:29 | networks like final government or finite volume being used to partition the three D |
|
| 07:35 | into small volumes. Uh, here's things in terms again computational fluid dynamics |
|
| 07:45 | , uh, may also some construction in terms off figuring out stresses on |
|
| 07:54 | . This is his image is more electro Magnetics. What happens when, |
|
| 08:00 | construction, airplane and you, the both of the space around the |
|
| 08:06 | as well as figuring out how to the body of the aircraft itself from |
|
| 08:12 | currency's induces in the body on the on here is one with the structural |
|
| 08:18 | again, submarines or some other mechanical and the different colors. Then tried |
|
| 08:25 | illustrate the partitions that may be in . So green may be assigned to |
|
| 08:30 | note and read to another node. wish to get another notice. |
|
| 08:36 | come off. There are other systems anyone does electrodynamics of biochemistry, where |
|
| 08:42 | have atoms and molecules that interact through forces on you try to figure |
|
| 08:51 | are things potentially move in fluid in or some other kind of solvent and |
|
| 08:59 | is hardly relevant. And these times Kobe, Uh, and there is |
|
| 09:05 | of more things that modeling in terms being prosthetics and, uh, medical |
|
| 09:13 | , I guess, um or are in this kind of crew scheduling in |
|
| 09:18 | ? So justice is a big Well, it's not the big |
|
| 09:22 | but a set of examples from most and science applications. But here's this |
|
| 09:30 | is kind of the logistics problems are planes and crews in the right place |
|
| 09:35 | the right time. So in some , the problem of the data structure |
|
| 09:43 | this purpose is typically than modeled by kind of a graph. Wow, |
|
| 09:50 | of the graph. This representing computation edges in the graph, represents interaction |
|
| 09:59 | notes. Mhm uh, on. think that's pretty much what this science |
|
| 10:06 | . Uh, so it's a What examples by text, one of |
|
| 10:12 | early ones for using this type of methods who are all right, both |
|
| 10:22 | Princess Circuit Board designs for putting components on a circuit board, as well |
|
| 10:29 | then running the singles on the person board to the various components on the |
|
| 10:37 | . So this is a computational, hard problem, and increasingly, that's |
|
| 10:44 | very much used also for during chip , because it's placement and routing is |
|
| 10:49 | big problem. The other ones, think, cover dimensions. Um, |
|
| 10:58 | it says quality is affected performance, that is the architecture dependence that |
|
| 11:09 | um, the other aspect of the partition that is good to keep in |
|
| 11:13 | that effects how What type of methods like to use is whether the data |
|
| 11:22 | is static or if it's dynamics or keep changing. So if you have |
|
| 11:31 | kind of a so or even in molecular things that were more smaller molecules |
|
| 11:38 | around and you try to figure out part then, um, Humanae Thio |
|
| 11:46 | the data structure and also in mechanical . You may. It's natural, |
|
| 11:53 | guess, to think of it part the fairly static structure on that may |
|
| 11:59 | the case in many situations, but of the things that is being done |
|
| 12:05 | , for instance, the automotive industry simulation of car crashes. Onda, |
|
| 12:11 | you can imagine, there car looks different in the process of it crashed |
|
| 12:18 | being your normal cart or something that totally different. And that is very |
|
| 12:25 | problem, in fact, to not the dynamic part but actually how to |
|
| 12:29 | with things from Trump. So that kind of a very quick illustration off |
|
| 12:40 | where graph partitioning off fairly large paragraphs important. So and some of these |
|
| 12:54 | you have tens of millions, or possibly even up to billions on nose |
|
| 13:01 | your graph. Andi, an even number of edges most of the |
|
| 13:10 | So so it and they questions on general background. I will soon start |
|
| 13:17 | talk about these particular methods, how work. We'll stop for a second |
|
| 13:23 | terms of the motivational part. All , so I think to keep in |
|
| 13:34 | that's for all of these methods that will talk about again are effectively graph |
|
| 13:45 | problems. Hm? How you then from your application to model that this |
|
| 13:52 | is fairly application dependent, as a . But the general, like the |
|
| 13:58 | that notes represent computing and edges, data interaction. And, uh, |
|
| 14:09 | is so because it's an important problem a lot of things are problem |
|
| 14:15 | So there's no way so far, is so that they catch all method |
|
| 14:23 | works great in all cases. So a good toe. Have an understanding |
|
| 14:30 | a range of different methods. That won't You won't get an assignment |
|
| 14:35 | doing petitioning. So this is Mawr for life after class or potentially, |
|
| 14:42 | somebody wants to do the project on data petitioning methods, our approach is |
|
| 14:53 | I will cover most of these methods , so I won't talk more about |
|
| 14:59 | on this particular slide. Um, it is just the first the concept |
|
| 15:06 | this craft petitioning where you have the collection of notes and eh? Just |
|
| 15:15 | I mentioned. Not everything is equal all applications. So that's why one |
|
| 15:21 | needs also assign the weight to each of the edges that is reflective off |
|
| 15:30 | amount of data or the communication that thio take place between the nodes at |
|
| 15:37 | end points of an edge. And also mentioned that you know, each |
|
| 15:44 | may not the Korean equal amount that . And that's why there's also in |
|
| 15:51 | and wait just associated with each one the notes to reflect their work associated |
|
| 15:57 | that note. So, um, there they are is basically than Thio |
|
| 16:08 | . There's no So you get the so you get a number off petitions |
|
| 16:13 | least equal to the number off. knows that one has in, in |
|
| 16:19 | custom, the target cluster. I think that's pretty much what this |
|
| 16:26 | says. So here is kind of example there now, a particular partitioning |
|
| 16:32 | was made where knows our group. in this case that I'm being four |
|
| 16:39 | . Andi, um, with the that the nose in the box and |
|
| 16:44 | the partition on them, I can of get the aggregate weight off the |
|
| 16:50 | between the petition based on the number edges and their way that goes between |
|
| 16:56 | petitions. This basically says that, , this is a complication, A |
|
| 17:03 | hard problem because it grows exponentially in number off. Um, no such |
|
| 17:09 | heaven address. So now this is some of the notion off separators that |
|
| 17:25 | , when you want to petition the , it's is that one needs |
|
| 17:32 | That's the slice. The graph somehow two or more parts than one can |
|
| 17:37 | trick coercively as my section. Or can do this. What that thing |
|
| 17:42 | on an earlier slide. Uh, okay, way. So you generate |
|
| 17:47 | partitions in one step, per supposed generate them over a number of by |
|
| 17:54 | steps now and during the partition of graph, one can either select a |
|
| 18:05 | of nodes on that. If you those notes from the graph, it |
|
| 18:11 | apart in two or more parts. in this case, the red virtus |
|
| 18:16 | here are kind of example off. separator overtake separator that remove the red |
|
| 18:25 | stand. You get to separate one on the left and one on |
|
| 18:32 | right of black notes from the night craft. Others. There's also age |
|
| 18:40 | that basically means that different. They , they set of edges. I |
|
| 18:45 | got two different petitions or more. in this case, both the green |
|
| 18:53 | the blue I just is colored by represent an edge separators on this case |
|
| 19:01 | to hedge separators illustrated. Those are no means the only ones. But |
|
| 19:06 | to illustrate the concept off No than separators. And then there are some |
|
| 19:13 | in terms. Off size is basically terms of size and notes separated relative |
|
| 19:21 | . And there's, um, you , properties off those separators that are |
|
| 19:28 | good to know that at least that where starter works, we'll decide toe |
|
| 19:32 | with notes and separators that that's kind a small except then for at least |
|
| 19:39 | bigger than the edge separator. And also some bound on the edge separator |
|
| 19:45 | to the north separator. There's a famous result that I will talk |
|
| 19:54 | Maybe it comes later. Sorry if has, uh, and and there's |
|
| 20:01 | lift on chargin separated Terram that I it is in their slides or I |
|
| 20:07 | remember the sequence on top of my that there was one of the early |
|
| 20:12 | that waas derived. Actually, four printed circuit board or really side design |
|
| 20:20 | design purposes that shows if you have plane or graph. What can I |
|
| 20:26 | that exists? Balance for has small separator has to be such a lower |
|
| 20:35 | . And of course, that's something would like to try to get close |
|
| 20:38 | you and designing a good petitioning Then there Early results system being not |
|
| 20:50 | improved. But it has been extended all kinds of different, uh, |
|
| 20:58 | in terms of the craft properties and different measures. And on the property |
|
| 21:04 | the graph, that may not be . So, um, any questions |
|
| 21:14 | far before I dive into specific Okay, coordinated by section is, |
|
| 21:32 | , I said we'll see. hopefully something that feels intuitive, and |
|
| 21:38 | very simple. Method on a mere just fine may not need any more |
|
| 21:44 | method, but it doesn't always work well. So that's fine. There |
|
| 21:48 | a whole host of other methods. right, so here is now what |
|
| 21:53 | coordinate perception does so in this in the context of a three dimensional |
|
| 21:59 | . So the way it works is that, uh, again, this |
|
| 22:03 | based on the graph. So your coordinates So the corners for the nodes |
|
| 22:09 | then you can sort them respect to one of these coordinate actions X, |
|
| 22:14 | and Z in this case. And you find in the sort of water |
|
| 22:21 | medium point or media note along that orbits. Behalf of the nose has |
|
| 22:29 | smaller X value, and half of has a larger X value. So |
|
| 22:36 | you can figure out them if you This is a no separator, |
|
| 22:43 | Uh huh. Many edges does gets , so to speak or removed from |
|
| 22:52 | graph. No, I didn't say explicitly, but the point if you |
|
| 22:57 | this measure picture with the green and . Um, and just those ages |
|
| 23:04 | the communication. Then that means to place between the two parts of the |
|
| 23:11 | . So so what? This algorithm basically look in the x y and |
|
| 23:16 | direction. It does this exercise for one of the independently and then it |
|
| 23:23 | the one direction. X violence. which one of the coordinates Directions should |
|
| 23:31 | the first cut. That is the that then minimize the number of edges |
|
| 23:38 | the communication for that. And then proceeds to take the other two directions |
|
| 23:44 | the first. Now you have two and Dan countries each of these two |
|
| 23:51 | independently and tried, but well, , predominantly one do not continue or |
|
| 24:00 | the direction that was just bisected. take the other two and figure out |
|
| 24:06 | one is the best. And then the third one And then we try |
|
| 24:11 | get enough petitions, but through there direction. So here is kind of |
|
| 24:19 | a little bit of illustration. Where ? Some of the the shades of |
|
| 24:23 | represents it the kind of density off . And this is just the two |
|
| 24:30 | illustrations on this case. This red kind of presumably because the number of |
|
| 24:39 | on the left hand side and the hand side to be about the |
|
| 24:43 | And, um, this compared to y axis this waas apparently, |
|
| 24:52 | Cut That generates fewer. It just down cutting it. We respect their |
|
| 25:00 | access. So then the next time , Wanda's separately for the two |
|
| 25:07 | and she was this kind, the dimension for expecting things into two |
|
| 25:15 | And I'm gonna keep going and generate and more partitions. So this is |
|
| 25:22 | . Um, so focus obviously depends the problem contacts. And then this |
|
| 25:27 | , it was we got sort of partitioning what was done because of the |
|
| 25:32 | of the area. But for every that we apply this technique to is |
|
| 25:37 | up to us to determine the mapping the problem domain to some sort of |
|
| 25:43 | interpretation so that we can apply Yes, there will be a fan |
|
| 25:48 | . So this type of coordinate per . So I will talk about methods |
|
| 25:56 | do not require coordinates in a So for many, engineering, if |
|
| 26:01 | have a physical domain that you are and this examples I mentioned earlier |
|
| 26:07 | um, you know this I think mentioned it to the solar jet figure |
|
| 26:13 | the physical demand gets partitioned into small . Typically find it volume will find |
|
| 26:20 | elements as they're called and then because have a geometry to start with against |
|
| 26:27 | . You have coordinates for each one the elements, and then it's fairly |
|
| 26:32 | to use this method. If you something that is more just the relationship |
|
| 26:37 | , for there is basically topology, would call it more than geometry. |
|
| 26:42 | it may not be obvious how you use this kind of a method and |
|
| 26:46 | to force it geometry on it, there's no natural reasons for it to |
|
| 26:52 | . Process. So this is kind a reflection off. A lot of |
|
| 27:00 | things started out that a lot of came from engineering problems or science problems |
|
| 27:06 | one had the geometry mhm, There's a little bit of example that's |
|
| 27:12 | that, Yeah, this kind of , but it doesn't always work that |
|
| 27:18 | on, so I can use things one doesn't try to divide things |
|
| 27:24 | and sometimes that may help. And the two things behind again this driving |
|
| 27:35 | approach is not only that you have , but the notion that is this |
|
| 27:42 | compute rolls. So you associate computation the amount of data. That's why |
|
| 27:47 | first tried toe have even sizes, I would assume unless you have note |
|
| 27:53 | and you need to include the note and then the dickens uneven in terms |
|
| 27:58 | the number of nodes you want to respective petitions, and the other part |
|
| 28:05 | as a rule of thumb one tend use this surface the volume idea. |
|
| 28:14 | basically you want to minimize the surface the surface to some degree is related |
|
| 28:20 | the amount of communication needed. So giving bombs in the smaller the |
|
| 28:25 | um, the better off you So in that case, very as |
|
| 28:30 | structures or off the physical demand tend to be particularly good in terms off |
|
| 28:39 | criteria to minimize or keep the communication low. So very kind of first |
|
| 28:52 | on this by section strategy is by a little bit rotating rectangle. To |
|
| 29:00 | is not to do things by the access, but do things according to |
|
| 29:07 | , moments of inertia. So in case, when looks at moments of |
|
| 29:11 | and now follow that that's supposed to things by a vertical or horizontal. |
|
| 29:18 | you do it in this case, to the um, sort of main |
|
| 29:25 | of inertia in this case. And you use this access or inertia thio |
|
| 29:33 | audience effectively the coordinate system that instead of juicing day perhaps Cartesian coordinate |
|
| 29:40 | you may have to start with. in this case, just clicking cool |
|
| 29:47 | on the next few slides. It's very quickly. There's things in the |
|
| 29:51 | deck that I think I'm skipping that detail if, how you can use |
|
| 29:58 | , you know, short partitioning But here is basically try Thio, |
|
| 30:03 | , find and then the a good line by in this case, using |
|
| 30:11 | least cars fit effectively to the points you have. And then to find |
|
| 30:17 | cut, you want to find a line or, in general, a |
|
| 30:23 | or hyper plane proposal perpendicular to, this case, into the case the |
|
| 30:31 | . So then your project, the points on two this line and then |
|
| 30:37 | whatever sort of, uh, starting to pick on the line, you |
|
| 30:43 | the productive points respect to the distance that point, and then it takes |
|
| 30:48 | sort of a median point along that , and then you separate them before |
|
| 30:54 | after this medium point along the and then you have to petitions that |
|
| 30:59 | it for sites. So this is of this inertial petitioning, um, |
|
| 31:09 | . And yeah, here's a little more of it algorithm in case one |
|
| 31:13 | interested to use it. But it's the least course fit and productions onto |
|
| 31:20 | line into the, um, So an illustration off. Just you know |
|
| 31:28 | you want there many different slices in case, but there's two illustrated |
|
| 31:35 | Both are kind of least squares, of the line l more or |
|
| 31:43 | And then it's clear that on the hand side graph, if you use |
|
| 31:48 | plane perpendicular or lying perpendicular to it than in the left hand side. |
|
| 31:55 | four ages cut. On the other , if it happens to be the |
|
| 32:00 | line than plane perpendicular to, that a lot more edges to become. |
|
| 32:09 | this is just and the outcome of illustration work and these authority in all |
|
| 32:16 | by section under picks, the left one automatically, that's Oh, here's |
|
| 32:23 | . Like I talked about about the sergeant petitioning thing, and for a |
|
| 32:30 | scientist, I would say you should about. He slipped and Harden is |
|
| 32:35 | very famous uH huh, hear him computer science. And basically, what |
|
| 32:43 | proved is that there's always existed Good, No partitioning or notes |
|
| 32:51 | That's or guarantees that the two parts not too unbalanced for any plane in |
|
| 32:57 | graph that is really one. And notion that are separators as them being |
|
| 33:06 | by many groups to try to understand it works for other types of |
|
| 33:15 | Now, another thing. Um, has been used quite a lot. |
|
| 33:20 | some notion. No space feeling But before I talk about that, |
|
| 33:24 | ask if there's any other questions about coordinate or inertial by section methods, |
|
| 33:37 | talking about the space feeling curves. the idea behind the space feeling curves |
|
| 33:45 | , um, that one find the or basically, in the graph that |
|
| 33:59 | have, you kind of walk around the graph on bond. But there |
|
| 34:06 | are that hopefully only visit the note once, and then you cover or |
|
| 34:13 | notes in the graphs a little bit you're traveling salesman type problem. So |
|
| 34:19 | , once you have visited all the in your graph than, um, |
|
| 34:29 | have a linear ordering all those and then you can do so that |
|
| 34:35 | medium point and says, Well, ones on the before and the ones |
|
| 34:40 | the medium points on to half. then, of course, the Captain |
|
| 34:45 | gets to be this a separator auras to one of the two petitions. |
|
| 34:54 | , yeah, there are a all these space feeling curves that has |
|
| 35:00 | around for a long time, as see famous name and at least husband |
|
| 35:04 | A and the animal he also known something anyone in taking enemy of |
|
| 35:10 | probably seeing an angel, but and give you some examples of what these |
|
| 35:16 | are. So these are space feeling that has been used and trying to |
|
| 35:24 | petitioning for clusters, you know, some examples on them and as well |
|
| 35:31 | what this curves looks like. So the piano type of curves and this |
|
| 35:38 | , just trying to illustrate that it a recursive structure on. You can |
|
| 35:44 | see that your gap refinement on what out on the left hand side as |
|
| 35:49 | basic unit, um, by rotations reflections on. Then you can build |
|
| 36:00 | and signer structures wrong. So this a looks of this guy on a |
|
| 36:11 | ? Nope, I guess I did quick through here on the rotation and |
|
| 36:15 | of being done and then you can it can recur Sali to build more |
|
| 36:21 | more refined structures. But these are simple to use in the case you |
|
| 36:27 | a very regular type of the main him mass structure in 23 or higher |
|
| 36:36 | . But it may not be so impossible to use them if you have |
|
| 36:40 | much more of an orbiter and type and this is kind of the Hilbert |
|
| 36:49 | that looks a little bit different. here is a gun. Same |
|
| 36:54 | How do you feel that ordering to or cover more and more notes re |
|
| 37:01 | again by rotations and reflections on Dhere also okay, So the Hilbert |
|
| 37:10 | You can use it for kind of non uniforms partitioning on space so you |
|
| 37:15 | record so many refined regions and work that. And this has actually been |
|
| 37:21 | in terms off finite element measures. just before that, you see in |
|
| 37:30 | well, I guess. Upper right corner. Now these lines. Skylar |
|
| 37:35 | put on the line in terms off things. Pointer points on graph knows |
|
| 37:43 | when they are separated just a little in space. But there's a number |
|
| 37:47 | notes, uh, and equal, in the different partitions are about to |
|
| 37:55 | on my mark, and I think yes. On this a little bit |
|
| 38:00 | the different partitions are about different That has been about the same number |
|
| 38:05 | notes in them. So this is way in which one can use the |
|
| 38:15 | will be carving and the left hand shone the mapping between the points on |
|
| 38:20 | space feeling curve, and it's just it, according to their read I |
|
| 38:25 | on the top left. But it in terms of notes and the original |
|
| 38:32 | , and on the right hand side kind of illustration of Gilbert turned walking |
|
| 38:37 | in space, and then I'm gonna it in three D on do all |
|
| 38:43 | of things. No on. And is also sometime known as a Z |
|
| 38:51 | energy. Go back and look at slides are that I used in way |
|
| 39:01 | on in terms off, um, album, something I talked about in |
|
| 39:10 | claim that they make this vector matrix multiplication. It was sort of blocking |
|
| 39:16 | the order in which you treat the my country blocks, you know, |
|
| 39:21 | row and column Major order. It's term, but there's also are the |
|
| 39:26 | have talked about. So the compiler they actually looked at how to order |
|
| 39:32 | in memory to make the maximum, , use of locality in terms off |
|
| 39:41 | hierarchy on the Mortons e. Ordering just see ordering was quite popular in |
|
| 39:48 | off, trying to figure out how they things out in memory or traverse |
|
| 39:54 | in memory for optimal use. So hierarchy Um, this was last space |
|
| 40:07 | curve that I included in my slides , and E. I asked us |
|
| 40:17 | by chance heard about great codes. , they kind of resemble where some |
|
| 40:28 | of busy a curve charged. no, I think it's a good |
|
| 40:39 | on top of my head. I say no without looking at it so |
|
| 40:44 | can tell you the principle is So great code was designed way |
|
| 40:54 | And the idea waas in encoding things safe transmission that the great code had |
|
| 41:08 | properties. Or if you look at normal decimal numbers, um, take |
|
| 41:15 | example of the seven and eight on has three bits set, and eight |
|
| 41:22 | only one bit set in the normal encoding. So in that case, |
|
| 41:27 | bits flips on going from 7 to . So the great code has the |
|
| 41:33 | that if you work to go from to 8 and instead of using the |
|
| 41:37 | encoding using great coding coding than a bit has changed. So the great |
|
| 41:45 | is constructed. So in terms of integers, then there's only one with |
|
| 41:53 | changes. So coding. People you know, found this very useful |
|
| 42:01 | of encoding off sending information in order be also simply doing correctness checks because |
|
| 42:11 | was just the one day trip. this thing wants then really re |
|
| 42:18 | as perhaps I should say, um, interconnection work networks in the |
|
| 42:25 | off was known as binary cube tubes and higher dimensions. That on |
|
| 42:33 | has to, um, the extent , too along each axis. So |
|
| 42:40 | basically have a zero and a And that's the number of, |
|
| 42:45 | points in any given dimension. So it turns out that the critical was |
|
| 42:52 | very efficient way for walking around this cube and only sleep one bit at |
|
| 42:58 | time. And that Z what kind illustrated on this particular slide? |
|
| 43:07 | so I think on the next I will show you some examples of |
|
| 43:14 | Jews and then I'll stop again, , take some more questions on these |
|
| 43:19 | of space. Feeling curves, but So this is by a group at |
|
| 43:26 | . P I Rensselaer Polytechnic Institute and are very famous. I was one |
|
| 43:33 | the leading groups in terms of finite methods. Um, and but the |
|
| 43:43 | different pictures on this slide shows is different objects that they studied. So |
|
| 43:52 | is a simple just a cone. is another aircraft win structured in there |
|
| 43:57 | wing on. Then what is the ? And then there's some ordinary that |
|
| 44:04 | did the descriptor session of the space on again. Then you get geometry |
|
| 44:09 | you can work with that. And there is they tried the Hilbert ordering |
|
| 44:17 | Morton Z ordering and the great code So those other three colored curves only |
|
| 44:23 | one of the graphs. Now, there is solving and dashed lines in |
|
| 44:31 | one of the four crafts and the is this on this guy's? That's |
|
| 44:41 | surface index that is the number As I said, Partition surface element |
|
| 44:54 | Thio. The total number of element eso that has run again. It's |
|
| 45:00 | continues domain. I get sliced up small sub domains, and for each |
|
| 45:07 | of the faces off this small sub , the elements In this case there |
|
| 45:14 | a neighbor. So the elements that on the surface of the sub domain |
|
| 45:21 | to know that implies that those faces are on the sub domain surface requires |
|
| 45:34 | with some other. No. So , um, elements that are in |
|
| 45:45 | internal to the note that basically is local memory references. So the index |
|
| 45:51 | gives an indication off the external or communication relative to our local number of |
|
| 46:01 | references. Andi, on the horizontal is the number of partitions. So |
|
| 46:11 | there to, you know, once average line, then solid line |
|
| 46:16 | um, the average overall partitions generated the dash lines are there maximum for |
|
| 46:27 | off the partitions. So I kind in some ways worse case versus average |
|
| 46:33 | in terms off, uh, communication local memory references. So now if |
|
| 46:42 | compare the three different partitioning methods that used, we'll see that the Hilbert |
|
| 46:50 | terms off they look at I'll at cone first, that the Hilbert on |
|
| 46:57 | did better than the other two a bit, but they did better in |
|
| 47:02 | of the maximum. It's kind most of the time most of the |
|
| 47:08 | of positions that seem to be doing better, but it's a little |
|
| 47:12 | you know, they're in who is of the winner as a functional number |
|
| 47:17 | petitions being used, and the similar is on the other cases. But |
|
| 47:26 | we can see that for the muzzle a kind off mostly somewhat, |
|
| 47:34 | larger or not as great worst case the other two methods on the other |
|
| 47:41 | . But order it kind of did in both average and worst case e |
|
| 47:48 | I had one more slide here. is another aspect of the petitioning. |
|
| 47:55 | the previously was basically, um, versus memory references. It did not |
|
| 48:04 | into account another aspect that is That is, how many partitions does |
|
| 48:15 | partition need to interact with? So is what they call the inter processor |
|
| 48:25 | . So ideally, you want also have a lower minimize the number off |
|
| 48:34 | nodes need to interact with, because reflects the number of messages that needs |
|
| 48:41 | because into the network. So in case again, the pictures somewhat |
|
| 48:52 | But when it came to the A , sensing with the number of notes |
|
| 48:56 | need to send messages to, it's always so in this case that the |
|
| 49:02 | , in terms of the near a , did not do as well as |
|
| 49:06 | other methods, even though for the off day that the communicated it was |
|
| 49:13 | better choice. If you go back look at the previous craft, so |
|
| 49:19 | point is simply that yes, first, that there is no obvious |
|
| 49:26 | that's winner. Even in this simple cases, a swell as the table |
|
| 49:32 | been used quite frequently because it tends perform rather well in many cases. |
|
| 49:42 | , I'll stop there before I move to the next and see if there's |
|
| 49:45 | questions. Okay, so is the method I want to talk about. |
|
| 49:59 | by section and pretty clever method, would say an interesting and it |
|
| 50:06 | So coming back to the fine I just talked about So this r |
|
| 50:14 | I group and then you all there and that does final element of simulation |
|
| 50:21 | physical spaces. They at least for long time they used this space filling |
|
| 50:29 | idea. Uh, I don't know they still do their other methods started |
|
| 50:34 | about being a bit, uh, most developed a deep later that it |
|
| 50:42 | quite popular and widely used once. space feeling carb idea is the something |
|
| 50:53 | I just wanted you to be aware because is useful in many other |
|
| 50:59 | Um, a za side remark. for this particular course, but recently |
|
| 51:07 | one of my students will work with group that looked up, um, |
|
| 51:14 | of brain imaging. And in that , it turns out, in order |
|
| 51:19 | the data compression Sometimes Lynn arising the three d space from image ing in |
|
| 51:32 | off signal intensities by ordering and according this place, feeling curves. It |
|
| 51:38 | out that one get the much better than taking them in whatever order that |
|
| 51:44 | naturally, respect to the image. space feeling curves is something I think |
|
| 51:51 | should keep in mind. All Yeah. Um, I'm not sure |
|
| 51:58 | familiar you might be with the but can one make use of, |
|
| 52:04 | , nonlinear dynamics to help out with special filling curves? Mhm. |
|
| 52:11 | Okay, so I'm thinking in terms like attractors, right? No, |
|
| 52:21 | understand. I am trying to figure how to think about it. |
|
| 52:30 | yeah, I don't have a good . Maybe we'll come back to it |
|
| 52:37 | I talk about some of the other that may actually have some relation to |
|
| 52:42 | question. So I'm what I'm talking . Don't When I thought they can |
|
| 52:50 | back to it when I talk about a couple of lines down on the |
|
| 52:55 | , spectral by section, which is of a bit of a clustering type |
|
| 53:01 | , but not quite, but I'm right. I'll talk about this, |
|
| 53:11 | , geometric by section and so way and talked about major cities and mostly |
|
| 53:20 | doing, blocking or matrices. I fairly simple again. It's a very |
|
| 53:24 | structure. And now if you think measures kind of also regular structures, |
|
| 53:30 | pretty easy to find. The cutting that split things evenly, as was |
|
| 53:36 | on um, when I talked about and blue edges right there was just |
|
| 53:43 | to the measure is pretty obvious. didn't prove that those were optimal? |
|
| 53:48 | stops can also be grow that the obvious petitions are in fact as good |
|
| 53:55 | any. And then the petition. best petitioning may not be unique |
|
| 54:02 | So if you have this kind of regular structure, as I said, |
|
| 54:06 | finding a cut in plain that is . It's not too hard, and |
|
| 54:11 | intuitive one tends to be optimal, one doesn't need to be about the |
|
| 54:16 | to find out. No, if don't have this kind of structure but |
|
| 54:22 | something again like final tell emissions along an airplane or the various mechanical parts |
|
| 54:31 | about, it may not be so to figure out how to us cut |
|
| 54:35 | into pieces of about, say, sizes and, well, communication taking |
|
| 54:42 | account on edge cuts and their So, um, what man group |
|
| 54:52 | was actually at Carnegie Mellon did years was try to use this notion in |
|
| 55:00 | graphic protection. So it's kind of neat idea. So what to take |
|
| 55:05 | this is just illustrated now for points the plane, because off making it |
|
| 55:10 | of intuitive to see what's happening is context in this case points in the |
|
| 55:17 | and projected to sphere than in three of this. They always this fear |
|
| 55:24 | one dimension higher than the dimensionality of data set. So in this production |
|
| 55:32 | the factory jobs the point between the in this case in the plane and |
|
| 55:37 | , the North Pole in the sphere then figures out where this straight line |
|
| 55:45 | the surface of the sphere, and the projected point. Okay, so |
|
| 55:51 | way one goes about doing this, one take, um well, these |
|
| 55:58 | and I'll show some pictures, but guess I'll just comment on what it |
|
| 56:02 | on this line. So basically do protection of all the points and in |
|
| 56:07 | the space onto the sphere in the higher dimensional space. Ah, and |
|
| 56:15 | once on a made all the projection all the points onto the sphere, |
|
| 56:20 | does come formal mapping or basically rotation stretching of the points on the |
|
| 56:28 | So the center point on the points gravity off these points, projected points |
|
| 56:33 | this fear ends up and the center the sphere, once one have done |
|
| 56:42 | , one desk could do cutting planes the sphere and what this fellows did |
|
| 56:49 | the best way didn't try to be clever of hard to choose a cutting |
|
| 56:55 | but basically use randomly oriented cutting planes did a bunch of trials and then |
|
| 57:01 | out or selected the A plane that's in the minimum number, all cuts |
|
| 57:11 | that waas so they can tune it trying to figure out the number of |
|
| 57:15 | and decide when to stop trying more planes, and said that this is |
|
| 57:21 | enough. And then they proved that doing this, um, a |
|
| 57:26 | you will get a very good petitioning in practice you didn't need to be |
|
| 57:33 | many random cuts before running up something close to the best possible cut. |
|
| 57:44 | here is now the illustration what they . So there's now plainer triangular finite |
|
| 57:52 | mesh. So then they represent each by as a node in a graph |
|
| 57:59 | then an edge represent, um, that share an edge. So you |
|
| 58:10 | this clean edge from one triangle to Adjacent Triangle and adjacent may also be |
|
| 58:18 | that shares and note. So someone got stand, except the nodal |
|
| 58:26 | like this that represents the triangles. then knowing the triangle, which is |
|
| 58:33 | shown on this slide, one knows the edges are that relates to other |
|
| 58:38 | in the graph. So these are their notes that should be projected onto |
|
| 58:43 | three DS here in this case and the play. So here is kind |
|
| 58:47 | what happened when they did the production it looks more like the protector to |
|
| 58:52 | South Pole rather than the North It doesn't matter which ones you do |
|
| 58:56 | take one of the goals. That's simplest option. So now you can |
|
| 59:01 | , I guess the notion that it like maybe points on a sphere |
|
| 59:08 | then, the next step waas to of rotate and stretch things on the |
|
| 59:15 | . So the center of gravity that think was shown area on this point |
|
| 59:20 | is no longer on this sort of access of the sphere. Um, |
|
| 59:26 | by the rotation and stretching on this , banking got the central gravity or |
|
| 59:33 | point of the points to fall into center of the sphere on then. |
|
| 59:40 | sort of circle and you see here kind of an example of a playing |
|
| 59:44 | cuts through the center of this year then splits, then notes on this |
|
| 59:53 | and roughly two equal parts and then . Given what the cut, this |
|
| 60:01 | can figure out how maney edges of being associated with this cut as well |
|
| 60:07 | how balanced is the captain. The of the number of notes from either |
|
| 60:12 | of this cut in plain so and once when I've decided, always cut |
|
| 60:17 | plane to use one can projected that cutting plane onto the to deplane and |
|
| 60:27 | on Bester has can see the two off the petitions and then one time |
|
| 60:38 | , return it back to looking actors define it. Elements, goods where |
|
| 60:44 | cut is on decided, you on the exact cut which elements goes |
|
| 60:50 | to the top and which ones goes the bottom. So this is a |
|
| 60:55 | what, uh, this geometric method does. So conceptual is quite simple |
|
| 61:03 | coding wise. It's quite simple, , to use. And it does |
|
| 61:09 | pretty decent cuts With the few trials , uh, in the slide deck |
|
| 61:15 | there is a bunch of examples. not sure I used Thio showed all |
|
| 61:21 | . Many of them are. We'll what the next slide is. That |
|
| 61:25 | it, I guess, in terms But there is example Sahara, then |
|
| 61:30 | tries when needed to do and how improvement that cuts change with the number |
|
| 61:35 | trials is by no means wanna tonics some additional trials make it worse. |
|
| 61:43 | . So and at some point, need to decide when you want to |
|
| 61:50 | . So these were the coordinate based I plan to talked about. So |
|
| 61:58 | questions on these coordinates based methods? . Um, yeah. So now |
|
| 62:17 | won't talk about it. Also noted section methods and then about this so |
|
| 62:23 | spectral deception. The normal by section like, I would say, the |
|
| 62:28 | by section. Pretty straightforward, except doesn't necessarily need any coordinate points. |
|
| 62:35 | it's just basically, you can do through the breadth First, search eso |
|
| 62:41 | one creates what sometimes calls a level . So you pick one point in |
|
| 62:49 | graph that job and they make it the route and then you figure out |
|
| 62:58 | what nodes are a distance one from road and then from them. You |
|
| 63:03 | out what are the Children knows such have not already accounted for. Um |
|
| 63:11 | I got this kind off a level that reflects how far best from the |
|
| 63:24 | the various notes in the graphs And then you can best the slice |
|
| 63:32 | according Thio, the level for which have about half of them closer to |
|
| 63:38 | roots and half of them so that the roof. Okay, so this |
|
| 63:46 | the very I would say simplest. , not the simple, but it's |
|
| 63:50 | very simple method for doing things, you don't necessarily have coordinates, but |
|
| 63:56 | have a topology. Now there, , how you pick the route? |
|
| 64:06 | , there many different matters, and is typically and one way is basically |
|
| 64:12 | pick randomly one and you try it see what kind of a cut you |
|
| 64:20 | . And then you can just take random one. Or if I can |
|
| 64:28 | a notes based on the degree of notes on all different versions, that |
|
| 64:35 | fine has been tried. There is that is known as, um |
|
| 64:43 | that uses reverse. Um, when have to, your first attempt to |
|
| 64:50 | a random note, you bigotry then off the notes that are then |
|
| 64:56 | of at the bottom of the tree picked among the ones that are at |
|
| 65:01 | furthest away from the root Makes that one of them. If there's more |
|
| 65:08 | one, you make that the new . And so you kind of flipped |
|
| 65:13 | tree and then start to proceed the tree from they know they leave. |
|
| 65:19 | , that was one of them furthest from the room. And it turns |
|
| 65:25 | there to do that. Sometimes you , um, a better cut so |
|
| 65:31 | of them simply picture of do the and then let's not think of |
|
| 65:37 | Basically, hang the tree upside down see what happens. And then they |
|
| 65:42 | do that a few times and get , um, no, that furthest |
|
| 65:49 | and try a few times or just picked yet another starting point. This |
|
| 65:56 | so this is one way that the first search can be done to, |
|
| 66:01 | , there's the level graph and then petition based on the level graph. |
|
| 66:09 | here is an example off. it may work out in terms of |
|
| 66:14 | regular mesh. We're in this the center point of the mess when |
|
| 66:18 | kicked us The rule on, as can see, with various, |
|
| 66:26 | squares that are kind of rotated, , 45 degrees with respect Thio the |
|
| 66:33 | of the knish you can see The center point is just the root |
|
| 66:41 | of one little square in the and that distance one from the |
|
| 66:46 | There are four notes and then you to distance to accept, so you |
|
| 66:53 | see how many nodes there are at different distances from the root and they |
|
| 67:00 | kind of, as I said, for the five degrees visually respect to |
|
| 67:05 | mesh on its account. You can see that the total number off Yellow |
|
| 67:13 | knows is almost identical to the total of notes in this case in the |
|
| 67:21 | including or illustrated squares. So this the seven by seven measures 49 notes |
|
| 67:29 | one is 24 1 is 25. this is just an example how they |
|
| 67:35 | . First thing worked out in terms partitioning in this case, 22 part |
|
| 67:47 | . And there is, I and the slide that can swallow is |
|
| 67:51 | little bit of pseudo code for out generate the bread first dealing with it |
|
| 68:00 | . One comment. I should make guess. It's a good point. |
|
| 68:05 | many on the partitioning algorithms are actually algorithms, um, or husband. |
|
| 68:19 | of course, that means you're restricted what you can do on a single |
|
| 68:29 | . Or it may take a very time if you need to bring in |
|
| 68:34 | of image from disk or some other um, memory. So parallel partitioning |
|
| 68:46 | are sometimes not too straightforward generalization off sequential out with its soul. This |
|
| 68:57 | a comment because the sue the codes have on the slides that don't show |
|
| 69:04 | it's in the slide that they tend be most sequential arguments. Any question |
|
| 69:16 | the breath? First one of or idea not what happened now? |
|
| 69:30 | , there is one more on right? Two more other than the |
|
| 69:37 | in um so this is kind of interactive refinement type algorithm where I'm are |
|
| 69:45 | means, yeah, have a partition two parts on typically and deception again |
|
| 69:57 | a starting point. Um, and you figure out the number is just |
|
| 70:03 | cut and then you try Thio figure how to get the better partitions by |
|
| 70:13 | notes in this case between the A B domain. So this is what's |
|
| 70:23 | as a cardigan, Lynn and And it was on the way back |
|
| 70:28 | people at A T and T, guess figure out needed to figure out |
|
| 70:32 | to build communication networks from networks. , on this algorithm is actually forms |
|
| 70:46 | basis, I would say for one the very popular petitioning methods, but |
|
| 70:55 | and this, um, direct But it is that the core off |
|
| 71:01 | I will talk about most likely next . So it says here the cost |
|
| 71:09 | basically the number of edges that go the two domains. And it should |
|
| 71:18 | knows between, say, x uh, providers who knows between the |
|
| 71:24 | and B domains than, um, used to be, um, |
|
| 71:32 | I just as I just that connects point. So the other domains of |
|
| 71:40 | two edges going from X two points be And it only has one edge |
|
| 71:48 | to another point within a sort of to move from A to B. |
|
| 71:57 | again, so to speak to men reduce the number of edges from A |
|
| 72:02 | B by two on you get one edges, so there is a net |
|
| 72:07 | of one. Andi, if one at why that has to internal edges |
|
| 72:17 | two edges going from B to So if you move, why from |
|
| 72:23 | to B, then there's basically no in terms of the number of edges |
|
| 72:29 | , um, a crossing from A B on. The idea with this |
|
| 72:36 | is you need to be keeping the balance. Or if you move something |
|
| 72:42 | A to B, then you also to move something from BBA toe A |
|
| 72:47 | order to keep the partition sizes. balance. So this is what this |
|
| 72:54 | does, um, a little bit there algebra for figuring out what the |
|
| 73:02 | costs are on this life on. think this is a little bit more |
|
| 73:08 | of what I just talked through, to figure out what cut sizes and |
|
| 73:17 | it's certainly slide. It's relatively expensive essentially you end up doing, |
|
| 73:24 | n Square trials, checking all and then you dio decide on which |
|
| 73:32 | to swap. And after the you need to try again. So |
|
| 73:37 | why you get something. And that complexity. Wise should stabilizer converging about |
|
| 73:45 | CUC operations, which is quite The reason why this is still method |
|
| 73:52 | is that this a synthetic behavior, fact, is very pessimistic, pessimistic |
|
| 74:00 | practice. So that's why the few may actually be sufficient to do |
|
| 74:08 | and I'll talk about that more next , and I was that and let |
|
| 74:13 | spend a few words on this that by section and then, uh, |
|
| 74:18 | about the other things. Next any question on this corner gone Lynn |
|
| 74:26 | algorithm and basically attracted refinement off by that has been made. Okay, |
|
| 74:38 | number section is something quite different. , so as a fellow by the |
|
| 74:49 | of Fiedler that realize that one can argon value analysis to partition crafts |
|
| 75:04 | I think the analogy that is tickle as this notion of a vibrating string |
|
| 75:13 | to see in the middle of this . Okay. And so there is |
|
| 75:21 | vibration modes. You know, if have the two and points on the |
|
| 75:24 | , there are basically six lights in violin or get arms that the end |
|
| 75:33 | are fixed on your pocket and you different wave forms of the string between |
|
| 75:39 | two young points. So these, , modes on there, as you |
|
| 75:49 | , illustrate in the middle of corresponds different Eigen values of the model off |
|
| 75:58 | string. And if one looks at center point here, center graph in |
|
| 76:07 | center, that is kind of almost a sine wave thing. F |
|
| 76:14 | what? To look at the plus and the minus part on the parts |
|
| 76:20 | the strings. It is kind of good, um, point Thio. |
|
| 76:28 | of whatever is on the left side one half and whatever is on |
|
| 76:32 | negative side is another house. So can be applied thio much more general |
|
| 76:42 | in a stream. But in kind this, then then the I get |
|
| 76:50 | or again, yeah, I get off. The structure is reflected in |
|
| 76:56 | values and Eigen vectors, and one think of that. If you have |
|
| 77:03 | least some playing sheet on you, you need some partitioning again to use |
|
| 77:13 | dynamics off the sheep that it bends flexes? And then it turns out |
|
| 77:22 | that then the Eigen modes on. a good way off partitioning the structure |
|
| 77:30 | . I guess my time is actually , so I should continue with the |
|
| 77:36 | by section next time and take some before so next collection. And let's |
|
| 77:47 | the question. So I'll tell you more exactly what to do in this |
|
| 77:51 | . But it involves computing Aryan values Eigen vectors, but you only |
|
| 77:57 | and some of you may say that's very expensive computation, and in principle |
|
| 78:01 | is, Ah, but normally, only cares about one Eigen value and |
|
| 78:10 | corresponding Eigen vector, so one doesn't to solve the full. I can |
|
| 78:16 | a problem. I can just focused methods that compute a single I can |
|
| 78:26 | . On the other part, it not necessarily have to be computed very |
|
| 78:31 | . So that means one thing you ejected onion value methods to get the |
|
| 78:37 | good estimate off the Aryan value. is interested in that without expanding too |
|
| 78:48 | much in computing. We'll talk more that as well as where it has |
|
| 78:55 | used in the outcome. And so authors off not and it's important, |
|
| 79:06 | data, Sanya National Labs and our . They developed a very good software |
|
| 79:13 | for doing these things, and they got lots of the washing prices for |
|
| 79:19 | . Okay, take questions. So need to think about everyone's question about |
|
| 79:36 | dynamic are chaotic type methods. how that may be related. I |
|
| 79:45 | have a good as they're gets about more for the case of so they |
|
| 79:50 | be useful for a static graph, O b A dynamic growth. But |
|
| 79:53 | you know that based on certain industrial , you'll never leave a certain area |
|
| 79:59 | I was thinking. It would be . Yeah. No, it's a |
|
| 80:05 | idea. I'm sorry. I need think about it. I don't have |
|
| 80:08 | good answer, but let's see if can get, uh, look around |
|
| 80:17 | see a little bit put people may done and not to use it. |
|
| 80:22 | a good question. So thank Probably It was more of a shot |
|
| 80:26 | the dark. Yeah, it's Yeah. Um, yeah. Dynamic |
|
| 80:38 | . There are not always intuitive, many times they do give interesting and |
|
| 80:42 | results. So any other questions? ? Okay. If not, I |
|
| 81:01 | stop the recording. Stop sharing This one. I do e didn't |
|
| 81:08 | |
|
