| 00:00 | hurtful. So, uh, so . So it s O and I'll |
|
| 00:11 | a little bit more about the composition data structures or data sets. You |
|
| 00:16 | , for clusters or MPP, where a communication network going to connection network |
|
| 00:25 | you need to decide what goes where for anything that requires cluster. The |
|
| 00:34 | talked about on Monday as well as is, should be valuable to |
|
| 00:41 | So that's why I kind of, , include them and the classes. |
|
| 00:48 | sometimes people, um that a doctor other disciplines, they don't quite understand |
|
| 00:55 | their tools for petitioning data structures. even though we don't have an assignment |
|
| 01:01 | you to do it, But so is for your general education, Let's |
|
| 01:07 | so. I was about to start Specter by section, and then I'll |
|
| 01:12 | about that on the other bullets on slide. All right, so this |
|
| 01:18 | again The purpose is to carve up data using this idea of an owner |
|
| 01:24 | ALS and most of the computations air whether data is But since you're solving |
|
| 01:30 | problem that doesn't fifth and an typically or for other reasons, they |
|
| 01:36 | more complete powers. He has spread out over a number off notes that |
|
| 01:43 | them recently load balance. And I to, uh, minimize or of |
|
| 01:50 | excessive communication, because the communication net , even slower than memory access, |
|
| 01:59 | by 2 to 3 orders of So that's the whole of the |
|
| 02:05 | All right, You know, respectable section I showed this slide and |
|
| 02:09 | about the string plucking a string in various again loads are illustrated here |
|
| 02:15 | um well, the vibrational states, you like or again notice the |
|
| 02:19 | I used him alternatively, and talking these things and some of you that |
|
| 02:25 | familiar with argon analysis. For those you, hey, may make |
|
| 02:31 | The point is that the middle one and I says lambda, too. |
|
| 02:35 | string pictures is the one that has of been used for partitioning graphs in |
|
| 02:42 | . And, um so here is a little bit that that did not |
|
| 02:47 | talk much about, But if you a graph fun conform. This called |
|
| 02:52 | matrix that may be familiar from some topic about electrical engineering or physics or |
|
| 02:59 | one also uses discreet representation. Sometimes . I want to try to |
|
| 03:07 | and I have a picture on the slide. But basically where the |
|
| 03:11 | my tricks e want to set it . So one has one role for |
|
| 03:15 | note in the graph. And then has one column for every, |
|
| 03:19 | edge in the graph? And then because you get to interests in every |
|
| 03:27 | that corresponds to non zero interests. should say that corresponds to the notes |
|
| 03:37 | the end, ends the edge. then there's another one that, |
|
| 03:43 | lactation matrix that is used in That's it for doing draft the composition |
|
| 03:51 | it's a symmetric methods and metrics. this case that one has. There's |
|
| 03:56 | same number. Off rose and colors house show the next kind of slide |
|
| 04:04 | they illustrate these two things, so too trivial graphs kind off on the |
|
| 04:10 | hand side. And then there's the . Corresponding incidents matrix in the middle |
|
| 04:13 | the slide, and then we have loved policy and on the right hand |
|
| 04:19 | . So if you look at the line graph again, there is a |
|
| 04:25 | notes. There's five rolls on, , therefore, edges therefore columns. |
|
| 04:30 | if you look at the recall, then there are two interest in each |
|
| 04:33 | of them that corresponds to the end off the corresponding edge. So first |
|
| 04:42 | number one there is a blue one it's right on track. What happened |
|
| 04:51 | ? Yes. Um, that has endpoints, that old one and no |
|
| 04:58 | . So there's there's two entries and it can follow them for the other |
|
| 05:05 | very simple and similar, and one them is that has a negative value |
|
| 05:10 | the other one, and it doesn't too much which one you would makes |
|
| 05:15 | negative value and the other one that value the main point. And it |
|
| 05:22 | necessarily need to be one. They be waited as well. But this |
|
| 05:26 | a very simple examples to show the on the matrix that's a gap. |
|
| 05:32 | in the terms of the mash craft the lower left hand corner and the |
|
| 05:37 | incidents matrix, you can kind of the happen as well. First day |
|
| 05:44 | one and two. They have the structure as for the line graph, |
|
| 05:52 | then when it comes to three, the connection with one and four So |
|
| 05:57 | to non zero interest are a bit apart and correspondent to again. |
|
| 06:03 | their role for another one in four . Now on the right hand |
|
| 06:09 | this Laplace and matrix that corresponds Thio . Same number off rows and columns |
|
| 06:15 | the number of notes and the And then you get entries, according |
|
| 06:21 | . The connectivity. So what you you have the center of the |
|
| 06:28 | it's it's themselves like which are then the dia Galo in this fashion |
|
| 06:36 | And then you have the off diagonal that tells toe which no, |
|
| 06:41 | much. No, There is an so often take note to. Then |
|
| 06:46 | connects both the note run and Three, so they have interest and |
|
| 06:51 | to not wanna know free. And this case, the elements of the |
|
| 06:58 | equals the number off. Incident edges that note. No one can do |
|
| 07:04 | same exercise for the Are there for nice craft in the bottom row on |
|
| 07:15 | , and it's simple, so it a lactation matrix. If one has |
|
| 07:20 | incidents matrix, one can get to passion by basically taking the Indians matrix |
|
| 07:28 | its own transports. So in this , take top one which is a |
|
| 07:34 | by forward, and I should take transpose over to get the four by |
|
| 07:38 | . And then the product is basically fight by Fine. That is several |
|
| 07:42 | M matrix. So it turns out this fellow Fiedler I was a check |
|
| 07:51 | that realize that this, uh, actually a pretty good idea for you |
|
| 07:58 | graph partitioning. And because of the way that the passion matrix has |
|
| 08:08 | , it's symmetric and Israel. Um mean that the edge values aerial values |
|
| 08:16 | the maybe weights and so on. it's a really honest symmetric matrix that |
|
| 08:20 | again values both Rio and, um or zero, but not negative, |
|
| 08:26 | should say. And it also has Eigen vectors correspondent to the again values |
|
| 08:35 | positive. I guess I should Is there anyone that Yes, For |
|
| 08:42 | knowledge, I'm not sure what I do about it. But anyone that |
|
| 08:45 | not know about idea values and Eigen . Hopefully you have heard the concept |
|
| 08:59 | for me, my intuitive sense is the string illustration in the couple of |
|
| 09:08 | backs that the I again mode for one of these. Yeah, |
|
| 09:18 | molds Here on the string there is Eigen value, and the deflection of |
|
| 09:22 | string corresponds to the idea of So those are the intuitive just notional |
|
| 09:33 | again, value on again vector competitions you so the point that it says |
|
| 09:39 | this slide. So if you have graph that turns out that the smallest |
|
| 09:46 | value is in fact zero because it's is disconnected cept or it doesn't has |
|
| 09:56 | anchors, is filthy then, lunch and sort together again values in |
|
| 10:04 | over their magnitude because again, they're simple to order on. Then the |
|
| 10:11 | non zero Eigen value corresponds to Yeah, made their crash in this |
|
| 10:17 | , the one that's about looks like like a sine wave on this particular |
|
| 10:23 | . And, um, the in case, we can use this deflections |
|
| 10:32 | the strain from the Bible state. the ones that have a positive and |
|
| 10:38 | negative deflection thio, uh, make sort of repetition ings or if you |
|
| 10:44 | string model in terms small elements and dynamic equation for the strength than, |
|
| 10:53 | , you get deflection. Correspondent of small partitions of the string is used |
|
| 10:58 | modeling, differential equations or other stream . So that's his son used for |
|
| 11:06 | petitioning. So that's what I said this slide, I think Andi So |
|
| 11:14 | is a little bit of analysis was by Jim Jamela at Is He Berkeley |
|
| 11:22 | were well known in America analyst, we don't need to get too much |
|
| 11:27 | again value problems yes, to, a little bit hard works. And |
|
| 11:32 | there are software packages out there that these things. You don't have to |
|
| 11:37 | to write code for it if you to use it at some point. |
|
| 11:45 | , so. But basically, says compute, they don't have to compute |
|
| 11:50 | the arguing values you basically are interested for doing a by section. The |
|
| 11:55 | non zero I can imagine when they in order magnitude on you. Look |
|
| 12:01 | the corresponding I am back to, it takes the I get back to |
|
| 12:06 | . Positive values to form on petition Yangon, values were non positive values |
|
| 12:12 | the other petition and you're in The next thing I have a little |
|
| 12:20 | more slides. For those of you may be interested in this in particular |
|
| 12:24 | the next several slides I have is show you a little bit what the |
|
| 12:28 | of using this bathroom might be the . In fact, kind of old |
|
| 12:33 | from worked at the long time ago number of collaborators. But the point |
|
| 12:40 | taking this showing this picture is a of things. One is first to |
|
| 12:49 | that the cuts or the partitions that being made intuitively makes sense, |
|
| 12:55 | So the algorithm didn't try to slice along the shaft of this particular |
|
| 13:02 | Try to minimize the cut area, ? So it, oh, make |
|
| 13:06 | cuts off the structure. Our particular kind of. When we talked about |
|
| 13:13 | inertia, a coordinate based method it's clear the moment of the |
|
| 13:19 | If you look at the shaft, along the shaft, and the cut |
|
| 13:21 | per particular to the chef. This was also done, so each |
|
| 13:27 | another petition should have roughly same number finite elements in this case, so |
|
| 13:33 | can see that color coded part if is very small elements of high density |
|
| 13:41 | elements, sadness in terms of the space petitions are small, but it's |
|
| 13:48 | the same number of elements in all petitions. Another part in using here |
|
| 13:55 | to show, uh, how things off scale of computational effort. Respect |
|
| 14:04 | the number of petitions that one would on the horizontal axis, in this |
|
| 14:10 | is a logarithmic access. Where's the access is just a normal in your |
|
| 14:17 | access. So what, You can this particular method in terms of generating |
|
| 14:24 | petition ISS that it, um it even grow as quickly as the log |
|
| 14:33 | the number of petitions. So it's computational efficient in that sense to generate |
|
| 14:40 | large number of partitions. And then some statistics about how many edges so |
|
| 14:47 | of edges have a cut to the number of edges and not show a |
|
| 14:52 | more examples. All this method for other structures it this one is a |
|
| 14:59 | simple one, um, that the partition in this way, and for |
|
| 15:05 | , it's kind of a curiosity because particular mhm part are petitioning was used |
|
| 15:17 | , you know, Foster on the of his book for Designing Colonel |
|
| 15:21 | So that was the work within and , I guess, like this particular |
|
| 15:29 | and ask difficult uses for his book . Anyway, this is another |
|
| 15:33 | In this case, it's kind of to linear in terms of the |
|
| 15:39 | in terms, off the logarithmic or of the number of petitions. Of |
|
| 15:46 | , the number of edges cut this . The percentage share this clearly it's |
|
| 15:52 | the very high percentage, but it's on the size of the partitions on |
|
| 15:57 | size of the graphs. It's not that particular magic number. And the |
|
| 16:03 | went, Yeah, again, the in the number of petitions and our |
|
| 16:08 | your petition there is a little bit off, perhaps more serious, large |
|
| 16:15 | , larger scale examples. So this for fluid dynamics, competitions that put |
|
| 16:21 | at the time, and in that's a curiosity. So this when |
|
| 16:25 | was the work was done, there the first time, um, and |
|
| 16:30 | aircraft was model and the airflow around aircraft waas simulated. So that was |
|
| 16:38 | Falcon jet that is I am regional talk chat, and you can also |
|
| 16:47 | some other the airliner that doesn't What? This study. But it's |
|
| 16:51 | a half of the triple Seven structure the affecting you may be familiar |
|
| 16:56 | but the point of this thing. you can see in this case, |
|
| 17:00 | number of notes in this final element . They went up to about 350,000 |
|
| 17:08 | the number of elements for about two and the number of edges for about |
|
| 17:12 | million. And the largest graphs, , but this basically shows them a |
|
| 17:18 | bit off. The scalability that I to again show for these more, |
|
| 17:24 | somewhat ambitious or complex structures is that did this for up to about 2000 |
|
| 17:30 | 2000 petitions. And again, if look at the petition in time |
|
| 17:37 | uh, so it's a factor off , I guess, from the foul |
|
| 17:45 | Thio. The M six wing there a two million, but if you |
|
| 17:52 | at the time, it grows by less than a factor of five. |
|
| 17:58 | again, this case very well. a question. Out of curiosity, |
|
| 18:03 | were the processors at the time with use. So this waas um |
|
| 18:14 | there was on the first The computer a connection machine. I have to |
|
| 18:18 | out what year it was in this of the connection machine we may have |
|
| 18:23 | , um, but the Yes. it says number of processes 2000. |
|
| 18:34 | this was against the connection in model on the processors that we used on |
|
| 18:48 | one. I need to go That's a good question. I should |
|
| 18:59 | this by art, but it may been a MIPS processor. I believe |
|
| 19:05 | waas for this generation of the Um, Thio, whatever is your |
|
| 19:18 | your cell phone is more powerful than processor waas. Yeah, Um so |
|
| 19:29 | a good question. I will try go find out what we actually |
|
| 19:36 | So I just the security Oscar um, for seven years. So |
|
| 19:43 | early machine of this earlier version of machine 64,000 processors, which is still |
|
| 19:53 | fairly large number even compared to today's machines and this was done have |
|
| 20:00 | embarrassed to say about almost 30 years . So all right, so and |
|
| 20:09 | to show that was the floors. then I have your structure mechanics, |
|
| 20:14 | , fracture mechanics problem. And then is a case. What? I |
|
| 20:20 | to show for it. Weak scaling this particular case, using is, |
|
| 20:27 | , but for petitioning algorithm. So weak scaling in the sense that you |
|
| 20:32 | at the table below and tells you about the size, the number of |
|
| 20:37 | of the problem size on. You see if we scale the problem with |
|
| 20:41 | number of processors in this case. huh. You get the same efficiency |
|
| 20:48 | the time is proportional. The time processor is pretty much constant. So |
|
| 20:56 | kind of fairly ideal scaling one could at the time, people think thought |
|
| 21:03 | I wasn't possible for unstructured much and that was one of the things |
|
| 21:08 | cool people wrong with. Alright, other questions on that before ever? |
|
| 21:14 | are so all right. So now about multi level graft petitioning. And |
|
| 21:30 | a zai mentioned last time I didn't on it. This time I've been |
|
| 21:34 | this spectrum by section I was was today to that they only need take |
|
| 21:41 | about one Eigen value eso there argon methods after asked you to focus and |
|
| 21:49 | get one and not all of Normally, Eigen value competition is very |
|
| 21:55 | . But if you restrict your computations just finding one, it's not all |
|
| 22:04 | that it was acceptable effectively to do . And the quality of petitions were |
|
| 22:10 | good. And one can actually prove they are actually hasn't optically on the |
|
| 22:19 | sponsor you could get. If you're it up the other part, what |
|
| 22:25 | it feasible? One doesn't need to the Eigen values very accurately. So |
|
| 22:30 | our case, it was shown for the examples they tried, uh, |
|
| 22:38 | what customers did. So I had kinds of stuff that traded. This |
|
| 22:44 | was gave sort of good enough There was no really point to the |
|
| 22:50 | at the higher position. And that if you use destructive algorithms, then |
|
| 22:55 | can take advantage off. Yeah, level of precision you need to reduce |
|
| 23:02 | computational effort. Nevertheless, if you a very large graph, um, |
|
| 23:09 | computation, time may still be And in the slides that did not |
|
| 23:15 | about what they are in the Sign of uninterested can look at those |
|
| 23:19 | . Um, then you will see what fraction of the computer time is |
|
| 23:24 | petitioning time. But in our I think there was, yeah, |
|
| 23:31 | to 20% off the solution time. right, so there, there, |
|
| 23:39 | terms of of the level petitioning, that when the try to find a |
|
| 23:46 | graph that is small compared to unity small enough compared to the crafts, |
|
| 23:55 | want the partition. So it proceeds trying to do what's known as a |
|
| 24:02 | off the graph to reduce it to smaller. And then when petitions, |
|
| 24:08 | smaller graph by any one of the I've talked about so far and then |
|
| 24:14 | try to project back onto the original the partitioning that made on this course |
|
| 24:24 | . So here's kind of a cartoon off this multi level and thing |
|
| 24:29 | One goes through a number of coursing until the finance, something that I |
|
| 24:35 | competition and feasible to petition. And van can run the course in the |
|
| 24:42 | reverse to make it finally, anti anyone get back to the original |
|
| 24:48 | and then each step off sort of the coarsening. What makes this production |
|
| 24:55 | potentially refinement step four steps for each stop. So this is the basic |
|
| 25:09 | in this multi level partitioning, escaped preneurs kind of some cartoon examples |
|
| 25:17 | and then some actual results off doing . So there was one package out |
|
| 25:28 | . They're known as neatest. There created by faculty and students at the |
|
| 25:35 | of Minnesota that has become quite popular use for graph partitioning. And on |
|
| 25:47 | side there is pointers to Harmon's and and with this particular petition and always |
|
| 25:54 | the way they dio coarsening of the is to use what's known as maximum |
|
| 26:01 | ing's. And when maximum matching XYZ , try Thio. Find the collection |
|
| 26:11 | is, or the largest collection of can get, um, without anyone |
|
| 26:18 | the registry collect or grabbed from the sharing an end point. So if |
|
| 26:25 | looks like this simple graph here, the red, red and just do |
|
| 26:33 | share any and points and except for of the notes, you can tell |
|
| 26:43 | all the notes are covered by these red edges and there is one point |
|
| 26:50 | if you were to try to use or its incident edges has kind of |
|
| 26:55 | the left graph here towards the on the right side, in the |
|
| 27:02 | one of the three on the right of the graph, any one of |
|
| 27:07 | just would then connect to another note is already covered by already. So |
|
| 27:13 | just becomes by itself. Then, this course, a graph on basically |
|
| 27:19 | . They know that the ends of edge into the course note. So |
|
| 27:25 | this case, that becomes five course , one being the famous originally |
|
| 27:32 | not we did not pick an incident for in terms of the matching |
|
| 27:39 | but then we have a year and then one can continue to do |
|
| 27:43 | personally, but they didn't do it this case. So in that case |
|
| 27:49 | competition, that graph, uh, stops there, and then one has |
|
| 27:56 | do the back production onto the original . But I hope I have on |
|
| 28:03 | slide, yes. So launch and protected them onto the original breath |
|
| 28:11 | So this is kind of the idea the Minnesota folks used for the media's |
|
| 28:19 | , and then they used. If , as it says on the |
|
| 28:25 | this slide and one can use them Colonel Conlin method not to talk about |
|
| 28:34 | when you have in this case, by partition and then you can try |
|
| 28:37 | figure out is by swapping notes between . If it actually reduces the total |
|
| 28:45 | off edges or the weight off the is being cut. So So they |
|
| 28:54 | and I have some results. Something , some slides coming up, |
|
| 29:01 | Yes. So this as a bunch standard, um perhaps that are available |
|
| 29:12 | at various websites. I don't think orders, if your words websites that |
|
| 29:21 | interesting graphs for the community to use test algorithms. And so this comes |
|
| 29:29 | one or several of them. I remember. But in the paper that |
|
| 29:35 | called it at the bottom off the , anyone interested can find more |
|
| 29:40 | But what they did for this, , have somewhere they got them |
|
| 29:46 | As you can see in this many of them come from solid or |
|
| 29:51 | mechanics type applications. They're not particularly . They're not trivial but I was |
|
| 30:01 | they did this work. Reasonable test cases, Yeah. So a |
|
| 30:13 | bit more details about what's happening in maximum matching. Okay, so it |
|
| 30:21 | totally fully define how you take the not to include in this or construct |
|
| 30:30 | maximal matching set. So what? group they tried a few different schemes |
|
| 30:39 | on this slide. So the first is simply just randomly pick edges as |
|
| 30:44 | as they don't have any common, , and points or notes, and |
|
| 30:52 | can't doing that. So of course statistical, and you run it. |
|
| 30:57 | huh. A bunch of times and some statistics on die. Don't know |
|
| 31:04 | how many times they did it, it probably took the best all a |
|
| 31:09 | of runs to get the course craft doing this random matching. And I |
|
| 31:23 | to find it in their papers, before the lecture, and it wasn't |
|
| 31:29 | to me to what? How far went in terms off. They're questioning |
|
| 31:36 | they went all the way to 32 or the stopped at some part and |
|
| 31:42 | , um, partitioning before they went 32 petitions. Um now the have |
|
| 31:54 | successor. Heavy edge matching is the that makes logical sense to me because |
|
| 32:02 | they do in that case is basically visit snows in the graph. And |
|
| 32:07 | you want to know, you pick edge. For that note, that |
|
| 32:13 | not conflict in with what have you already picked that has the maximum |
|
| 32:21 | So that means if you pick that that becomes now a kind of course |
|
| 32:27 | that she, like s O, gets not the left to partitioning. |
|
| 32:36 | you kind of make heavy edges internal course knows. And then they did |
|
| 32:43 | the opposite. That was like edge . And then they also just a |
|
| 32:49 | bit more sophisticated than trying to find the clicks sort of heavily connected note |
|
| 32:57 | in the HCM notion. So what out for this particular example? Shown |
|
| 33:04 | this graph for 32 we're petitioning this age edge matching worked well and most |
|
| 33:14 | the graphs. So on the next and some of the data you picked |
|
| 33:18 | that, um, they used this h matching because it performed so well |
|
| 33:25 | the bulk of the examples they So the other part Waas then strategies |
|
| 33:35 | refinement when you do the UN So they tried to do the back |
|
| 33:40 | to the original graph on the cut that you're made on this course |
|
| 33:49 | And there's a whole developing number and alternatives that tried on the slide. |
|
| 33:55 | first is just greedy that I said one interational, this corner gone Lynn |
|
| 34:05 | , refining scheme that I talked about time on the KR is best that |
|
| 34:11 | weren't until they kind of converges. that's more than one interaction. Whatever |
|
| 34:18 | of integrations it took for some then the D. J R |
|
| 34:25 | Instead of looking at all the notes the petitions and during refinement, just |
|
| 34:31 | the notes that are on the edge boundary off a petition that then has |
|
| 34:37 | to another petition. And so that be in front of G, R |
|
| 34:45 | K and R are then the two one Gear and kale are but then |
|
| 34:50 | , considering under a notes and, , all the notes and the |
|
| 34:57 | And finally, the combination off using Lynn refinement for course craft. But |
|
| 35:07 | one gets closer to the original graph have more notes than restricted to the |
|
| 35:13 | and just do one interational day. on, man. So in this |
|
| 35:20 | , in terms off the party, find what time I can see that |
|
| 35:30 | winners this video are album. And one looks at the, uh, |
|
| 35:39 | of edges cut on, then the sonogram in refinement that uses more iterations |
|
| 35:49 | yeah, fine and but still stays the boundary turned out to, in |
|
| 35:56 | cases generate the best cut. So kind of an interesting exercises on, |
|
| 36:04 | there's more of it in this particular . But I just wanted to illustrate |
|
| 36:11 | this, um, idea works on notion of doing course inning petitioning and |
|
| 36:17 | course inning. And then, um has been a very successful and white |
|
| 36:25 | SNC. Their software has been widely for graph partitioning uh, in their |
|
| 36:32 | . They have done there at this . That is quite a few years |
|
| 36:35 | . Now the uh huh, they that it didn't matter too much for |
|
| 36:43 | . Petitioning method is used for the craft because it was small enough that |
|
| 36:49 | didn't matter whether they used something kind Lin refinement on the course craft and |
|
| 36:56 | around with moving stuff around or the spectral a section or other methods. |
|
| 37:04 | it's fairly arbitrary what you did. that case, it was small enough |
|
| 37:07 | it didn't matter. So neither in of running time nor in terms of |
|
| 37:13 | quality of the final petitioning. so any questions on this scheme on |
|
| 37:30 | graph partitioning? And I said, graph partitioning and well, I wouldn't |
|
| 37:44 | it was considered the solve problems for more than a decade. Uh, |
|
| 37:54 | it's kind of good enough that there that much research activity in terms of |
|
| 38:01 | petitioning. But in the last 5 10 years, that has picked up |
|
| 38:08 | . Mm, when both problems, machines has gotten significantly larger, and |
|
| 38:14 | come to that in a bit Now, in the early days, |
|
| 38:25 | , it's like a Mideast package and much all the other packages up There |
|
| 38:33 | are. This was sequential, so basically ran on a single note. |
|
| 38:38 | that means you couldn't really worked with that didn't fit on a single |
|
| 38:45 | So, um however, the spectral section that by myself, false |
|
| 38:52 | And we always did it. That's parallel partitioning methods. So we run |
|
| 38:58 | the few that actually did Carol So. But the media's people also |
|
| 39:02 | that so they now have. Oh known as far meetings for Carol Meters |
|
| 39:11 | again is available for download on the . But this line just that, |
|
| 39:17 | to point out there's a little bit to do things in parallel because if |
|
| 39:23 | look at the two, the top of the slide can see if each |
|
| 39:29 | looks at the degree off. No on the boundary here on they have |
|
| 39:34 | vino that has in three, the way three on the internal edge |
|
| 39:40 | to W. And then I was weight of five. So taking be |
|
| 39:45 | and putting it in partition J instead I well, then make this edge |
|
| 39:51 | weight five. The internal to the position, and that would reduce a |
|
| 39:58 | 23 from the connection from I to . Now, the Day guy position |
|
| 40:04 | make the same conclusion that if I you are to the other I petition |
|
| 40:11 | the weight would only be too. this, wait five will be on |
|
| 40:15 | other side. Now if they don't , then they both swapped. And |
|
| 40:21 | that case, in fact, things worse. You can say there's another |
|
| 40:27 | on the bottom. It's a similar . So it's you're trying to paralyze |
|
| 40:32 | . Then things becomes difficult, and may not work the way you hope |
|
| 40:39 | . And so one thing is to what it says on this slide |
|
| 40:43 | Thio, bit of serialization Z or just look at petitions, pair wise |
|
| 40:51 | based on that. But, it's no guarantee again that it actually |
|
| 40:56 | better. And how many integrations you need to do in this kind of |
|
| 41:02 | speak. Uh, on now here's just for reference to things and |
|
| 41:11 | So what, in the end, the outcome in terms of the skin |
|
| 41:15 | was used to be the parallel And they're not entirely small, but |
|
| 41:23 | giant either. Still, mostly engineering problems. So here is kind of |
|
| 41:30 | the graph along, referring to in off how things worked out. So |
|
| 41:37 | is basically that the parallel is equal doesn't equally good job in terms off |
|
| 41:45 | number of ages cut as serial And if things are above one, |
|
| 41:50 | means that the parallel petition did not the as well. But in this |
|
| 42:00 | , when I didn't think quite as , it didn't really change things all |
|
| 42:06 | much You can also notice, in case, actually, the parallel petition |
|
| 42:12 | somewhat better. And remember that this kind of has statistical effect. So |
|
| 42:19 | they ran it long enough for a in there, all the cases is |
|
| 42:25 | what it is, Uh, not iconic and what you do but in |
|
| 42:31 | , And when they did this serialization , uh, the privacy got the |
|
| 42:39 | petitioner to generally call it cuts qualities to their serial Albelda. And as |
|
| 42:53 | can guess, on the horizontal axis just a bunch of different press. |
|
| 43:05 | , any questions on that? We're about this now. So So this |
|
| 43:20 | the Minnesota teams on the things that they're especially worked with the current and |
|
| 43:26 | algorithm and then they this multilevel abortion the corner gone Lynn and they got |
|
| 43:34 | . The carnival in principle is very , as I mentioned when I talked |
|
| 43:40 | it. In practice, it seems converge in various reiterations, and that's |
|
| 43:45 | kingdoms. Varying computational lee competitive Petitioner Thio the spectral reception, but in |
|
| 44:00 | of the quality of the cuts and two of them are comparable. And |
|
| 44:05 | the spectral perception gave a better cut the multi level that generally took more |
|
| 44:13 | . So the spectral protection folks that a group at Sandia National Labs in |
|
| 44:21 | that question the spectral by section They also then did the multilevel version |
|
| 44:28 | their code and then, But they choose to do different courses and strategy |
|
| 44:35 | used, once known as maximum That's when they start trying to pick |
|
| 44:43 | instead. And that is find it maximum set of notes that are not |
|
| 44:55 | , connected to each other. Exactly how the outcome differs, respected |
|
| 45:02 | maximum edge matching. It's not intuitively to me, but they tried |
|
| 45:09 | and then they tried some refinement strategies well on in terms of the what's |
|
| 45:17 | a surveyor, coach and reiteration to petitions anyway, Here is kind of |
|
| 45:22 | administration of this maximum independent old sets that illustrated just for line graph. |
|
| 45:35 | it shows here. The DS then A knows that cats and them together |
|
| 45:40 | of course, the edition in But the picking is not based on |
|
| 45:45 | , but based on notes. So then, of course, is in |
|
| 45:50 | case. That's the way that a in der Graaff on that's a little |
|
| 46:00 | off. What I want to come . This in terms off this basic |
|
| 46:08 | petitioning where the graphics models by nodes edges and you try to minimize the |
|
| 46:16 | of edges cut. And, as mentioned the because of the computational |
|
| 46:29 | is trying to come in and pretended be the most widely used because it |
|
| 46:37 | fairly or relatively inexpensive compared to other and generic. Quite good. Uh |
|
| 46:45 | . Partitions, but sometimes got in spectrum. Method did a better |
|
| 46:51 | but it was stolen. Um, I will talk a lot about typographic |
|
| 47:04 | any questions. All right, so hyper graph is trying to capture other |
|
| 47:19 | that the simple graph model does And here's a few examples where the |
|
| 47:27 | graft model turns out to work somewhat in our area. The cartoonish slides |
|
| 47:38 | up to illustrate how this help a models, in fact, helps sometimes |
|
| 47:45 | better partitions. So I know some you interested in or know about general |
|
| 47:59 | . Sometimes when I triangular systems and not, um so that case, |
|
| 48:04 | turns out that the high program model a better job in terms so conditioning |
|
| 48:10 | English systems are still very highly So it was just a quick slide |
|
| 48:18 | reference more in terms of where am can find? Well, did what |
|
| 48:24 | does what in terms about software and on papers? I guess. |
|
| 48:37 | Here's what I'm a cartoonist. Examples to illustrate the point, so I |
|
| 48:45 | think it's necessarily the best. But simple. So and the we have |
|
| 48:53 | petitioning, modeling things. That's what and edges that is on the left |
|
| 48:59 | side. And then there is the of the hyper graph on the right |
|
| 49:02 | side. So it's fun things about . And there, one way to |
|
| 49:14 | off tried to point out the benefits terms of clusters. So if from |
|
| 49:21 | to do, the petitioning and just on figuring out edge cuts and assume |
|
| 49:28 | for each edge being cut in this , no one needs to be a |
|
| 49:33 | being sent between the partitions. um, in this case, on |
|
| 49:40 | left hand side, if you look this great point A than it does |
|
| 49:49 | left neighbor in the other petitions in lower right and left hand corners. |
|
| 49:55 | right, on then itself in the . Upper right hand corner petition. |
|
| 50:01 | also has a vertical edge going So in that case, you live |
|
| 50:07 | well, basically, send two messages what needs to be communicated between a |
|
| 50:15 | it's left neighbor. And yeah, and it's south neighbor. So the |
|
| 50:25 | and that in fact, the hyper than more than fact lump these two |
|
| 50:38 | together. Someone would not need todo messages now. So that's so in |
|
| 50:50 | , in this case, the hyper mall. Actually, I would say |
|
| 50:55 | appropriately what it does. It identifies number off grid notes that has a |
|
| 51:05 | in the other partition. Now, of the software packages, like in |
|
| 51:13 | , for instance, they are clever . Thio Figure out what messages goes |
|
| 51:22 | the the pair off, uh, and the clusters so it would not |
|
| 51:31 | the naive thing or sending things for one on the knows in the in |
|
| 51:37 | petition. But I would look at the entire set the messages that needs |
|
| 51:43 | go between to compute notes and package up as one message. And then |
|
| 51:52 | has to be unpackaged on the other to figure out what part of the |
|
| 51:59 | relevant for each one off the notes the measure. That is the logical |
|
| 52:04 | . That is the data. So even if it's not done in the |
|
| 52:11 | , some are software implementations. the emerging off messages sent to you |
|
| 52:19 | single message. And here's some other to kind of is quickly illustrates the |
|
| 52:27 | how things may then be carved up terms of very regular petition. Great |
|
| 52:33 | . Ondas did the normal graph modeling and edges. It will get something |
|
| 52:39 | on the left hand side if you a hyper graph type model. If |
|
| 52:44 | go get something that ends up looking like on the right hand side, |
|
| 52:49 | in this case you do see some , and there is kind of more |
|
| 52:58 | of huh? The outcome A different , uh, five point sensor we |
|
| 53:03 | used for the a Kobe conch reiteration . If one does typical grab petition |
|
| 53:12 | society to grab petition on. These small examples of the difference. Is |
|
| 53:18 | a giant or lost in problems that be significantly better. Oh, |
|
| 53:28 | I have this triangular example and officials in this case, um, this |
|
| 53:35 | of petitioning where in the hyper graph generates the better outcome than the latest |
|
| 53:44 | on the part tooth is another package bond that one can download. Don't |
|
| 53:50 | what the afternoon comes from. The was done by. And the fact |
|
| 53:56 | the member that now is Georgia I think. Okay, so this |
|
| 54:05 | more or less same. Some more on this particular graph. Um, |
|
| 54:15 | any questions on this is kind of couple of lord topics and tried to |
|
| 54:22 | before the end of the class. go fairly quickly, given that is |
|
| 54:30 | your orientation and either use for And then we can talk about it |
|
| 54:35 | in detail or enough for an Okay, so the next thing I |
|
| 54:48 | get three more sub topics. Large graphs s I mentioned. So both |
|
| 54:56 | science and engineering problems has gotten larger machines has cut the more powerful and |
|
| 55:02 | so today finite element problems may have of millions of elements and and more |
|
| 55:14 | think about the Internet and Web And they actually have for that |
|
| 55:27 | uh, hyperlinks for linking between what do in behaviors as well. A |
|
| 55:34 | networks than man gets into crafts that have billions of notes and edges. |
|
| 55:45 | in that case, things aren't seriously scale. So that's as I mentioned |
|
| 55:51 | while ago today that that got this problem to get renewed interest in terms |
|
| 55:59 | methods to do, petitioning for real skin grafts on for large scale |
|
| 56:06 | And again, these problems are then large enough that they can't fit in |
|
| 56:10 | notes of money. Also parallel approaches the partitioning, for sure, and |
|
| 56:19 | don't have many slides on it. have a collection references for on the |
|
| 56:27 | that is interested in diving into it a couple of examples chilling on. |
|
| 56:34 | things can be done and what can achieved so well, talk about this |
|
| 56:46 | for showing I've coming. That seems be one of the better ones that |
|
| 56:51 | the right emerged in the last few that is based on so called neighborhood |
|
| 57:05 | . So there are offices and age . So it was. The idea |
|
| 57:14 | to have petitions that has then roughly number off edges on. Then |
|
| 57:27 | um, the edges, incidentally note up in different petitions. That means |
|
| 57:38 | those both those petitions need, the noble values for whatever you're going |
|
| 57:45 | compute. So in this particular then they replicate representation off the nodes |
|
| 57:54 | falls on the boundary off partitions and through the replication, that it's important |
|
| 58:04 | for corrections on the algorithm that the off the note in the different |
|
| 58:11 | our instinct. So that means when kind of replicate notes that will eventually |
|
| 58:18 | communication between partitions. So I'm not to talk about the different methods |
|
| 58:27 | But there is one example from the that is referenced in the answer. |
|
| 58:36 | were at the right hand corner of light and, um, the top |
|
| 58:45 | table gives the name of particular graphs the aliens. That's name. They |
|
| 58:53 | them for this table below it. , it shows the size of the |
|
| 58:59 | . So in this case, the craft was about 130 million notes. |
|
| 59:06 | about what? Fire billions edges now the middle table or the table |
|
| 59:21 | That shows a column for each one the graph, and then you throw |
|
| 59:27 | that table is different petitioning methods and one so that this was still done |
|
| 59:34 | . And, uh, there's an algorithm. Okay, It also shows |
|
| 59:42 | metes, uh, have problems for of the graphs that are the larger |
|
| 59:49 | on the fun looks only in recent Air that again has tried to use |
|
| 59:56 | or car Nitties for petitioning and seems to have scaled very well. So |
|
| 60:04 | people get in trouble. So the methods here, um thio scale |
|
| 60:13 | Okay. Andi don't crash from the grass on that bottom role on the |
|
| 60:20 | . It's this, uh, neighborhood that is petitioned. The edge sets |
|
| 60:25 | , replicate notes on boundaries on and then see there how the running |
|
| 60:31 | scales and the waves quite well in off the running time. So the |
|
| 60:45 | exchanges a little bit more expensive, I can't remember then this then city |
|
| 60:50 | stations. But so the running. I guess they it's not compatible or |
|
| 61:03 | . And I look at it. didn't spot it before. Um, |
|
| 61:09 | the D B H seems to be running time. On the other |
|
| 61:11 | on the table it mm seems to a different story home. Sorry for |
|
| 61:21 | . Not paying attention over there when make this slide. And then I |
|
| 61:27 | , um, one more method that not done again by the Sandia, |
|
| 61:34 | 30 people that until the spectrum by method and software for it. And |
|
| 61:43 | not going to go into detail on one liner, but, um, |
|
| 61:49 | to illustrate a little bit of scalability they did get, um, so |
|
| 61:56 | the left graph on this slide, kind of purplish bluish nine on |
|
| 62:04 | That is for a Web data data set with a little bit of |
|
| 62:12 | three billion notes and about 128 billion . So it's a quite large graph |
|
| 62:22 | then the three curves below it on left hand side is for artificial. |
|
| 62:30 | graphs have to generate producing a few schemes from how to generate the |
|
| 62:35 | Um, graphs. Okay, but . Two point on the left hand |
|
| 62:42 | is to show a couple of things they got pretty good scalability and going |
|
| 62:48 | 256 to 2000 notes Not perfect fill your data or proportion. It's paid |
|
| 62:56 | , but not all that bad. sort of one other thing. And |
|
| 63:03 | other thing I want to emphasize here these three artificial graphs that they use |
|
| 63:10 | arm at around er and Rand HD , are, you know, running |
|
| 63:21 | on the comment I wanted to make some things, uh, it may |
|
| 63:33 | easy or it's a falsehood to believe random graphs are a bad. I |
|
| 63:39 | it's my point. Random graphs generally not represent anything worse case, and |
|
| 63:48 | may not even be particularly good approximation anything really like in this case, |
|
| 63:54 | went their comments. They that set Israel what data set. So when |
|
| 64:02 | news for simplicity many times when a time finding data use something created by |
|
| 64:12 | ization. Somehow that is closer. our claim some average case than any |
|
| 64:24 | of worst case so and interpreting results using randomized data. One should be |
|
| 64:34 | fast, and here's a little bit a slide comparing they're extra code two |
|
| 64:45 | meters. In that case, they . It used, um to look |
|
| 64:50 | the two columns, more or less the center. On the table, |
|
| 64:56 | can see that they're extra pulp approach considerably faster, and also it also |
|
| 65:04 | to do considerably larger graphs. Then I need this environment has managed to |
|
| 65:16 | and two more topics, I any questions or not. So I |
|
| 65:23 | , I'm There's a lots of new that I have not familiarize myself all |
|
| 65:30 | much. So it's mostly pointers. anyone interested in large scale graft related |
|
| 65:40 | problems that can remodel by graphs? can say many of these methods were |
|
| 65:50 | methods. Uh, we're actually invented created by people are interested in large |
|
| 66:01 | data basis and alright dynamics craft not quickly. Here is just a example |
|
| 66:12 | and in terms of what may happen and engineering problems of a finite |
|
| 66:18 | passions and something crashing. So in case, clearly when these to |
|
| 66:24 | um, both potentially regulated in terms the on a tenement mesh, but |
|
| 66:31 | also the distribution of measure all notes need to be changed depending upon what's |
|
| 66:37 | . So in that case, some of dynamic Russians necessary. So one |
|
| 66:45 | is again like here that I may to redistribute your mission. Um, |
|
| 66:51 | it also happens since she did molecular or astrophysical simulations that, ah, |
|
| 67:03 | planets particles molecules are distributed in space over time to carry and maintain low |
|
| 67:10 | . More, many to most suffer between computer built on the the petition |
|
| 67:19 | sort of the brute force where you just to start all over every |
|
| 67:22 | But that's kind of expensive, so are then different forms of incremental methods |
|
| 67:28 | try to take advantage of that one with the relatively good partition and kind |
|
| 67:37 | refine it or improve it. Respect . What's happening in your application and |
|
| 67:43 | are the same methods can be and there's also kind of what's sometimes |
|
| 67:51 | as diffusion methods that they're basically looking , um, readjusting the graph by |
|
| 68:02 | or diffusion equations effectively how things should . And I think that's what I |
|
| 68:12 | here. You have some packages that be used for dynamic partition. Uh |
|
| 68:19 | . I don't remember if Parma disguise made this ends all time, have |
|
| 68:25 | visit versions for dynamic or this Just . Yes. You can use |
|
| 68:31 | You have a starting point remembering course and refinement, etcetera. So we |
|
| 68:39 | certainly use what petition? Don't already . Thio cut out the number of |
|
| 68:47 | steps in the partitioning. And then more thing I wanted to bring |
|
| 68:56 | uh, trying to finish on time that cool iss spec Titian ing. |
|
| 69:05 | does things go? So everything I've so far is about partitioning the data |
|
| 69:14 | and trying thio related to the objective , yet no balance. And, |
|
| 69:25 | , minimize the amount off communication. , the communication is also depending on |
|
| 69:38 | the partitions ends up. Respect to communication networks that into connects the notes |
|
| 69:43 | the cluster. It's you are interested this, and you read papers. |
|
| 69:53 | of most of the papers that are in the the Star references thoroughly ignore |
|
| 70:04 | mapping park. Some of them actually mentioned that, yes, there is |
|
| 70:09 | to it than yes, partitioning So it's very important. Thio not |
|
| 70:18 | that when you look at potentials, know benchmarks are running tests that people |
|
| 70:28 | report both. What? The mapping Andi. Better yet, try to |
|
| 70:36 | out or interpret results in terms of ? Um, I think waas So |
|
| 70:43 | will just make a few comments on . So here is kind of what |
|
| 70:53 | called. I don't think there's unnecessarily interpretation on what they are except the |
|
| 71:01 | two confident natural order. So partitioning . You may end up having a |
|
| 71:13 | D or a number label on each . And then, of course, |
|
| 71:19 | compute notes also have an address or I. D. And so one |
|
| 71:25 | is basically to have partitions Map to compute notes, according Thio, the |
|
| 71:37 | identities. The other one I call because when you run your partitioning |
|
| 71:47 | um, implicitly in how things are done, there will be a partition |
|
| 71:53 | each. No, it does not mean that they're ordered, according to |
|
| 72:01 | I labeled natural order. But they somewhere. No one of those two |
|
| 72:11 | to be map ings that reduce congestion the network or Leighton. See, |
|
| 72:21 | not necessarily clear they can be bad they can be good. The other |
|
| 72:29 | that is recently well define is randomly petitions to notes, the computer |
|
| 72:38 | and third, more sophisticated. One to do that for a map where |
|
| 72:44 | or partitions two notes and people have it with some resource managers. And |
|
| 72:51 | don't know of any one of the managers that are typically installed. In |
|
| 72:57 | , that does. That you may , in terms off the M. |
|
| 73:02 | I and that I talked about certain on the mapping was left open for |
|
| 73:10 | . Implementer is to potentially find out about the interconnection networks in map processes |
|
| 73:17 | them. So been in Eastern. , give a couple of examples. |
|
| 73:24 | s Oh, this is from the people. Um, there's on the |
|
| 73:29 | that happens to be three on the is just too different graphs that they |
|
| 73:37 | . And I just want to focus the collard boxes and in this |
|
| 73:44 | for 128 partitions. Case for the and the arbitrary mapping is exactly what |
|
| 73:56 | partitioning happened to result or whatever machine was run on, and they gave |
|
| 74:03 | one particular time to do this problem the bottom table. The corresponding 1 |
|
| 74:11 | petitions for the autograph has two other and the random assignment that more or |
|
| 74:18 | gave the same as the kind of . But then it is truly randomized |
|
| 74:24 | . And then there's a pre partitioning you try to be clever about how |
|
| 74:29 | map the partitions onto the Nolde. what the interaction between partitions are |
|
| 74:38 | In this case, the random and ended up being pretty similar both for |
|
| 74:44 | auto and for the and the world graphs. And in both cases, |
|
| 74:52 | somewhat network career mapping did, got a job. I have something |
|
| 75:02 | my own experience from way back, , in which case there was kind |
|
| 75:07 | small problems and use and find the stuff. And in this case, |
|
| 75:12 | , it turned out that the random did better than whatever the default were |
|
| 75:22 | . To use the same word as the previous, uh, slides generated |
|
| 75:28 | terms off. Well, running time the communication part together is kinda operations |
|
| 75:38 | . There's a gun showing what the for the same machine that random medications |
|
| 75:43 | this case did a much better So random allocations again and not the |
|
| 75:53 | case it's actually tend to be a case has appointed out from the previously |
|
| 76:00 | what comes out of there. Whatever out of the petition may not be |
|
| 76:06 | that great. I think that's there's 11 more example showing in terms off |
|
| 76:15 | on the random mapping. Most cases have time or in the worst, |
|
| 76:20 | least than so. That turned up this machine. A random ization cost |
|
| 76:25 | congestion in the interconnection, of Yeah, and it's just in the |
|
| 76:30 | . Excited that. And I think what I had for today, and |
|
| 76:35 | time is really up. But I'll questions. So these are packages out |
|
| 76:46 | that I encourage you to take a at. If you are doing in |
|
| 76:52 | large escape problems now or in the , at least you have a reference |
|
| 76:57 | starting point so and stop |
|
