<div class="gmail_quote">On Sun, Jun 10, 2012 at 12:30 PM, Barry Smith <span dir="ltr"><<a href="mailto:bsmith@mcs.anl.gov" target="_blank">bsmith@mcs.anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  For clarification it sounds like you color your matrix (with independent sets) and then march through the colors, each color gets smoothed (in parallel since they are independent) then on to the next color?</blockquote>
</div><br><div>Not independent sets, just by data dependency. For example, everyone relaxes a block along the right boundary (implying an ordering that visits those blocks in rank order, except that those strips never touch each other so they can be done in parallel), then send the updated state to the proc on the right. While waiting for the message, he might smooth another set that does not have a data dependency. When a process receives the first message (from the proc to the left), it can relax that part. There is a picture in Mark's paper that should make the algorithm clear. This approach doesn't suffer from the atrocious memory access pattern of classical coloring; it's also asynchronous and completes with fewer messages in total.</div>