<div dir="ltr"><div><span style><font color="#222222" face="arial, sans-serif">My apologies, the email I send had large attachments and didn&#39;t get through. Here is the email and the link to the figures:</font></span></div>

<div><a href="http://imgur.com/a/yRTHf">http://imgur.com/a/yRTHf</a></div><div>-------------------------------------------------</div><span style><div><span style><br></span></div>Thanks everyone for participating in the discussion. I really appreciate it. I guess I&#39;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&#39;m not using p4est right now). Please see figures for a sample amr quadtree grid.</span><div style>

<br></div><div style>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:</div>

<div style><br></div><div style><div>[0] # of edge cuts: 35</div><div>[1] # of edge cuts: 35</div><div>[2] # of edge cuts: 35</div><div>[3] # of edge cuts: 35</div><div>[0] Before: # of ghost Nodes: 35 </div><div>[1] Before: # of ghost Nodes:  29 </div>

<div>[2] Before: # of ghost Nodes:  35 </div><div>[3] Before: # of ghost Nodes:  23 </div><div>[0] After: # of ghost Nodes:  17 </div><div>[1] After: # of ghost Nodes:  20 </div><div>[2] After: # of ghost Nodes:  17 </div>

<div>[3] After: # of ghost Nodes:  16 </div></div><div style><br></div><div style>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)</div>

<div style><br></div><div style><div>[0] # of edge cuts: 67</div><div>[1] # of edge cuts: 67</div><div>[2] # of edge cuts: 67</div><div>[3] # of edge cuts: 67</div><div>[0] Before: # of ghost Nodes:  58 </div><div>[1] Before: # of ghost Nodes:  67 </div>

<div>[2] Before: # of ghost Nodes:  62 </div><div>[3] Before: # of ghost Nodes:  44 </div><div>[0] After: # of ghost Nodes:  103 </div><div>[1] After: # of ghost Nodes:  115 </div><div>[2] After: # of ghost Nodes:  81 </div>

<div>[3] After: # of ghost Nodes:  28 </div></div><div style><br></div><div style>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&#39;m wrong here?). That&#39;s why i asked if minimizing edge cuts does not translate to having fewer ghost points. </div>

<div style><br></div><div style>Does minimizing latency favors creating &#39;clustered chunks&#39; of points for each processor and if so, could that create a partitioning with more ghost points? </div><div style><br></div>

<div style>One final point, I&#39;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&#39;t get the reported numbers. why is that? (for instance proc 3, cuts 20 edges, including extra &#39;diagonal&#39; ones at the coarse-fine interfaces but parmetis reports 35-- i can explain this more in details if needed)</div>

<div style><br></div><div style>thanks,</div><div style>Mohammad</div><br><div class="gmail_quote">On Thu, Feb 16, 2012 at 6:21 AM, Mark F. Adams <span dir="ltr">&lt;<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>&gt;</span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div><div class="h5"><div>On Feb 16, 2012, at 8:46 AM, Matthew Knepley wrote:</div>

<br><blockquote type="cite">On Thu, Feb 16, 2012 at 7:43 AM, Gerard Gorman <span dir="ltr">&lt;<a href="mailto:g.gorman@imperial.ac.uk" target="_blank">g.gorman@imperial.ac.uk</a>&gt;</span> wrote:<br><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Matthew Knepley emailed the following on 16/02/12 13:29:<br>
&gt; On Thu, Feb 16, 2012 at 3:38 AM, Mohammad Mirzadeh &lt;<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a><br>
&gt; &lt;mailto:<a href="mailto:mirzadeh@gmail.com" target="_blank">mirzadeh@gmail.com</a>&gt;&gt; wrote:<br>
&gt;<br>
&gt;     Hi guys,<br>
&gt;<br>
&gt;     I&#39;m wondering if there is any implementation<br>
&gt;     for ParMETIS_V3_PartGeomKway()? All I can find is the<br>
&gt;     implementation for ParMETIS_V3_PartKway and I&#39;m wondering if<br>
&gt;     including the vertex positions could help me get a better<br>
&gt;     partitioning?<br>
&gt;<br>
&gt;<br>
&gt; As far as communication goes, it will not help.<br>
&gt;<br>
&gt;<br>
&gt;     Also I have a general question. Is minimizing number of edge cuts<br>
&gt;     essentially the same as minimizing communication? I understand<br>
&gt;     that they are related, but communication is proportional to the<br>
&gt;     number of ghost points which is not exactly equal (its actually<br>
&gt;     less than) to the number of edge cuts. So then is it possible that<br>
&gt;     this could actually result in larger number of ghost points, at<br>
&gt;     least for some of processors?<br>
&gt;<br>
&gt;<br>
&gt; It of course depends on your problem and the graph you draw, but you<br>
&gt; can always draw a graph<br>
&gt; where the edge cut is exactly your communication.<br>
&gt;<br>
&gt;<br>
<br>
<br>
It might also be interesting to look at Zoltan&#39;s hypergraph partitioning<br>
which can better balance communications -<br>
<a href="http://www.cs.sandia.gov/zoltan/dev_html/dev_phg.html" target="_blank">http://www.cs.sandia.gov/zoltan/dev_html/dev_phg.html</a></blockquote><div><br></div><div>I would caution you that one thing people are rarely careful about is quantifying the effect of</div>


<div>latency vs communication volume. I would bet you $10 that the lion&#39;s share of slow down is</div><div>due to load imbalance/latency rather than communication volume (since comm links are so</div><div>big).</div><div>


<br></div></div></blockquote><div><br></div></div></div><div>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.  </div>

<div><br></div><div>Furthermore you don&#39;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).</div><span class="HOEnZb"><font color="#888888"><div>

<br></div><div>Mark</div></font></span><div class="im"><br><blockquote type="cite"><div class="gmail_quote"><div>   Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<br>
Cheers<br>
<span><font color="#888888">Gerard<br>
<br>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>


-- Norbert Wiener<br>
</blockquote></div></div><br></div></blockquote></div><br></div>