[petsc-users] Grid Partitioning with ParMetis
Matthew Knepley
knepley at gmail.com
Fri Jul 29 16:09:21 CDT 2011
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>
More information about the petsc-users
mailing list