[petsc-dev] Generality of VecScatter

[Mark F. Adams]

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>