
\chapter{Performance Analysis}


To evaluate the performance of the code on a parallel machine we ran
some examples on a cluster of four nodes connected with PathScale
InfiniPath HTX. Each node has two AMD Opteron 275 (Dual-core 2.2 GHz
Processors) and 4 GB of main memory. The system achieves 60
Gigaflops with the Linpack benchmark, which is about 85\% of peak
performance.

For each test run we evaluate the parallel efficiency as
\[
E_n = \frac{T_1}{nT_n} 100,
\]
where $T_n = \max_{0\le i < n}\{t_i\}$, $n$ is the total number of
processors (submesh) and $t_i$ is the time required to run the {\tt
evolve} code on processor $i$.  Note that $t_i$ does not include the
time required to build and subpartition the mesh etc., it only
includes the time required to do the evolve calculations (eg.
\code{domain.evolve(yieldstep = 0.1, finaltime = 3.0)}).

\section{Advection, Rectangular Domain}

The first example looked at the rectangular domain example given in
Section \ref{subsec:codeRPA}, except we changed the finaltime time
to 1.0 (\code{domain.evolve(yieldstep = 0.1, finaltime = 1.0)}).

For this particular example we can control the mesh size by changing
the parameters \code{N} and \code{M} given in the following section
of code taken from
 Section \ref{subsec:codeRPA}.

\begin{verbatim}
#######################
# Partition the mesh
#######################
N = 20
M = 20

# Build a unit mesh, subdivide it over numproces processors with each
# submesh containing M*N nodes

points, vertices, boundary, full_send_dict, ghost_recv_dict =  \
    parallel_rectangle(N, M, len1_g=1.0)
\end{verbatim}

Tables \ref{tbl:rpa40}, \ref{tbl:rpa80} and \ref{tbl:rpa160} show
the efficiency results for different values of \code{N} and
\code{M}. The examples where $n \le 4$ were run on one Opteron node
containing 4 processors, the $n = 8$ example was run on 2 nodes
(giving a total of 8 processors). The communication within a node is
faster than the communication across nodes, so we would expect to
see a decrease in efficiency when we jump from 4 to 8 nodes.
Furthermore, as \code{N} and \code{M} are increased the ratio of
exterior to interior triangles decreases, which in-turn decreases
the amount of communication relative the amount of computation  and
thus the efficiency should increase.

The efficiency results shown here are competitive.

\begin{table}
\caption{Parallel Efficiency Results for the Advection Problem on a
Rectangular Domain with {\tt N} = 40, {\tt M} =
40.\label{tbl:rpa40}}
\begin{center}
\begin{tabular}{|c|c c|}\hline
$n$ & $T_n$ (sec) & $E_n (\%)$ \\\hline
1 & 36.61 & \\
2 & 18.76 & 98 \\
4 & 10.16 & 90 \\
8 & 6.39 & 72 \\\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption{Parallel Efficiency Results for the Advection Problem on a
Rectangular Domain with {\tt N} = 80, {\tt M} =
80.\label{tbl:rpa80}}
\begin{center}
\begin{tabular}{|c|c c|}\hline
$n$ & $T_n$ (sec) & $E_n (\%)$ \\\hline
1 & 282.18 & \\
2 & 143.14 & 99 \\
4 & 75.06 & 94 \\
8 & 41.67 & 85 \\\hline
\end{tabular}
\end{center}
\end{table}


\begin{table}
\caption{Parallel Efficiency Results for the Advection Problem on a
Rectangular Domain with {\tt N} = 160, {\tt M} =
160.\label{tbl:rpa160}}
\begin{center}
\begin{tabular}{|c|c c|}\hline
$n$ & $T_n$ (sec) & $E_n (\%)$ \\\hline
1 & 2200.35 & \\
2 & 1126.35 & 97 \\
4 & 569.49 & 97 \\
8 & 304.43 & 90 \\\hline
\end{tabular}
\end{center}
\end{table}


%Another way of measuring the performance of the code on a parallel machine is to increase the problem size as the number of processors are increased so that the number of triangles per processor remains roughly the same.  We have not carried out measurements of this kind as we usually have static grids and it is not possible to increase the number of triangles.

\section{Advection, Merimbula Mesh}

We now look at another advection example, except this time the mesh
comes from the Merimbula test problem. That is, we ran the code
given in Section \ref{subsec:codeRPMM}, except the final time was
reduced to 10000 (\code{finaltime = 10000}). The results are given
in Table \ref{tbl:rpm}. These are good efficiency results,
especially considering the structure of the Merimbula mesh.
%Note that since we are solving an advection problem the amount of calculation
%done on each triangle is relatively low, when we more to other problems that
%involve more calculations we would expect the computation to communication ratio to increase and thus get an increase in efficiency.

\begin{table}
\caption{Parallel Efficiency Results for the Advection Problem on the
  Merimbula Mesh.\label{tbl:rpm}}
\begin{center}
\begin{tabular}{|c|c c|}\hline
$n$ & $T_n$ (sec) & $E_n (\%)$ \\\hline
1 &145.17 & \\
2 &77.52 & 94 \\
4 & 41.24 & 88 \\
8 & 22.96 & 79 \\\hline
\end{tabular}
\end{center}
\end{table}

\section{Shallow Water, Merimbula Mesh}

The final example we looked at is the shallow water equation on the
Merimbula mesh. We used the code listed in Section \ref{subsec:codeRPSMM}. The
results are listed in Table \ref{tbl:rpsm}. The efficiency results are not as
good as initially expected so we profiled the code and found that
the problem is with the \code{update_boundary} routine in the {\tt domain.py}
file. On one processor the \code{update_boundary} routine accounts for about
72\% of the total computation time and unfortunately it is difficult to
parallelise this routine. When metis subpartitions the mesh it is possible
that one processor will only get a few boundary edges (some may not get any)
while another processor may contain a relatively large number of boundary
edges. The profiler indicated that when running the problem on 8 processors,
Processor 0 spent about 3.8 times more doing the \code{update_boundary}
calculations than Processor 7. This load imbalance reduced the parallel
efficiency.

Before doing the shallow equation calculations on a larger number of
processors we recommend that the \code{update_boundary} calculations be
optimised as much as possible to reduce the effect of the load imbalance.


\begin{table}
\caption{Parallel Efficiency Results for the Shallow Water Equation on the
  Merimbula Mesh.\label{tbl:rpsm}}
\begin{center}
\begin{tabular}{|c|c c|}\hline
$n$ & $T_n$ (sec) & $E_n (\%)$ \\\hline
1 & 7.04 & \\
2 & 3.62 & 97 \\
4 & 1.94 & 91 \\
8 & 1.15 & 77 \\\hline
\end{tabular}
\end{center}
\end{table}
