\section {\bf Implementation Details}

In this section  we will describe how we implemented each phase of the
PIC code using HPF. 
        
\subsection {Scatter (Inverse Interpolation) Phase}
%PDOST1 Routine

\begin{figure}[htb]
\centerline{\psfig{figure=xfig/scatter.eps,width=3.0in}}
\caption{\sf For a one-dimensional simulation, interaction of a particle
(a) on the lower half of a grid interval; (b) on the upper half of a
grid interval with the neighboring grid points.}
\label{fig:pdost}
\end{figure}

The {\bf scatter phase} consists of three major steps. In the first step
the charge densities at each grid point due to nearby charged particles 
are calculated  using a second-order spline interpolation with periodic boundaries. 
The interaction between the particles and nearby grid points is shown in 
Figure~\ref{fig:pdost}. Since only the particles local to a partition 
participate in the computation of the charge densities at this step, 
the whole thing can be done easily using an {\tt INDEPENDENT DO} loop over 
the number of field partitions (Figure~\ref{code:PDOST1}) without any 
communication.  Each processor executes
the inner body for all the partitions belonging to it.
The variable {\sc n}
is assigned a value and then used as an index on the left-hand side of 
assignment  expressions. Because the compiler at this time lack adequate 
dependency and communication analysis mechanisms these types of loops are
automatically serialized instead of
complicated runtime inspector-executor loops \cite{Inspector} being generated.
To prevent performance degradation, we wrote an extrinsic routine that
 does static loop partitioning based on loop indices that executes the loop 
body in parallel. 

In the second step, the partial results
at guard grid points are sent to the appropriate processors to augment the partial values at
shadowed primary grid points of neighboring partitions. 

\SS
\begin{figure}[htb]
\begin{small} 
\noindent\hrulefill
{\sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\kill
%\>\>{\bf Subroutine Scatter1(part,q,noff)}\\
%\>\> Dimension part(idimp,npmax,nblok),q(nxpmx,nblok),noff(nblok) \\
%\> !HPF\$ Distribute *(*,*,block) :: part \\
%\> !HPF\$ Distribute *(*,block)   :: q    \\
%\> !HPF\$ Distribute *(block)     :: noff \\
\> !HPF\$ INDEPENDENT, NEW(n, dx)  \\
\>\>    DO k = 1, number\_of\_particle\_partitions  \\
\>\>\>     DO i = 1, number\_of\_particles\_in\_partition \\
\>\>\>\>     dx = part(POS,j,k) -$\lfloor part(POS,j,k)+0.5\rfloor$  \\
\>\>\>\>     n = $\lfloor$ part(POS,j,k) +0.5 $\rfloor$ -noff(k) +2\\  
\>\>\>\>     q(n, k) = q(n,k) + qm*(0.75-dx)$^2$ \\
\>\>\>\>     q(n+1, k) =  q(n+1,k) +0.5*qm*(0.5+dx)$^2$\\
\>\>\>\>     q(n-1, k) = q(n-1,k) +0.5*qm*(0.5-dx)$^2$\\
\>\>\>  END DO\\
\>\> END DO \\
\end{tabbing}
\noindent\hrulefill
}
\end{small}
\caption{\sf Calculating the particle charge densities at each grid point.}
\label{code:PDOST1}
\end{figure}
\DS

The third step is the preparation for the FFT. Since the next phase involves
complex data, each partition {\sc k} takes
a pair of consecutive items of {\sc q}, {\sc q(j,k)} and {\sc q(j+1,k)} 
and constructs from them a  complex charge density value {\sc qc(j/2,k)} 
in parallel (Figure~\ref{fig:cpp2fp}.)

Normally, once the second step has been performed, this step is communication 
free. However, we combined this step with the previous one for efficiency 
reasons and eliminated one costly buffer copy operation. 
The HPF code for this step is given in Figure~\ref{code:cpp2fp1}.
The {\tt FORALL} loop takes the real charges of primary grid points in pairs 
and calculates the corresponding complex charges.

While computing the complex charge densities at the leftmost and rightmost
grid points, contributions of the charges at the guard cells  of neighboring
partitions are added separately. Of course, this operation requires 
communication. The compiler analyzes the {\tt FORALL} statement and determine
the elements to be sent out and received  and generates  the appropriate 
communication calls automatically.

\begin{figure}[htb]
\centerline{\psfig{figure=xfig/copy-pp-to-fp.eps,width=4.50in}}
\caption{\sf Copying data from real charge density to complex charge density.}
\label{fig:cpp2fp}
\end{figure}


\SS
\begin{figure}[htb]
\begin{small}
\noindent\hrulefill
{\sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxx\=xxxxx\=xxxxx\kill 
%\>\>{\bf Subroutine Copy\_PP\_2\_FP1(q,qc)}\\
%\>\> Dimension qc(kxp,kblok),q(nxpmx,kblok) \\
%\> !HPF\$ Distribute *(*,block)   :: q, qc   \\
\>\>     FORALL(k=1:kblok,j=1:kxp)\\
\>\>\>     qc(j,k) = cmplx( q(2*j-1, k), q(2*j,k))  \\
\>\>     END FORALL\\
\\
\> C Consider contributions from guard cells . NP is the number of partitions.\\
\>\> FORALL k = (1 : kblok) \\
\>\>\> ! add last two guard cells to first complex charge of partition k+1\\
\>\>\>        qc(1,k+1(mod NP)) = qc(1,k+1(mod NP)) + cmplx(q(nxpmx-1,k),q(nxpmx,k)) \\
\>\>\>! add left guard cell to last complex charge of partition k-1\\   
\>\>\>        qc(kxp,k-1+NP(mod NP)) = qc(kxp,k-1+NP(mod NP)) + cmplx(0, q(1,k+1(mod NP))) \\
\>\>  END FORALL
\end{tabbing}
}
\noindent\hrulefill
\end{small}
\caption{\sf Copying data from real charge density array to complex charge 
density array (Scatter-steps 2 and 3).}
\label{code:cpp2fp1}
\end{figure}
\DS





