On Nov 25, 2011, at 9:13 PM, Jed Brown wrote: > On Fri, Nov 25, 2011 at 20:06, Mark F. Adams <mark.adams at columbia.edu> > wrote: >> 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). >> >> while (candidates remain): >> forall v in owned_candidates with neighbor ranks smaller than p: > > 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. > > You could say loop: > > for all owned_candidates v > for all neighbors q of v > if q is selected > delete v > skip v > else if q.proc > myproc and q is not deleted > skip v > endif > end for > if not skip v then > select v > delete all q > broadcast v status ???? > > Why broadcast the single value immediately?
Thats what I'm asking. I assumed that there is some buffering going on here but that is a later question. > 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. > > endif > end for > reduce all status to owners ??? > > 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. > > > 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??? > > 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. 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. 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). 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. Now I want to see exactly how that is implemented, here is a guess: MPI_Win_fence 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) MPI_Win_fence. This is not complete but am I on the right track? Mark -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111126/ab3243c7/attachment.html>