<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Nov 25, 2011, at 9:13 PM, Jed Brown wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div class="gmail_quote">On Fri, Nov 25, 2011 at 20:06, Mark F. Adams <span dir="ltr"><<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">
<div class="im"><blockquote type="cite"><div>MIS is straightforward. To define the parallel graph, let's say that ghosting processes have (owner rank, index) of neighbors. An owned point is only a candidate for selection if all neighbors have the same rank or smaller (according to Rule 2 of your paper).</div>
<div><br></div><div>while (candidates remain):</div><div> forall v in owned_candidates with neighbor ranks smaller than p:</div></blockquote><div><br></div></div><div>This is not quite right, and I want to see how complex or cumbersome this one sided model will get when you get all the details in.</div>
<div><br></div><div>You could say loop:</div><div><br></div><div>for all owned_candidates v</div><div> for all neighbors q of v </div><div> if q is selected</div><div> delete v</div><div> skip v</div><div> else if q.proc > myproc and q is not deleted</div>
<div> skip v</div><div> endif</div><div> end for</div><div> if not skip v then </div><div> select v</div><div> delete all q</div><div> broadcast v status ????</div></blockquote><div><br></div><div>Why broadcast the single value immediately? </div></div></blockquote><div><br></div><div>Thats what I'm asking. I assumed that there is some buffering going on here but that is a later question.</div><br><blockquote type="cite"><div class="gmail_quote"><div>I figured that we would just store the status until we are done with what we can do locally, then we'll do reduce-and-broadcast and move on to the next round.</div>
<div> </div></div></blockquote><blockquote type="cite"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; "><div> endif</div><div>end for</div><div>reduce all status to owners ???</div></blockquote><div><br></div><div>
Yeah, we reduce the status from the local spaces (which may have marked a point as deleted), then broadcast. The communication graph is stored on the local side.</div></div></blockquote><blockquote type="cite"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">
<div><br></div><div>I thought in your one-sided model you could not broadcast, or push data. You can only pull data and only want to pull data. But you have a broadcast???</div></blockquote></div><br><div>Remember that my first primitive was "broadcast", which is essentially global-to-local. The map is as a local-to-global map and the "get" is initiated at the local space.</div>
</blockquote></div><div><br></div>I was confused, and perhaps still am, the broadcast is the one sided pull of ghost data to the local space. So a broadcast is passive for the broadcaster whereas it implied an active process to me. The reduce is a push of ghost data with the same (only) map to the global vertex.<div><br><div>The way I'm writing the algorithm there is no need for a reduce, I think, but this is a detail, this algorithm broadcasts the selected vertex status (and deleted which I forgot in my psuedo-code) and then it infers the local deleted w/o having to have it sent (reduced).</div><div><br></div><div>So I'm thinking a good way to implement this MIS with your model is after each vertex loop, you do what you call a "broadcast" of all new status.</div><div><br></div><div>Now I want to see exactly how that is implemented, here is a guess:</div><div><br></div><div>MPI_Win_fence</div><div>loop over all of your boundary vertices that are not "done" yet, and do an MPI_Get (I assume that these requests are buffered in someway) </div><div>MPI_Win_fence.</div></div><div><br></div><div>This is not complete but am I on the right track?</div><div><br></div><div>Mark</div></body></html>