\documentstyle[12pt,lslide,psfig]{article}
%\documentstyle[12pt,amssymbols,lslide,psfig]{article}
        % <- if amssymbols.sty is available
%\documentstyle[12pt,amstex,amssymb,lslide]{article}
        % <- if you use AmSLaTeX
%\documentstyle[12pt,psfig]{article}


\pagestyle{myheadings}
%\pagestyle{empty}

\makeatletter
\def\@oddhead{\vbox{\hbox to\hsize{\sl \rightmark \hfill \sl \thepage }}}
\def\@oddfoot{\vbox{\vspace{-20pt} \footmsg \hfill \rm \today}}
\makeatother

\def\rightmark{\bf \Large PIC with HPF}
\def\footmsg{\bf \Large E. Akarsu et al.}

\landscape
        % <- if your driver can rotate 90 degrees.
        % e.x. in emTeX derivers:
        %  hp filename /tr2
        % \portrait is default.

% Addjust page dimensions here if necessary. For example:
%\addtolength{\textwidth}{-.3in}
%\addtolength{\textheight}{.5in}
%\addtolength{\topmargin}{.02in}
%\addtolength{\oddsidemargin}{-.03in}
%\addtolength{\evensidemargin}{-.03in}

\setlength{\textwidth}{6.9in}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.5pc}
\setlength{\topmargin}{-0.3in}
\setlength{\oddsidemargin}{-.3in}
\setlength{\parindent}{1pc}


%\verttop
        % compare it with \vertcenter that is the default

%\ovalframe
%\doubleboxframe % or \ovalframe
        % compare them with \shadowframe that is the default

%\boxsecframe
%\boxsecframe
        % compare it with \shadowsecframe that is the default


\begin{document}
\Large

\title{Particle-in-Cell Simulation Codes in High Performance Fortran}
\date{November 20, 1996}
\author {Erol Akarsu,Kivanc Dincer,Geoffrey Fox, Tom Haupt \\
    Northeast Parallel Architectures Center\\
    at \\
    Syracuse University}

\titlepage


%\sectioncontents

\maketitle

\begin{slide}
\section{Outline}
\date {}
\begin{itemize}
\item {\bf Main Phases of PIC codes}
\item {\bf Approach to Parallelization}
\item {\bf Implementation Details}
\item {\bf Performance Results}
\item {\bf Conclusion}
\end{itemize}

\end{slide}

\begin{slide}
\large
\section{Main Phases of PIC codes}

\begin{figure}[htb]
\centerline{\psfig{figure=xfig/pic-phases.eps,height=4.50in,width=6.00in}}
\caption{\sf Main phases of a typical PIC code.}
\label{fig:pic-phases}
\end{figure}

\end{slide}

\begin{slide}
\section{\bf Approach to Parallelization}

\begin{itemize}
  \item {\bf Decomposition of Principal Data Structures}
  \item {\bf Loop Level Parallelization(FORALL and INDEPENDENT DO)}
  \item {\bf Communication Optimizations(CSHIFT)}
  \item {\bf Passing Distributed Data to Subroutines(Descriptive Directive)}
  \item {\bf Extrinsic Procedures}
  \item {\bf Compiler Restrictions(Nonlinear Dependency)}
\end{itemize}

\begin {eqnarray}
   -E_l^i &=& -j \omega A_l - \frac {\partial \phi}{ \partial l}\,\, on \,\, S\\
   A &=& \mu \int_{axis} I(l) \frac{e^{-jkR}}{4 \pi R} dl\\
   \phi &=& {1/\epsilon}\int_{axis}\sigma (l)\frac{e^{-jkR}}{4\piR}dl\\
   \sigma &=& \frac{-1}{j\omega}\frac{dI}{dl}
\end{eqnarray}

\end{slide}

\begin{slide}

\section{\bf Decomposition of Data Structures}
\begin{figure}[htbp]
\centerline{\psfig{figure=xfig/grid.eps,height=5.0in,width=6.0in}}
\caption{\sf Illustration of particle and grid decompositions (Eulerian
 Decomposition) and
 associated charge densities at each grid point and interaction
 among them.}
\label{fig:gpfig}
\end{figure}

