ParMETIS (4.0.3) PartKway returns discontiguous partitions with "large" number of MPI tasks
Dear all,
I am using ParMETIS (version 4.0.3) to partition in parallel
the dual graph of a finite element mesh with 8.75M tetrahedra.
In particular, I build the dual graph on my own, and then
call ParMETIS graphpartkway subroutine to partition it into
the same number of parts as MPI tasks involved in the parallel
computation. The dual graph is constructed in such a way that
two vertices are neighbours if and only if the corresponding tetrahedra
share a face. I am using ncon==1, no vertex/edge weights nor tpwgts,
and ubvec=1.10.
With this set-up, I am obtaining discontiguous partitions
with 1024 MPI tasks/partitions and beyond. I am aware that
ParMETIS 4.0.3 does not ensure contiguous partitions, but ...
1) Is there any algorithm set-up that favours contiguous
partitions? I have tried defining NGR_PASSES to 20 (instead of 4)
in defs.h without success. I also tried to replace the
parallel recursive bisection at the coarsest level by a replicated
on all processors METIS 5.x partkway with METIS_OPTION_CONTIG enabled,
also without success (i.e., it seems uncoarsening/refining to be
the source of discontiguity).
2) Would it be so hard to write a message-passing code that tries to
enforce contiguous partitions afterwards as it is done in METIS 5.x
when METIS_OPTION_CONTIG is enabled ?
Find at
http://www3.uji.es/~martina/part117_discont.png
a picture showing how does a discontiguous partition
looks like. It is the local finite element mesh corresponding
to part. id 117. Note that in the bottom-right corner, there are two
tetrahedra sharing only one corner; these two tetrahedra are
DISCONNECTED in the dual graph. This kind of situation can lead to
singularities in the solution of
local Neumann problems in domain decomposition solvers (the ones that
are fed by the finite element mesh partition computed by ParMetis).
Thanks for your support.
Best regards,
Alberto.
Submitted by amartin on Fri, 2013-11-01 12:28
»
- Login to post comments
RE: ParMetis can produce
ParMetis can produce disconnected partitions as it does not enforce any connectivity constraints.
RE: RE: ParMetis can produce
That's it? There is nothing one can do at least to favour contiguous partitions via e.g., parameter values?
RE: Unfortunately there is none.
Unfortunately there is none. The serial Metis does have that option, but not ParMetis.
RE: Unfortunately there is none
Thanks for your response.
I have been taking a look at the code that enforces contiguous partitions in METIS, and I have the feeling that it would be quite hard to develop this code within ParMETIS given the constraints imposed by the distributed-memory environment (due to the lack of a global view of the problem). Isn`t it? Have you got any idea about how this problem could be solved in an efficient way?
Thanks.
Best regards,
Alberto.
RE: Moving Metis' algorithm in
Moving Metis' algorithm in ParMetis is non-trivial (this is why it is not there).
As far as an "engineering" solution that you may want to try out, is to do the partitioning using some form of a repeated k-section, in which k is > 2 and < # of final partitions. However, if your mesh is rather small compared to the # of partitions that you want to compute, then the above may be of little help.
RE: Thanks for your
Thanks for your response.
This is precisely the "solution" that we had in mind. In particular, in a first partitioning level, use the minimum number of MPI tasks such that the problem fits into available memory, to generate as many # of partitions. In a second partitioning level, call METIS whithin each MPI task (with METIS_OPTION_CONTIG enabled), to generate the rest of partitions.
Best regards,
Alberto.