Thanks Matt for your help and support. I read a little on ParMetis manual and looked at PETSc implementation and I think I figured out the source of my confusion.
The fact is, ParMetis does create a good partitioning starting from the initial numbering. Indeed according to their manual for ParMetis 3.2 and on page 5: "... ParMETIS_V3_PartKway makes no assumptions on how the graph is initially distributed among the processors. It can effectively partition a graph that is randomly distributed as well as a graph that is well distributed . If the graph is initially well distributed among the processors, ParMETIS_V3_PartKway will take less time to run. However, the quality of the computed partitionings does not depend on the initial distribution." The problem that I was having was looking at the final AO and assuming that nodes 0-8 are on rank 0 and 9-17 on rank 1 of the *new partitioned grid. *This is wrong since "ISPartitioningToNumbering()" generates an index set "is" such that "on each processor the index set that defines the global numbers (in the new numbering) for all the nodes currently (before the partitioning) on that processor". In other words, I still need to change the numbering such that each processors has the newly computed numbers! This whole thing is little bit too confusing! Anyway, I think the problem is solved now. Thanks again for the help, Mohammad On Fri, Jul 29, 2011 at 2:09 PM, Matthew Knepley <knepley at gmail.com> wrote: > 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/537f0f75/attachment-0001.htm>
