[petsc-users] ParMETIS_V3_PartGeomKway

Thu Feb 16 18:03:41 CST 2012

On Feb 16, 2012, at 5:06 PM, Mohammad Mirzadeh wrote:

> 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?).

Partitioning is an NP-something problem, ie, you do not get the optimal solution in reasonable time.  If you give ParMetis the optimal initial partitioning it will ignore it and just run its algorithm and give you, in general, a sub-optimal solution.  It does not check that the initial partition was better than what it produced.  So you _can_ get a worse partitioning out of ParMetis then what you gave it.

Mark

> 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
> 
> 
> <new_4_1.jpg><old_4_1.jpg><old_8_1.jpg><new_8_1.jpg>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20120216/9fad7618/attachment.htm>