[petsc-users] ParMETIS_V3_PartGeomKway

[Mark F. Adams]

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/493eccad/attachment.htm>