[petsc-users] Grid Partitioning with ParMetis
Mohammad Mirzadeh
mirzadeh at gmail.com
Fri Jul 29 16:58:15 CDT 2011
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>
More information about the petsc-users
mailing list