[petsc-users] ParMETIS_V3_PartGeomKway

Thu Feb 16 16:06:39 CST 2012

Thanks everyone for participating in the discussion. I really appreciate
it. I guess I'm gonna describe the problem more in details here. So
basically I use parmetis to partition my quadtree grid (we have previously
talked about why i'm not using p4est right now). Please see figures for a
sample amr quadtree grid.

For most cases, the partition quality that I get is reasonable like the one
for the smaller grid (maximum level of amr = 4) where I have color-coded
the grid points according to their proc_id (0, 1, 2 and 3) , both before
and after the partitioning. In this case, the program tells me that:

[0] # of edge cuts: 35
[1] # of edge cuts: 35
[2] # of edge cuts: 35
[3] # of edge cuts: 35
[0] Before: # of ghost Nodes: 35
[1] Before: # of ghost Nodes:  29
[2] Before: # of ghost Nodes:  35
[3] Before: # of ghost Nodes:  23
[0] After: # of ghost Nodes:  17
[1] After: # of ghost Nodes:  20
[2] After: # of ghost Nodes:  17
[3] After: # of ghost Nodes:  16

Now, the partitioning is quite good and number of ghost points required
have been dropped after partitioning is applied. However, if i run the code
for a larger grid (maximum amr level = 8), the partitioning that I get is
actually worse than the initial numbering i started with (well at least for
proc 0, 1, 2)

[0] # of edge cuts: 67
[1] # of edge cuts: 67
[2] # of edge cuts: 67
[3] # of edge cuts: 67
[0] Before: # of ghost Nodes:  58
[1] Before: # of ghost Nodes:  67
[2] Before: # of ghost Nodes:  62
[3] Before: # of ghost Nodes:  44
[0] After: # of ghost Nodes:  103
[1] After: # of ghost Nodes:  115
[2] After: # of ghost Nodes:  81
[3] After: # of ghost Nodes:  28

as you can see for proc 0, 1, and 2 the number of required ghost points
have been doubled which means more communication. To me, this should not
happen (maybe i'm wrong here?). That's why i asked if minimizing edge cuts
does not translate to having fewer ghost points.

Does minimizing latency favors creating 'clustered chunks' of points for
each processor and if so, could that create a partitioning with more ghost
points?

One final point, I'm not sure how parmetis is calculating the edge cuts,
but if you simply count the number of cuts in the smaller graphs, you don't
get the reported numbers. why is that? (for instance proc 3, cuts 20 edges,
including extra 'diagonal' ones at the coarse-fine interfaces but parmetis
reports 35-- i can explain this more in details if needed)

thanks,
Mohammad

On Thu, Feb 16, 2012 at 6:21 AM, Mark F. Adams <mark.adams at columbia.edu>wrote:

>
> On Feb 16, 2012, at 8:46 AM, Matthew Knepley wrote:
>
> On Thu, Feb 16, 2012 at 7:43 AM, Gerard Gorman <g.gorman at imperial.ac.uk>wrote:
>
>> Matthew Knepley emailed the following on 16/02/12 13:29:
>> > On Thu, Feb 16, 2012 at 3:38 AM, Mohammad Mirzadeh <mirzadeh at gmail.com
>> > <mailto:mirzadeh at gmail.com>> wrote:
>> >
>> >     Hi guys,
>> >
>> >     I'm wondering if there is any implementation
>> >     for ParMETIS_V3_PartGeomKway()? All I can find is the
>> >     implementation for ParMETIS_V3_PartKway and I'm wondering if
>> >     including the vertex positions could help me get a better
>> >     partitioning?
>> >
>> >
>> > As far as communication goes, it will not help.
>> >
>> >
>> >     Also I have a general question. Is minimizing number of edge cuts
>> >     essentially the same as minimizing communication? I understand
>> >     that they are related, but communication is proportional to the
>> >     number of ghost points which is not exactly equal (its actually
>> >     less than) to the number of edge cuts. So then is it possible that
>> >     this could actually result in larger number of ghost points, at
>> >     least for some of processors?
>> >
>> >
>> > It of course depends on your problem and the graph you draw, but you
>> > can always draw a graph
>> > where the edge cut is exactly your communication.
>> >
>> >
>>
>>
>> It might also be interesting to look at Zoltan's hypergraph partitioning
>> which can better balance communications -
>> http://www.cs.sandia.gov/zoltan/dev_html/dev_phg.html
>
>
> I would caution you that one thing people are rarely careful about is
> quantifying the effect of
> latency vs communication volume. I would bet you $10 that the lion's share
> of slow down is
> due to load imbalance/latency rather than communication volume (since comm
> links are so
> big).
>
>
> Just to add, edge cuts are a good proxy for communication volume on PDE
> graphs, IMO, but they are not the same and I applaud Zoltan for optimizing
> this directly.  Both edge cuts and #ghosts are decent metrics to indirectly
> minimize number of partition neighbors (latency).   As Matt says this is
> probably what you want to minimize, assuming good load balance.
>
> Furthermore you don't really want to minimize any of these.  What you want
> to minimize is the maximum cuts/neighbors/load of an any partition -- that
> is load balance (max/optimal).
>
> Mark
>
>    Matt
>
>
>>
>> Cheers
>> Gerard
>>
>>
>
>
> --
> 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/20120216/9d81778f/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: new_4_1.jpg
Type: image/jpeg
Size: 132607 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120216/9d81778f/attachment-0004.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: old_4_1.jpg
Type: image/jpeg
Size: 137391 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120216/9d81778f/attachment-0005.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: old_8_1.jpg
Type: image/jpeg
Size: 217432 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120216/9d81778f/attachment-0006.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: new_8_1.jpg
Type: image/jpeg
Size: 217620 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120216/9d81778f/attachment-0007.jpg>