\begin{itemize}
\item{\bf Particle Array (and Particle Partition(PP))}
\item{\bf Grid Array     (and Field Partition(FP))} 
\item{\bf Guard Points}
\end{itemize}

\end {slide}

\begin {slide}
\section {\bf Extrinsic Procedures}

We wrote :

\begin{itemize}
\item   {\bf Fast Fourier Transform (FFT)} 
\item  { \bf Each Nested Loop }
\end {itemize}
as Extrinsic Subroutine

The version of HPF compiler was not able to parallelize some loops
in PIC code. Therefore we used extrinsic routines to make these
type of loops parallel. 

\end {slide}

\begin {slide}
\section {\bf Implementation Details}

\begin {itemize}
\item {\bf How we wrote down extrinsic functions}
\item {\bf Scatter Phase}
\item {\bf Field Solve Phase}
\item {\bf Gather Phase}
\item {\bf Particle Push Phase}
\end {itemize}

\end {slide}

\begin {slide}
\section {\bf How extrinsic functions was written}

We distributed particles and fields onto processors statically. {\bf PART}
holds the information of particles and Q the charge densities on
grid points. 

\begin {itemize}
\item {DIMENSION  PART(DIM=2,NUMBER\_OF\_PARTICLES, NUMBER\_OF\_BLOCKS)} 
\item {DIMENSION  Q(NUMBER\_OF\_GRID\_POINTS,NUMBER\_OF\_BLOCKS)}
\end {itemize}

We distributed these arrays block-wise  in the last dimension.
That is ,

\begin {itemize}
 \item {\bf !HPF\$ DISTRIBUTE (*,BLOCK)   :: Q}
 \item {\bf !HPF\$ DISTRIBUTE (*,*,BLOCK) :: PART}
\end {itemize}

Here are how we constructed our extrinsic functions:

\begin {itemize}
\item {\bf Analyze the nested loop to find the read \& written variables 
 in the loop}
\item {\bf Build one extrinsic function whose body is the body of loop and
whose parameters are those found at previous step} 
\end {itemize}

\end {slide}

\begin {slide}
\section {ONE EXTRINSIC FUNCTION EXAMPLE}

Here is one nested loop to compute charge densities on grid points:


\begin{figure}[htb]
\begin{large}
\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 \\
\>\>    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{large}
\caption{\sf Calculating the particle charge densities at each grid point.}
\label{code:PDOST1}
\end{figure}


\end {slide}

\begin {slide}

Here is the extrinsic function to compute above nested loop in parallel:

\begin{figure}[htb]
\begin{large}
\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(k,i,n, dx)  \\
\>    k = 1 \\
\>     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$\\
\>     EDNDO  \\
\end{tabbing}
\noindent\hrulefill
}
\end{large}
\caption{\sf Calculating the particle charge densities at each grid point.}
\label{code:PDOST1}
\end{figure}


\end {slide}

\begin {slide}

\section {\bf Scatter Phase}

