[petsc-dev] Generality of VecScatter

[Mark F. Adams]

On Nov 25, 2011, at 4:22 PM, Jed Brown wrote:

> On Fri, Nov 25, 2011 at 13:07, Mark F. Adams <mark.adams at columbia.edu> wrote:
> OK, thats a good start.  You do need two communication steps, 1) get offsets, 2) get data (right?).
> 
> Yes, to send variable-sized data, you need two steps. For constant-sized data, it is just one.
>  
>  You avoid packing the send data but you need to unpack the receive data, converting the raw graph data into the reduced ghost data.  Not simple but writing from one side only and with only one-to-one communication is attractive.
> 
> That depends a bit on what representation you want for the ghost data. You never "unpack" in a by-rank way since it gets put into the correct part of the domain according to where an MPI_Datatype says to put it. (This was part of the local setup when defining the MPI_Get() calls, but those are internal to the library.)
> 
> If you are increasing the level of ghosting, you probably want to number the new ghost nodes that you acquired and make the local data structure point directly at them instead of at the (rank, offset) at which they are owned. This is a global-to-local translation of the connectivity, so you can do it with a hash table or sorting. I think you can also skip sorting by pushing the new indices back through the global space.
> 
> That is, I effectively have two local-to-global maps, both pointing at the same global space: L1toG and L2toG. I want to translate some local information defined on L1 into L2. I can do this by fetching global indices and inverting the local part of the map, or (with the assistance of some memory provided by the global owner) I can do a gather L2 -> G* (G* has a slot for each process sharing via this map) and then get those indices back in L1 using scatter G* -> L1. I think the hash is usually better, but with a fast network and/or highly vectorized hardware, there might be an advantage to pushing the indices L2 -> G* -> L1 without the need for hashing or sorting.
> 
> 
> So keep going.  AMR is good but I'm not sure I'm up to specifying a complete unstructured AMR algorithm at the moment.  My other example of AMG coarse grid process aggregation is another....
> 
> Or perhaps a parallel maximal independent set algorithm, preferably my algorithm which is implemented in GAMG and documented in an old paper.
> 
> 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 ????
 endif
end for
reduce all status to owners ???

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

Mark

>         mark v as selected, mark neighbors(v) as deleted (in local space)
>     reduce status to owner
>     broadcast status to ghosters
> 
> In any round, multiple procs might have marked the vertex for deletion, but only if the vertex has a neighbor with larger owner rank, in which case it could not have been selected.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111125/79736b14/attachment.html>