dolfin team mailing list archive

[Anders Logg <logg@xxxxxxxxx>]

On Thu, Aug 28, 2008 at 04:09:25PM +0200, Niclas Jansson wrote:
> Anders Logg wrote:
> > On Fri, Aug 22, 2008 at 09:11:37AM +0200, Niclas Jansson wrote:
> >> Anders Logg wrote:
> >>> On Thu, Aug 21, 2008 at 11:14:09AM +0200, Niclas Jansson wrote:
> >>>> Anders Logg wrote:
> >>>>> On Thu, Aug 21, 2008 at 09:10:03AM +0200, Niclas Jansson wrote:
> >>>>>> Anders Logg wrote:
> >>>>>>> On Wed, Aug 20, 2008 at 06:17:30PM +0200, Niclas Jansson wrote:
> >>>>>>>
> >>>>>>>>>> Stage 2 seems to involve a lot of communication, with small messages.
> >>>>>>>>>> I think it would be more efficient if the stage were reorganized such
> >>>>>>>>>> that all messages could be exchanged "at once", in a couple of larger
> >>>>>>>>>> messages.
> >>>>>>>>> That would be nice. I'm very open to suggestions.
> >>>>>>>> If understand the {T, S, F} overlap correctly, a facet could be globally
> >>>>>>>> identified by the value of F(facet).
> >>>>>>> No, F(facet) would be the local number of the facet in subdomain S(facet).
> >>>>>>>
> >>>>>>>> If so, one suggestion is to buffer N_i and F(facet) in 0...p-1 buffers
> >>>>>>>> (one for each processor) and exchange these during stage 2.
> >>>>>>>>
> >>>>>>>> -- stage 1
> >>>>>>>>
> >>>>>>>>   for each facet  f \in T
> >>>>>>>>     j = S_i(f)
> >>>>>>>>     if j > i
> >>>>>>>>
> >>>>>>>>         -- calculate dof N_i
> >>>>>>>>
> >>>>>>>>         buffer[S_i(f)].add(N_i)
> >>>>>>>>         buffer[S_i(f)].add(F_i(f))
> >>>>>>>>     end
> >>>>>>>>   end
> >>>>>>>>
> >>>>>>>>
> >>>>>>>> -- stage 2
> >>>>>>>>
> >>>>>>>> -- Exchange shared dofs with fancy MPI_Allgatherv or a lookalike
> >>>>>>>> -- MPI_SendRecv loop.
> >>>>>>>>
> >>>>>>>>    for j = 1 to j = (num processors - 1)
> >>>>>>>>       src = (rank - j + num processors) % num processors
> >>>>>>>>       dest = (rank + j) % num processors
> >>>>>>>>
> >>>>>>>>       MPI_SendRecv(dest, buffer[dest], src, recv_buffer)
> >>>>>>>>
> >>>>>>>>       for i = 0 to sizeof(recv_buffer), i += 2
> >>>>>>>>          --update facet recv_buff(i+1) with dof value in  recv_buff(i)
> >>>>>>>>       end
> >>>>>>>>
> >>>>>>>>    end
> >>>>>>> I didn't look at this in detail (yet). Is it still valid with the
> >>>>>>> above interpretation of F(facet)?
> >>>>>>>
> >>>>>> Yes, I think so.
> >>>>> I think I understand your point, but I don't understand the details
> >>>>> of your code.
> >>>> if j > i the processor is responsible for creating M_i for the shared
> >>>> facet. The newly created M_i is placed in the send buffer for the
> >>>> subdomain S_f(f), together with the local facet number in that subdomain.
> >>>>
> >>>> So the send buffers contains tuples {M_i, F_i(f)}, since there is one
> >>>> buffer for each subdomain, one could be sure that F_i(f) is valid on the
> >>>> receiving processor.
> >>>>
> >>>> Instead of iterating over all processors and facets in stage 2, each
> >>>> processor receives a set of tuples (for all shared facets) from each
> >>>> processor. These could then be used to identify the local facet (since
> >>>> F_i(f) is the local facet number) and assign the dofs, which, if I
> >>>> understand everything correctly is obtained from M_i.
> >>>>
> >>>> One modification to the above algorithm, I think it's easier if the
> >>>> tuples are stored as {F_i(f), M_i}. Since M_i could be a long list of
> >>>> dofs. So the update loop would be something similar to
> >>>>
> >>>>   for i = 0 to size of recv_buff , i +=(number of dofs on each facet + 1)
> >>>>      local facet f = recv_buff(i)
> >>>>      for each facet on f, loop counter j
> >>>>         assign recv_buff( (i+1) + j) ) to facet dof j
> >>>>      end
> >>>>   end
> >>>>
> >>>>> The mapping N_i is an auxiliary global-to-global mapping, which maps
> >>>>> the global dofs on a local mesh to global dofs on the global mesh. It
> >>>>> has a meaning only on each local mesh. What we want to communicate is
> >>>>> the stuff in M_i.
> >>>> I see, then it should be M_i in the outlined code.
> >>>>
> >>>> Niclas
> >>> Sounds very good.
> >>>
> >>> Where do we start?
> >>>
> >>> I guess one good place to start would be to get input/partitioning
> >>> working and you seem to have that working already. We should be able
> >>> to read in a mesh, partition it (with ParMetis for now) and construct
> >>> the MeshFunctions S_i and F_i.
> >>>
> >>> Once that is in place, we can start hacking on DofMapBuilder::build().
> >>>
> >>> Could you outline what you have in terms of input/partitioning and
> >>> then we can start applying those patches.
> >>>
> >> Parallel mesh parsing, the entire mesh is never represented on a single
> >> processor. It's a two stage process, first the coordinates are loaded
> >> and partitioned with a geometric partitioner. In the second stage each
> >> processor loads the cells corresponding to the assigned coordinates, and
> >> finally the mesh is partitioned with a graph partitioner.
> >>
> >> Partitioning is done with the distributed geometric and mesh-to-dual
> >> graph partitioner in parmetis.
> > 
> > How does this work? It seems as if you have already partitioned the
> > domain geometrically, then there's no need to make a partition based on
> > topology. Or is the geometric partitioning only a first approximation
> > and then vertices are exchanged between processors?
> > 
> 
> 
> The coordinates in the XML-file are initially distributed across the 
> processors with a simple linear distribution, just to get it of the hard 
> drive.
>
> The geometric partitioner is used to make sure that all coordinates on a 
> processor lies close to each other. This simplifies and minimize 
> communication when parsing cell data.
> 
> Since the geometric partitioner creates rather bad partitions (with 
> respected to edge-cut), the graph partitioner is used to create a good 
> partitioning, with low edge-cut, thus minimizing 
> data-dependencies/communication.

Sounds good. Can you submit this in one or more patches, starting with
the parallel XML parser?

-- 
Anders

Attachment: signature.asc
Description: Digital signature