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???