\begin{figure}[htb]
\centerline{\psfig{figure=xfig/scatter.eps,height=3.0in,width=6.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.(by Inpedendent Do or Extrinsic
function )}
\label{fig:pdost}
\end{figure}


\begin{figure}[htb]
\centerline{\psfig{figure=xfig/copy-pp-to-fp.eps,height=6.0in,width=6.50in}}
\caption{\sf Copying data from real charge density to complex charge density.
(by Inpedendent Do or Extrinsic Function)}
\label{fig:cpp2fp}
\end{figure}

\end {slide}

\begin {slide}
\section {\bf Particle Push Phase}

\begin {itemize}
\item {\bf Each processor fills its send buffers,SbufR and SbufL
\item {\bf Each processor also calculates the number of outgoing particles in each send buffer}
\item {\bf Using CSHIFT function,shift these send buffers and number of 
outgoing particles to neighbors}
\item {\bf Each processor deposits the appropriate particles with position
between its boundaries ,if any,into its local data
and constructs again from others ,if any,
the send buffers from further going particles
\item {\bf Repeat above cycle until each particle reaches into appropriate
region }
\end {itemize}

Above steps,except third one, can be calculated in local.
\begin {itemize}
\item {\bf We wrote extrinsic function for each step above,except third one}
\item {\bf For third one, we use CSHIFT function to shift trough 
   third dimension}
\end {itemize}
\end {slide}


\begin {slide}
\begin{table}[h]  %5
\begin{center}
{ \large %\normalsize
\begin{tabular}{|| l | l || c | c | c | c | c | c ||} \hline
{\bf Phase} & {\bf Subphase} & \multicolumn{6}{c ||}{\bf Number of Processors} \\
 & &  1 & 2 & 4 & 8 & 16 & 32\\ \hline \hline
{\bf Scatter} & Phase 1   & 2.910 & 1.450 & 0.730 & 0.360 & 0.188 & 0.094 \\
        & Phase 2   &0.001 & 0.004 & 0.003 & 0.003 & 0.005 & 0.007 \\ \hline
{\bf Field Solve} & IFFT &0.123 & 0.075 & 0.045 & 0.030 & 0.023 & 0.024  \\
            & Poisson   &0.003 & 0.003 & 0.003 & 0.002 & 0.003 & 0.004  \\ \hline
{\bf Gather}      & Copy      &0.001 & 0.004 & 0.003 & 0.003 & 0.005 & 0.007  \\ \hline
{\bf Particle Push} &Push      &4.880 & 1.930 & 0.970 & 0.480 & 0.248 & 0.136  \\
              &Migrate   &0.000 & 0.800 & 0.410 & 0.210 & 0.115 & 0.070  \\ \hline
\hline
\multicolumn{2}{|| l ||}{\bf Loop Iteration Time}&1818.0 & 999.0 & 513.0 & 261.0 & 144
.0 & 94.5 \\ \hline
\end{tabular}
}
\caption{Execution times(in seconds) for 1D PIC  code in HPF 
 Number of Particles = 4M  Number of Grid Points = 16K .}
\label{tab:hpf1dspeed}
\end{center}
\end{table}
\end {slide}

\begin {slide}
\begin{table}[h]  %5
\begin{center}
{ \large %\normalsize
\begin{tabular}{|| l | l || c | c | c | c | c | c ||} \hline
{\bf Phase} & {\bf Subphase} & \multicolumn{6}{c ||}{\bf Number of Processors} \\
 & & 1 & 2 & 4 & 8 & 16 & 32 \\ \hline \hline
{\bf Scatter }     & Phase 1   & 2.910 & 1.450 & 0.730 & 0.360 & 0.189 & 0.090 \\
                  & Phase 2   & 0.001 & 0.004 & 0.003 & 0.003 & 0.005 & 0.007 \\ \hline
{\bf Field Solve} & FFT & 0.123 & 0.075 & 0.029 & 0.030 & 0.029 & 0.009 \\
                  & Poisson   &0.003 & 0.003 & 0.003 & 0.002 & 0.005 & 0.004  \\ \hline
{\bf Gather}      & Copy      &0.001 & 0.004 & 0.003 & 0.003 & 0.005 & 0.007  \\ \hline
{\bf Particle Push} &Push      &4.880 & 1.930 & 0.980 & 0.490 & 0.250 & 0.136  \\
                  & Migrate   &0.00 & 0.81 & 0.40 & 0.20 & 0.10 & 0.07  \\ \hline\hline
\multicolumn{2}{| l ||}{\bf Loop Iteration Time}&1818.0 & 1004.0 & 505.6 & 263.8
 & 132.1 & 85.5 \\ \hline
\end{tabular}
}
\caption{Execution times(in seconds) for 1D PIC  code in MPL 
 Number of Particles = 4M  Number of Grid Points = 16K .}

\label{tab:mpl1dspeed}
\end{center}
\end{table}
\end {slide}


\begin {slide}
\begin{table}[h]  %11....
\begin{center}
{\large %\normalsize
\begin{tabular}{|| l | l || c | c | c | c | c ||} \hline
{\bf Phase} & {\bf Subphase} & \multicolumn{5}{c ||}{\bf Number of Processors} \\
 & &  1 & 4 & 8 & 16 & 32 \\ \hline \hline

{\bf Scatter }    & Phase 1   & 5.450 & 1.300 & 0.650 & 0.329 & 0.167 \\
                  & Phase 2   & 0.0009 & 0.004 & 0.004 & 0.004 & 0.005 \\ \hline
{\bf Field Solve } & FFT & 0.005 & 0.015 & 0.009 & 0.009 & 0.015 \\
                  & Poisson   & 0.009 & 0.003 & 0.003 & 0.003 & 0.004 \\ \hline
{\bf Gather }      & Copy      & 0.0009 & 0.0040 & 0.0040 & 0.0040 & 0.0050 \\ \hline
{\bf Particle Push } &Push      &8.150 & 1.890 & 0.950 & 0.486 & 0.251  \\
                  & Migrate   & 0.000 & 0.380 & 0.230 & 0.178 & 0.204 \\ \hline\hline
\multicolumn{2}{|| l ||}{\bf Loop Iteration Time}&4453.8 & 1196.0 & 624.0 & 325.0 & 24
7.0 \\ \hline
\end{tabular}
}
\caption{Execution times(in seconds) for 2D PIC  code in HPF
 Number of Particles = 3M  Number of Grid Points = 128 * 256  .}

\label{tab:hpf2dspeed}
\end{center}
\end{table}
\end {slide}


\begin {slide}
\begin{table}[h]  %14....
\begin{center}
{\large %\normalsize
\begin{tabular}{|| l | l || c | c | c | c | c |c ||} \hline
{\bf Phase} & {\bf Subphase} & \multicolumn{6}{c ||}{\bf Number of Processors} \\
 & &  1 & 2 & 4 & 8 & 16 & 32\\ \hline \hline

{\bf Scatter} & Phase 1   & 5.45 & 2.66 & 1.32 & 0.66 & 0.33 & 0.15 \\
                  & Phase 2   & 0.000 & 0.000 & 0.009 & 0.009 & 0.004 & 0.005 \\ \hline
{\bf Field Solve}  & FFT &0.005 & 0.025 & 0.009 & 0.009 & 0.009 & 0.015  \\
            & Poisson   &0.009 & 0.009 & 0.009 & 0.009 & 0.003 & 0.004  \\ \hline
{\bf Gather }      & Copy      &0.000 & 0.009 & 0.009 & 0.009 & 0.004 & 0.005  \\ \hline
{\bf Particle Push}  & Push      &8.150 & 3.820 & 1.880 & 0.940 & 0.479 & 0.250  \\
        & Migrate   & 0.000 & 0.689 & 0.370 & 0.180 & 0.100 & 0.200 \\ \hline\hline
\multicolumn{2}{|| l ||}{\bf Loop Iteration Time}&4453.8 & 2368.6 & 1206.5 & 614.2
 & 303.0 & 237.9 \\ \hline
\end{tabular}
}
\caption{Execution times(in seconds) for 2D PIC  code in MPL
 Number of Particles = 3M  Number of Grid Points = 128 * 256  .}

\label{tab:mpl2dspeed}
\end{center}
\end{table}
\end {slide}

\begin {slide}
\begin{figure}[htbp]
\centerline{\psfig{figure=speedup_1d.ps,height=7.0in,width=7.0in}}
\caption{ Speedup Comparison of 1D MPL \& HPF PIC Codes}
\label{2-merger}
\end{figure}
\end {slide}


\begin {slide}
\begin{figure}[htbp]
\centerline{\psfig{figure=speedup_2d.ps,height=7.0in,width=7.0in}}
\caption{ Speedup Comparison of 2D MPL \& HPF PIC Codes}
\label{3-merger}
\end{figure}
\end {slide}

\begin {slide}
\section {Performance Results}

We got approximately same timing results \& speedups as MPL version of PIC code with HPF 
implementation. 

If we looked the tables following, every subroutine of PIC code
shows a near-linear speedup.

\end {slide}


\begin {slide}

\section {\bf CONCLUSION}

\begin {itemize}
\item {\bf We implemented PIC which is grand-challenge in HPF successfully}
\item {\bf If the HPF compilers could support independent loops properly,
then we could replace these extrinsics with them}
\item {\bf We got linear speedup from our application}
\item {\bf HPF can compete with Message Passing Implementations}
\end {itemize}
\end {slide}

\end{document}










