RE: [ESPResSo-devel] Cell lists vs. domain decomposition

[Limbach, Hans Joerg, LAUSANNE, NRC-FS]

Hi

I agree with Olaf, that in the documentation the different nature of the two 
things should be explained. As a second point it should be explained why and 
how they are related in Espresso:
The cells are per definition never smaller then the maximal short range 
interaction, which is also the relevant length scale for the ghost particle 
communication in the domain decomposition scheme (no matter if it is 1D, 2D or 
nD periodic). That is the reason why the cells that are used for the 
linked-cell algorithm (By the way in Espresso the particles are not just linked 
to a cell, they physically are located in the cell. So in principle the term 
linked-cell algorithm is wrong for the Espresso implementation) are also used 
for the ghost communication of the domain decomposition. In addition it is 
difficult to implement something where a cell is devided over several 
processors which would happen if you do not link these two things. 
With respect to other particle organization and parallelization schemes the 
cells have nothing to do with a linked-cell algorithm (even so they got there 
name cell from this historic link). In general a cell in Espresso is just a 
container for a bunch of particles and nothing more.
This is described in the Espresso paper, but probably it is good to add some 
clarifying sentences to the relevant sections when the linked-cell algorithm 
and the domain decomposition is decribed.

Hanjo 

> -----Original Message-----
> From: address@hidden 
> [mailto:address@hidden On 
> Behalf Of Ulf Schiller
> Sent: mardi, 7. août 2007 09:36
> To: ESPResSo developers' mailing list
> Subject: Re: [ESPResSo-devel] Cell lists vs. domain decomposition
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Olaf Lenz wrote:
> > Hi Despressies!
> > 
> > In context of the thread on diffusion, I noticed that in 
> the docs (i.e.
> > the UG) two things seem to be intermixed that are related but not 
> > really the same:
> > 1. To my understanding, "domain decomposition" is related to 
> > parallelization. It means that the simulation box is 
> decomposed into 
> > domains, each of which can be computed on another 
> processor. The size 
> > and shape of the domains is completely arbitrary. However, it is 
> > favourable to minimise the interface with neighbouring domains to 
> > reduce the communication overhead required to communicate the 
> > particles that interact with neighbouring domains.
> > 2. "Cell lists" on the other hand are needed to speed up 
> the algorithm 
> > on a single processor: the domain is decomposed into cells with a 
> > minimal side length of the interaction range. When it is 
> necessary to 
> > loop over the interaction partners of a particle, it is 
> only necessary 
> > to consider those particles that are in the 26 neighbouring 
> cells and 
> > the cell itself. This algorithm in combination with Verlet lists is 
> > the fastest option for many systems.
> > 
> > Both of these points can be related, and one can think of 
> choosing the 
> > domains from item 1 from the cells of item 2, but in theory 
> they are 
> > completely independent, are they not?
> > To my understanding, the "cellsystem" command of ES refers 
> to item 2, 
> > doesn't it? However, in the documentation of the command, 
> the notion 
> > "domain decomposition" is used. This bugs me.
> 
> Hi!
> 
> If I understand correctly, the "cellsystem" command refers to 
> both items. The parallelization and the organization of the 
> cell lists in ESPResSo are in fact closely related, e.g. the 
> layered cellsystem implies a 1x1xn node_grid and determines 
> the number of communications between processes. The N^2 
> cellsystem uses load balancing and thus implies what has to 
> be done on a processor and communicated to others.
> 
> > I would propose to remove the term "domain decomposition" from the 
> > docs on the cellsystem command, or else describe how they are 
> > interrelated in the case of ESPResSo.
> 
> My view on the issue is that the implementation of the 
> cellsystems has implications on the parallelization scheme. 
> In this sense, the domain decomposition comes closest to your 
> description, while the N^2 neither uses neither domain 
> decomposition nor cell lists in that way. The layered 
> cellsystem mixes both concepts (1d domain decomposition and 
> cell lists in one direction and N^2 in the other two).
> 
> I'm not sure how much detail should be put into the 
> documentation of the cellsystem command, in particular since 
> there is already a reference to the "Under the hood" section.
> 
> Cheers,
> Ulf
> 
> - --
> Ulf D. Schiller   *   Room 1.404   *   Phone +49 6131 379-481
> Max Planck Institute for Polymer Research Theory Group
> D-55128 Mainz, Germany                   50° 0' N, 008° 16' E
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.0 (GNU/Linux)
> 
> iD8DBQFGuCC7tqL0QpvXQjERAobqAKDDf5o62+dAPVBeA6Z21XaDrJRiIwCgrgjU
> YpvVEvivI8VUCM+msmy+O3g=
> =5VJx
> -----END PGP SIGNATURE-----
> 
> _______________________________________________
> ESPResSo-devel mailing list
> address@hidden
> https://fias.uni-frankfurt.de/mailman/listinfo/espresso-devel
>