<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Nov 9, 2017 at 5:53 AM, Vaclav Hapla <span dir="ltr"><<a href="mailto:vaclav.hapla@erdw.ethz.ch" target="_blank">vaclav.hapla@erdw.ethz.ch</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word">Thanks for the discussion. I think we got further.<div><br><div><blockquote type="cite"><div>8. 11. 2017 v 20:42, Matthew Knepley <<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>>:</div><span class="gmail-"><br class="gmail-m_-8114702957742201447Apple-interchange-newline"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote">On Wed, Nov 8, 2017 at 2:27 PM, Jed Brown<span class="gmail-m_-8114702957742201447Apple-converted-space"> </span><span dir="ltr"><<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>></span><span class="gmail-m_-8114702957742201447Apple-converted-space"> </span>wrote<wbr>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-m_-8114702957742201447HOEnZb"><div class="gmail-m_-8114702957742201447h5">Matthew Knepley <<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>> writes:<br><br>> On Wed, Nov 8, 2017 at 1:49 PM, Jed Brown <<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>> wrote:<br>><br>>> Matthew Knepley <<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>> writes:<br>>><br>>> >> > No, this is the right structure.<br>>> >><br>>> >> Oh come on. You're defending a quadratic algorithm.<br>>> >><br>>> >> ierr = ParMETIS_V3_PartKway(vtxdist, xadj, adjncy, vwgt, adjwgt,<br>>> >> &wgtflag, &numflag, &ncon, &nparts, tpwgts, ubvec, options, &edgeCut,<br>>> >> assignment, &comm);<br>>> >> // ...<br>>> >> for (p = 0, i = 0; p < nparts; ++p) {<br>>> >> for (v = 0; v < nvtxs; ++v) {<br>>> >> if (assignment[v] == p) points[i++] = v;<br>>> >> }<br>>> >> }<br>>> >><br>>> >> MatPartitioningApply creates an IS with "assignment" and can be<br>>> >> converted to a global numbering with ISPartitioningToNumbering. You<br>>> >> could as well have an ISPartitioningToSectionAndIS() that produces your<br>>> >> representation, preferably without this silly quadratic algorithm.<br>>> >><br>>> ><br>>> > Time it. Tell me if it matters. Telling me it matters in the long run is<br>>> > metaphysics.<br></div></div></blockquote></div></div></div></div></span></blockquote><div><br></div><div><span style="font-family:Menlo-Regular">Jed replied exactly what I needed to know - whether there's some easy conversion from the natural IS output of MatPartitioningApply into IS+PetscSection DMPlexDistribute needs. He showed there actually is a way, and it won't have worse performance (theoretical performance benefit). Moreover, what you do now for every PetscPartitioner implementation (all those "Convert to PetscSection+IS" blocks) would be done just in one place (design benefit). In this context, the request for timing was slightly unfair, I think.</span></div><div><div class="gmail-h5"><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-m_-8114702957742201447HOEnZb"><div class="gmail-m_-8114702957742201447h5">>><br>>> I realize ParMETIS isn't scalable and that if you have a modest number<br>>> of parts and only a million or so elements per rank, the cost of what<br>>> you do here will be acceptable for most uses.<br>>><br>>> But you didn't refute my point that ISPartitioningToSectionAndIS can<br>>> produce the representation you want.<br>><br>><br>> I do not think its an either or thing. Many equivalent interfaces are<br>> possible,<br>> so I should have told Vaclav "I think this is the right one", but I thought<br>> that<br>> was implicit in me being the responder, and none of us thinking that there<br>> is<br>> a true "right" in interface design.<br>><br>><br>>> The IS you're creating is similar<br>>> to the inverse of the Numbering (which is a permutation). You are the<br>>> one that replaced a scalable algorithm that has existed for a long time<br>>> and uses types correctly with PetscPartitioner which has some ugly<br>>> warts, duplicates a lot of code, and isn't a viable replacement for<br>>> MatPartitioning.<br>><br>><br>> 1) MatPartitioning is not a replacement for what I do. According to you,<br>> that<br>> should end the argument right there.<br>><br>> 2) Deep inside MatPartitioning, it must split things up as I do in order to<br>> pack<br>> stuff to be sent. I think it should be exposed as I have done.<br><br></div></div>Pack what stuff to be sent? PetscPartitionerPartition() takes the<br>arguments to ParMETIS directly as arrays. To use MatPartitioning, you<br>pass those same arrays to MatCreateMPIAdj which literally just holds the<br>pointers. Then MatPartitioningApply passes those on to ParMETIS or<br>whichever partitioning package. PetscPartitionerPartition_*<br>implementations depends on DM strictly as a way to define the weights.<br>That isn't more general or better; it's more restrictive.<br></blockquote></div></div></div></div></blockquote><blockquote type="cite"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>This sounds like deliberate misunderstanding. We are not talking about the input to</div><div>ParMetis, but the output. The biggest shortcoming of ParMetis (and indeed all mesh</div><div>partitioners) is that they tell you what must move, but do not move it. This is the value</div><div>add of Plex, it moves the mesh (including all connectivity) and the field data according</div><div>to the partition. In order to do this communication, you always want the partition segmented</div><div>by rank, as it is in the Section/IS output.</div></div></div></div></div></blockquote><div><br></div></div></div><div>I think we are talking here about both input and output!</div><div><div><br></div><div><font face="Menlo-Regular">What PetscPartitionerPartition actually does is getting the adjacency information from the DM using</font></div><div><font face="Menlo-Regular">DMPlexCreatePartitionerGraph(<wbr>DM dm, PetscInt height, <wbr>PetscInt *numVertices, <wbr>PetscInt **offsets, PetscInt *<wbr>*adjacency, IS *<wbr>globalNumbering)</font></div><div><font face="Menlo-Regular">and these raw arrays are then passed to</font></div><div><font face="Menlo-Regular">(*part->ops->partition)(part, dm, size, numVertices, start, adjacency, partSection, partition);</font></div><div><span style="font-family:Menlo-Regular"><br></span></div><div><span style="font-family:Menlo-Regular">This I don't like from couple of reasons:</span></div><div><span style="font-family:Menlo-Regular">1) the type-specific function has completely different arguments than the interface function - this is slightly non-standard, and if you talk about exposing, there should be an interface function with these arguments</span></div><div><font face="Menlo-Regular">2) on the other hand you derive IS+PetscSection output from the "raw" partitioner output inside each <wbr>PetscPartitionerPartition_* <wbr>separately </font><span style="font-family:Menlo-Regular">("Convert to PetscSection+IS" blocks)</span></div><div><span style="font-family:Menlo-Regular">3) so </span><span style="font-family:Menlo-Regular">part->ops->partition</span><span style="font-family:Menlo-Regular"> mixes "raw" inputs and "derived" outputs which sounds messy </span></div><div><br></div><div><font face="Menlo-Regular">I fully agree with Jed (and it seems it's compatible with Barry and Lisandro) this should be doable in a clearer way using </font><span style="font-family:Menlo-Regular">MatCreateMPIAdj</span><font face="Menlo-Regular">, MatPartitioningSetAdjacency, </font><span style="font-family:Menlo-Regular">M<wbr>atPartitioningApply, </span><span style="font-family:Menlo-Regular">ISPartiti<wbr>oningToSectionAndIS (the latter to be done)</span><span style="font-family:Menlo-Regular">.</span></div></div><span class="gmail-"><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I see no reason why PetscPartitioner cannot be implemented as a very<br>small amount of code around MatPartitioning (little more than the<br>interface function). The opposite would necessarily bring in concepts<br>like DM that are unnecessary when a user is partitioning matrices and<br>graphs.</blockquote><div><br></div><div>I am not arguing that it should not be done. I am saying</div><div> - I do not want to do it, because the payoff is small</div><div> - I do not want it to break anything that currently works</div><div> - I do not want it to break the interface we currently have to PetscPartitioner because I think it is genuinely good</div></div></div></div></div></blockquote><div><br></div></span><div>I think the payoff isn't necessarily small. Just imagine how much code could be avoided for further maintenance, or if there would be some new partitioner we wanted to interface. And I think the code much clearer to anyone who wants to learn how it works or even improve something.</div><div><br></div><div>I'm not that afraid about breaking. Grep tells me there's exactly one call to <span style="font-family:Menlo-Regular">PetscPartitionerPartition in whole PETSc - in </span><font face="Menlo-Regular">DMPlexDistribute.</font></div><div><br></div><div>One thing I always liked on PETSc is a culture of not sticking to status quo!</div><span class="gmail-"><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span>> 3) I think you exaggerate the faults of the code for effect. Do what you<br>> must.<br>><br>><br>>> And now you seem to be arguing against Vaclav unifying<br>>> it, claiming technical rationale that don't appear to hold up.<br>><br>><br>> Of course, I disagree with you, and think you make no attempt to understand<br>> why<br>> someone would write this code, because you never solve the problems its<br>> necessary<br>> for.<br></span></blockquote></div></div></div></div></blockquote><div><br></div></span><div>I understand you spent the most time with DMPlex, and it's a masterpiece! But it can always be beneficial to take into account a fresh view of someone who was not involved before.</div><div><br></div><div>I think I need to create a proof-of-concept. I would start by employing MatPartitioning in PetscPartitionerPartition with anything outside of this function untouched for now (as already suggested in #192), if you agree.</div><div><br></div><div>Or what about implementing a special temporary PetscPartitioner implementation wrapping MatPartitioning?</div><div>PETSCPARTITIONERMATPARTITIONIN<wbr>G sounds crazy, though :) But could be a good starting point.</div></div></div></div></blockquote><div><br></div><div>This is probably easier, and allows nice regression testing, namely run all tests using EXTRA_OPTIONS="-petscparitioner_type matpartitioning". I think</div><div>that should be alright for correctness. There are some parallel redistribution tests in Plex.</div><div><br></div><div>We will need at least one performance regression. Look at how I do it here:</div><div><br></div><div> <a href="https://bitbucket.org/petsc/petsc/src/312beb00c9b3e1e8ec8fac64a948a1af779da02f/src/dm/impls/plex/examples/tests/ex9.c?at=master&fileviewer=file-view-default">https://bitbucket.org/petsc/petsc/src/312beb00c9b3e1e8ec8fac64a948a1af779da02f/src/dm/impls/plex/examples/tests/ex9.c?at=master&fileviewer=file-view-default</a></div><div><br></div><div>You can make custom events, directly access the times, and compare. You could run the two versions</div><div>and check for degradation for a sequence of meshes in parallel.</div><div><br></div><div> Thanks,</div><div><br></div><div> Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><div><div>Thanks</div><span class="gmail-HOEnZb"><font color="#888888"><div><br></div><div>Vaclav</div></font></span><span class="gmail-"><br><blockquote type="cite"><div><div dir="ltr" style="font-family:Menlo-Regular;font-size:11px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span><br></span>I have written a parallel unstructured FEM that did this sort of<br>partitioning and redistribution on the fly. I wrote it in terms of<br>MatPartitioning and it worked fine. I abandoned it because it had<br>screwy dependencies and you had abandoned Sieve to work on<br>DMComplex/DMPlex. I'm happy to have made that change, but the concepts<br>and requirements are hardly foreign to me.</blockquote><div><br></div><div>Worked fine for you :) It always different with other people.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span>>> I don't<br>>> understand why, but it certainly looks like PetscPartitioner can be<br>>> implemented as a thin layer around MatPartitioning, then that layer can<br>>> be refactored into helper functions at the IS/PetscSection level.<br>><br>><br>> It might be true. To me, it looked like Mat stuff was draped on so it would<br>> be hard<br>> to pull the raw result out of the partitioner, and that things would get<br>> created (like<br>> the MatMult Scatter) which I did not want.<br><br></span>Barry created the MPIADJ representations in 1997 precisely for this purpose.<br></blockquote></div><br>Fair.</div><div class="gmail_extra"><br></div><div class="gmail_extra"> Matt<br clear="all"><div><br></div>--<span class="gmail-m_-8114702957742201447Apple-converted-space"> </span><br><div class="gmail-m_-8114702957742201447gmail_signature"><div dir="ltr"><div><div dir="ltr"><div>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</div><div><br></div><div><a href="http://www.caam.rice.edu/~mk51/" target="_blank">https://www.cse.buffalo.edu/~<wbr>knepley/</a></div></div></div></div></div></div></div></div></blockquote></span></div><br></div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>-- Norbert Wiener</div><div><br></div><div><a href="http://www.caam.rice.edu/~mk51/" target="_blank">https://www.cse.buffalo.edu/~knepley/</a><br></div></div></div></div></div>
</div></div>