On Fri, Nov 25, 2011 at 20:06, Mark F. Adams <mark.adams@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?

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.