On Fri, Jul 29, 2011 at 7:52 PM, Mohammad Mirzadeh <mirzadeh at gmail.com>wrote:
> Matt, > > Is ParMetis implementation in PETSc only done via > $PETSC_DIR/src/mat/partition/impls/pmetis/pmetis.c ? I am wondering if PETSc > has interface to ParMETIS_V3_RefineKway function as noted in ParMetis > manual? > If you want to Mat, then pmetis.c is it. There is stuff for more general meshes, but it is experimental. There is a paper about it http://arxiv.org/abs/0908.4427 which will give you an idea what it does. Thanks, Matt > Thanks, > Mohammad > > > On Thu, Jul 28, 2011 at 10:11 PM, Mohammad Mirzadeh <mirzadeh at > gmail.com>wrote: > >> I see. Thanks for the help Matt >> >> >> On Thu, Jul 28, 2011 at 10:01 PM, Matthew Knepley <knepley at >> gmail.com>wrote: >> >>> On Fri, Jul 29, 2011 at 4:52 AM, Mohammad Mirzadeh <mirzadeh at >>> gmail.com>wrote: >>> >>>> Thank you Matt. Indeed I have looked into p4est and also Dendro. p4est >>>> uses parallel octrees/quadtrees but for what I intend to do I only need to >>>> distribute a single tree that is created in serial among processors. >>>> I definitely like to have the tree data-structure in parallel but that >>>> would >>>> be another project. I also looked into Dendro and they kind of follow the >>>> same strategy. i.e every single processor has a local copy of the whole >>>> tree. What they do differently, however, is they somehow manage to use DA >>>> instead of a general unstructured numbering which is quite interesting but >>>> I >>>> still don't know how they do it. Unfortunately, they do not handle (as far >>>> as I understood from their manual) non-graded trees which are the ones I >>>> work with. >>>> >>>> So, all I need to do is to somehow distribute my grid among processors >>>> and since each one has a local copy of data-structure I could get around >>>> the >>>> problem. Just anotehr question. If the partitioning is not unique, do you >>>> at >>>> least get a better numbering than the tree you start with? >>>> >>> >>> You should, which is why I suggested that you are not giving the input >>> you think you are. >>> >>> Matt >>> >>> >>>> Mohammad >>>> >>>> >>>> On Thu, Jul 28, 2011 at 9:25 PM, Matthew Knepley <knepley at >>>> gmail.com>wrote: >>>> >>>>> On Fri, Jul 29, 2011 at 3:49 AM, Mohammad Mirzadeh <mirzadeh at gmail.com >>>>> > wrote: >>>>> >>>>>> Hi all, >>>>>> >>>>>> I am trying to write a code to do parallel computation on quadtree >>>>>> adaptive grids and to do so , I need to distribute the grid in parallel. >>>>>> I >>>>>> have selected a general unstructured framework for telling PETSc about my >>>>>> node numbering. An example of such grid is schematically shown below. >>>>>> >>>>> >>>>> 0) If you are doing this, I think you should at least look at the p4est >>>>> package before proceeding. >>>>> >>>>> >>>>>> >>>>>> 1 16 7 3 >>>>>> +---------------+---------------+------------------------------+ >>>>>> | | | | >>>>>> | | | | >>>>>> |14 | 15 | 17 | >>>>>> +---------------+---------------+ | >>>>>> | | | | >>>>>> | | | | >>>>>> | 4 | 12 | 6 |8 >>>>>> +---------------+---------------+------------------------------+ >>>>>> | | | | >>>>>> | | | | >>>>>> | 9 | 11 | 13 | >>>>>> +---------------+---------------+ | >>>>>> | | | | >>>>>> | | | | >>>>>> | 0 | 10 |5 | 2 >>>>>> +---------------+---------------+------------------------------+ >>>>>> >>>>>> >>>>>> To distribute this in parallel I am using the ParMetis interface via >>>>>> MatPartitioning object and I follow(more or less) the example in >>>>>> $PETSC_DIR/src/dm/ao/examples/tutorials/ex2.c; To make the initial >>>>>> distribution, I choose nodal based partitioning by creating the >>>>>> adjacency matrix, for which I create ia and ja arrays accordingly. once >>>>>> the grid is processed and the new orderings are generated, I follow all >>>>>> required steps to generate the AO needed to map between PETSc ordering >>>>>> and the new global numbering and this is the result: >>>>>> >>>>>> >>>>>> Number of elements in ordering 18 >>>>>> PETSc->App App->PETSc >>>>>> 0 9 0 1 >>>>>> 1 0 1 3 >>>>>> 2 10 2 4 >>>>>> 3 1 3 7 >>>>>> 4 2 4 12 >>>>>> 5 11 5 14 >>>>>> 6 12 6 15 >>>>>> 7 3 7 16 >>>>>> 8 13 8 17 >>>>>> 9 14 9 0 >>>>>> 10 15 10 2 >>>>>> 11 16 11 5 >>>>>> 12 4 12 6 >>>>>> 13 17 13 8 >>>>>> 14 5 14 9 >>>>>> 15 6 15 10 >>>>>> 16 7 16 11 >>>>>> 17 8 17 13 >>>>>> >>>>>> Now I have two questions/concerns: >>>>>> >>>>>> 1) Do processors always have the nodes in contiguous chunks of PETSc >>>>>> ordering? i.e 0-8 on rank 0 and 9-17 on rank 1 ? If so, this particular >>>>>> ordering does not seem to be "good" for this grid since it seems to cross >>>>>> too many edges in the graph (here 13 edges) and by just looking at the >>>>>> graph >>>>>> I can(at least) think of a better distribution with only 6 edge cuts. (if >>>>>> you are wondering how, having {0,9,4,14,1,10,11,12,15} on rank 0 and >>>>>> rest on >>>>>> rank 1). >>>>>> >>>>> >>>>> Yes, the PETSc ordering is always contiguous. Perhaps you are not >>>>> providing the graph you think you are for partitioning. >>>>> >>>>> >>>>>> 2) Isn't it true that the final distribution should be independent of >>>>>> initial grid numbering? When I try the same grid but with the following >>>>>> (hand-generated) numbering: >>>>>> >>>>>> 14 15 16 17 >>>>>> +---------------+---------------+------------------------------+ >>>>>> | | | | >>>>>> | | | | >>>>>> |11 | 12 | 13 | >>>>>> +---------------+---------------+ | >>>>>> | | | | >>>>>> | | | | >>>>>> | 7 | 8 | 9 |10 >>>>>> +---------------+---------------+------------------------------+ >>>>>> | | | | >>>>>> | | | | >>>>>> | 4 | 5 | 6 | >>>>>> +---------------+---------------+ | >>>>>> | | | | >>>>>> | | | | >>>>>> | 0 | 1 |2 | 3 >>>>>> +---------------+---------------+------------------------------+ >>>>>> >>>>>> I get the following AO: >>>>>> >>>>>> Number of elements in ordering 18 >>>>>> PETSc->App App->PETSc >>>>>> 0 9 0 9 >>>>>> 1 10 1 10 >>>>>> 2 11 2 11 >>>>>> 3 12 3 12 >>>>>> 4 13 4 13 >>>>>> 5 14 5 14 >>>>>> 6 15 6 15 >>>>>> 7 16 7 16 >>>>>> 8 17 8 17 >>>>>> 9 0 9 0 >>>>>> 10 1 10 1 >>>>>> 11 2 11 2 >>>>>> 12 3 12 3 >>>>>> 13 4 13 4 >>>>>> 14 5 14 5 >>>>>> 15 6 15 6 >>>>>> 16 7 16 7 >>>>>> 17 8 17 8 >>>>>> >>>>>> >>>>>> which is simply the initial ordering with a change in the order in >>>>>> which processors handle nodes. Could it be that the partitioning is not >>>>>> unique and each time the algorithm only tries to obtain the "best" >>>>>> possible >>>>>> ordering depending on the initial distribution? If so, how should I know >>>>>> what ordering to start with? >>>>>> >>>>> >>>>> Yes, ParMetis does not provide a unique "best" ordering, which is at >>>>> least NP-complete if not worse. >>>>> >>>>> Matt >>>>> >>>>> >>>>>> I am really confused and would appreciate if someone could provide >>>>>> some insights. >>>>>> >>>>>> Thanks, >>>>>> Mohammad >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> What most experimenters take for granted before they begin their >>>>> experiments is infinitely more interesting than any results to which their >>>>> experiments lead. >>>>> -- Norbert Wiener >>>>> >>>> >>>> >>> >>> >>> -- >>> What most experimenters take for granted before they begin their >>> experiments is infinitely more interesting than any results to which their >>> experiments lead. >>> -- Norbert Wiener >>> >> >> > -- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110729/c1c27dc4/attachment.htm>
