On Nov 25, 2011, at 9:13 PM, Jed Brown wrote:

On Fri, Nov 25, 2011 at 20:06, Mark F. Adams <[email protected]> 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