[petsc-users] Grid Partitioning with ParMetis
Mohammad Mirzadeh
mirzadeh at gmail.com
Thu Jul 28 23:52:33 CDT 2011
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?
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110728/81e6f267/attachment-0001.htm>
More information about the petsc-users
mailing list