[petsc-users] Grid Partitioning with ParMetis

[Matthew Knepley]

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/20110729/11eae3ea/attachment.htm>