% $Id$
% $Source$
% $Log$

\subsection{Decomposition of Principal Data Structures}

The particles and fields that comprise the physics of the problem are
represented algorithmically by two computational objects:
\begin{itemize}
 \item {\bf Particle array} keeps the information such as velocity,
position and mass,  of each particle of the simulation. 
 \item {\bf Grid array} is a regular mesh that discretizes the simulation 
 domain.  Each particle lies within a {\it cell} of the mesh bounded by two 
 grid points.
\end{itemize}

The performance of the PIC simulation codes depends critically on the 
decomposition (distribution) strategy of the grid points and particles among 
the nodes of a distributed memory  machine or workstation cluster.
We used a variant of 
{\bf Eulerian decomposition} \cite{Conc-PIC} which assigns
each processor a fixed spatial partition of the grid and the particles 
within the cells are surrounded by those grid points. This prevents the
high communication cost in the gather and scatter phase, yet load imbalance 
among processors
may develop after repetitive iterations  as a result of excessive particle 
accumulation in certain cells. 

\begin{figure}[htbp]
\centerline{\psfig{figure=xfig/grid.eps,width=4.50in}} 
\caption{\sf Illustration of particle and grid decompositions and 
 associated charge densities at each grid point and interaction
 among them.}
\label{fig:gpfig}
\end{figure}

Figure~\ref{fig:gpfig} shows how a one-dimensional domain of length 16 
is decomposed into grid(field) and particle partitions assuming there are
four processors ({\sc nvp=4}).

The virtual processor domain in HPF is declared as follows:

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxxxx \kill
\>    !HPF\$ PROCESSORS :: PROCS(nvp)
\end{tabbing}
}


{\bf Particle partitions(PP)} are used to divide the particles and particle 
computation efficiently among processors. 
The particles are distributed according to their coordinates {\sc x}, that
is, the $k$-th partition($PP_k$) contains all particles with
{\sc edges(left,k) $<$ x $\le$ edges(rght,k)}. Second dimension of {\sc edges}
enumerate partitions and it is distributed in a block-wise on that  dimension:

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxxxx \kill
\>\>        DIMENSION INTEGER edges(2, numpp) \\
\>    !HPF\$ DISTRIBUTE (*, BLOCK) ONTO PROCS :: edges
\end{tabbing}
}

The particles' parameters are stored in array {\sc part(i,j,k)}:
 the first index selects between the spatial coordinate and
the velocity of the particle,
the second enumerates particles in the partition, and the third one enumerates
the partitions. Consequently, the array {\sc part} is of shape 
{\sc (2,npmax,numpp)}, where
{\sc npmax} is the maximum number of particle allowed in one partition.
{\sc npmax} sets a maximum limit on the number of particles that can be placed
into a partition and prevents enormous load imbalances among partitions.
The current number of particles for each $PP$ is kept in  {\sc npp(numpp)}
array. Particle array is distributed in a block fashion:

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxxxx \kill
\>    !HPF\$ DISTRIBUTE (*, *, BLOCK) ONTO PROCS :: part
\end{tabbing}
}

{\bf Field partitions(FP)} are used to divide the electromagnetic computation 
among the processors uniformly. 
 Each partition has equal
number of cells (delimited by the grid points) of unit length. For
example, in Figure~\ref{fig:gpfig} we have 4 cells and 4 primary grid points
for each of 4 partitions.  Each partition owns the grid point on its
right boundary.

Since the interactions between the field and the particles are not
confined to a partition, each subdomain stores  additional information
about the charge density associated with grid points that lie outside
the partition: one {\bf guard point} on the left of the partition, and two
{\bf guard points} on the right to the partition (Figure~\ref{fig:gpfig})
that shadows the rightmost grid point of the left partition, and two leftmost
grid points of the right partition, respectively.
It helps each processor to calculate the partial affect of its
local particles on these overlapped grid points. The total charge density
at the primary grid points is found by adding the partial  deposits of the 
guard cells at  neighbor partitions.

The charge densities on  grid points (primary grid points and the ones of
guard cells)are stored in the real charge array {\sc q(nxpmx,numpp)}
where {\sc nxpmx} is the number of primary and guard cell grid points of 
one partition and  {\sc numpp} is the number of particle partitions.
These structures are  distributed as:

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxxxx\kill
\>    !HPF\$ DISTRIBUTE (*, BLOCK) ONTO PROCS :: q  
%\>    !HPF\$ DISTRIBUTE (BLOCK) ONTO PROCS    :: nxp \\
%\>    !HPF\$ DISTRIBUTE (BLOCK) ONTO PROCS    :: noff
\end{tabbing}
}

Actually, in order to solve the field equations, we have to transfer
real charge density  {\sc q} into complex charge 
{\sc qc(kxp,numfp)} where {\sc kxp} is the number of complex grids in each
partition and {\sc numfp} is the number of field partitions.  
The complex charge density on each
processor are calculated from local real charge density values of
primary grid points and the ones of overlapped grid points of
neighbor processors. The number of the complex 
grid points for each partition is equal to the one half of its primary
grid points.  Each processor holds all the complex
charges for its complex grid points in its subdomain.

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxxxx\kill
\>    !HPF\$ DISTRIBUTE (*, BLOCK) ONTO PROCS :: qc
\end{tabbing}
}

The complex grid points are aligned  with the odd-valued real primary
grid points.

%------------
% end of decomp.tex
%------------
