\chapter{Case Study: Matrix Multiplication}
The JStar Matrix Multiplication program multiplies two matrices of the same size ($N \times N$) and produces the
resulting matrix.
In this test case, the size of the matrices is 1,000. Assume that we have two $1,000-by-1,000$ matrices: matrix A and
matrix B. Matrix A is an anti-diagonal matrix and Matrix B is a square matrix.
The sequential matrix multiplication algorithm is to multiply one row in matrix A by one column in matrix B, and sum up these
product results to get one element in the final matrix. Repeat this step until all the elements in the product matrix
have been calculated.
%Matrix A and Matrix B are both the same sized square matrices, and thus the product matrix is also
%a $N-by-N$ square matrix.
Matrix A and Matrix B are specified in the following notations:
\[A_{N,N} =
\begin{pmatrix}
  0 & 0 & 0 & \cdots & 0 & 1 \\
  %0 & 0 & 0 & \cdots & 1 & 0 \\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
  a_{i,1}& a_{i,2} & \cdots & a_{i,j} & \cdots & a_{i,N}\\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
  %0 & 0 & 1 & \cdots & 0 & 0 \\
%   0 & 1 & 0 & \cdots & 0 & 0\\
  1 & 0 & 0 & \cdots & 0 & 0\\
\end{pmatrix}\]
$$ 
a_{i,j} = \left\{ \begin{array}{rl}
 1 &\mbox{ if (i+j) = N-1} \\
 0 &\mbox{ otherwise}
       \end{array} \right.   \forall i,j \in \{1,\ldots,N\}$$\\
\[
B_{N,N} =
\begin{pmatrix}
  0 & 1 & \cdots & b_{1,j} & \cdots & N-1 \\
  1 & 2 & \cdots & b_{2,j} & \cdots & N \\
  %2 & 3 & \cdots & \vdots & \cdots & N+1 \\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
  \vdots & \vdots & \vdots & b_{i,j} & \vdots & \vdots\\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
%   N-2 & N-1 & \cdots & b_{N,j} & \cdots & 2N-3\\
  N-1 & N & \cdots & b_{N,j} & \cdots & 2N-2\\
\end{pmatrix}
\]
$$ b_{i,j} = (i-1)+(j-1) \; \forall i,j \in \{1,\ldots,N\} $$
The matrix multiplication of Matrix A and Matrix B are:
\[
AB_{N,N} = A_{N,N} \times B_{N,N} 
\]
\[
=\begin{pmatrix}
  ab_{1,1}& ab_{1,2} & \cdots & ab_{1,j}& \cdots & ab_{1,N}\\
  %ab_{2,1}& ab_{2,2} & \cdots & ab_{2,j}& \cdots & ab_{2,N}\\
  \vdots & \vdots & \vdots & \vdots& \vdots& \vdots\\
  ab_{i,1}& ab_{i,2} & \cdots & \mathbf{ab_{i,j}}& \cdots & ab_{i,N}\\
  \vdots & \vdots & \vdots & \vdots& \vdots& \vdots\\
  ab_{N,1}& ab_{N,2} & \cdots & ab_{i,N}& \cdots & ab_{N,N}
\end{pmatrix}
\]
$$ab_{i,j} = \sum\limits_{m=1}^N a_{i,m} \times b_{m,j}\; \forall i,j \in \{1,\ldots,N\}$$
\\
\[=\begin{pmatrix}
  N-1 & N & N+1 & \cdots & 2N-3 & 2N-2\\
  %N-2 & N-1 & N & \cdots & 2N-4 & 2N-3\\
  \vdots & \vdots & \vdots & \vdots & \vdots & \vdots\\
  2 & 3 & 4 & \cdots & N & N+1 \\
  1 & 2 & 3 & \cdots & N-1 & N \\
  0 & 1 & 2 & \cdots & N-2 & N-1 \\
\end{pmatrix}
\]
\section{JStar MatrixMult Program}
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{./matrixmult/figure/MatrixMult_TableSchema}
\caption{The table schema of the JStar MatrixMulti program.}
\label{fig:MatrixMultTableSchema}
\end{figure}
The JStar MatrixMult program contains five tables: \class{MatMultRequest}, \class{MatMultRow}, \class{MatrixHeader},
\class{Matrix} and \class{PrintMatrix}, as shown in Figure~\ref{fig:MatrixMultTableSchema}. To effectively parallelize
the matrix multiplication, the program computes each row of the product matrix separately and create the result
matrix. Each row of product matrix can be conducted concurrently by taking one row from Matrix A and multiplying it
with Matrix B, as described in the following formula:
\[AB_{i} = A_{i} \times B =
\begin{bmatrix}
  a_{i,1} & a_{i,2} & \cdots & a_{i,j} & \cdots & a_{i,N} 
\end{bmatrix} \times
\begin{pmatrix}
  b_{1,1} & \cdots & b_{1,j} & \cdots & b_{1,N}\\
  b_{2,1} & \cdots & b_{2,j} & \cdots & b_{2,N}\\
  \vdots  &  & \vdots & & \vdots \\
  %b_{m,1} & \cdots & b_{m,j} & \cdots & b_{m,N}\\
  %\vdots  &  & \vdots & & \vdots \\
  b_{N,1} & \cdots & b_{N,j} & \cdots & b_{N,N}\\
\end{pmatrix}
\]
\[=
\begin{bmatrix}
  ab_{i,1} & ab_{i,2} & \cdots & ab_{i,j} & \cdots & ab_{i,N} 
\end{bmatrix}
\]
\par The JStar MatrixMult program starts up with one \class{MatMultRequest} tuple, generating one \class{MatMultRow}
tuple for each row in the product matrix. Each \class{MatMultRow} tuple performs one row multiplication rule which takes
a row from Matrix A, loops over all columns in Matrix B and uses a nested reducer that sums up the product results for
each column, and places the results in the corresponding row of the final matrix. The source code of the JStar Matrix
Multiplication is shown in Listing~\ref{sourcecodeofmatrixmult} of Appendix~\ref{ch:matrixmultscase}.
This case study was chosen because, unlike the previous case studies, it is embarrassingly parallel, so should be a good
candidate for a parallel implementation with high speedup.
\section{Benchmark Configuration}
\begin{table}[h!]
\centering
\subfloat[Hardware specification]{
\begin{tabular}{| l | c |}
\toprule
\multicolumn{2}{|>{\columncolor[gray]{.8}}c|}{Gaia (Symphony node CN-192)}\\
\midrule
CPU &  4 x Intel\textsuperscript{\textregistered} Xeon\textsuperscript{\textregistered} 8core E7- 8837 CPUs\\
& (8 cores @ 2.67GHz)\\\hline
L1 cache & 32K\\\hline
L2 cache & 256K\\\hline
L3 cache & 24576K\\\hline
RAM & 512GB RAM (@1066 MHz)\\\hline
Disk & 24 x 300GB 10k rpm SAS-2 hard disc\\
&  2 x 73GB 15k rpm SAS-2 hard disc \\\hline
OS & 64-Bit Linux operating system \\
& (kernel version 2.6.38)\\\hline
JAVA & 64-Bit JRE version 1.7.0\_17\\\hline
\end{tabular}
\label{tab:MatrixMultGaia}
}\quad
\subfloat[Java Virtual Machine options]{
\begin{tabularx}{0.95\textwidth}{|X|}
\toprule
\multicolumn{1}{|c|}{\cellcolor[gray]{0.8}JVM options}\\
\midrule
\flag{-Xmx7G} sets maximum Java heap size to be 7 GB.\\\hline
\flag{-verbose:gc} enables the verbose garbage collector.\\\hline
\flag{-Xbatch} stops the program while the hot spot compiler is recompiling/optimising the code.\\\hline
\flag{-XX:+PrintCompilation} prints the message when one method is compiled.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+PrintTenuringDistribution} prints the tenuring age information.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+PrintGCDetails} print messages at the garbage collection.\cite{website:javahotspotvm}\\\hline
\end{tabularx}
\label{tab:matrixMultJVM}
}
\caption{Benchmark configuration of the JStar MatrixMult program.}
\label{tab:MatrixMultBenchmarkConfig}
\end{table}
Table~\ref{tab:MatrixMultBenchmarkConfig} is the benchmark configuration for the JStar MatrixMult Program. The benchmark
experiments were conducted on a 32-core machine, as shown in Figure~\ref{tab:MatrixMultBenchmarkConfig}~\subref{tab:MatrixMultGaia}.
As the MatrixMult program takes two of the same sized ($1000-by-1000$) square matrices and produces another square matrix,
the total amount of memory the program uses is fixed and predicable.
This program does not require a large amount of heap space, but we set the maximum heap space to be 7GB to avoid garbage
collection during the benchmark.
\section{Performance Tuning Process}
\subsection{In-lining Tuples}\label{sec:inilinematrixmult}
\begin{figure}[h!]
	\centering
	\subfloat[The naive program]{
		\includegraphics[width=0.45\textwidth]{./matrixmult/figure/dependency_native.eps}
 		\label{fig:MatrixMultNativeDependency}
	}\quad
	\subfloat[The optimized program]{
		\includegraphics[width=0.45\textwidth]{./matrixmult/figure/dependency_optimized.eps}
		\label{fig:MatrixMultOptimizedDependency}
	}\\
	\subfloat{
	\begin{tabular}{c}
 	\hfill TRIGGER(Rule):$\bm{\longrightarrow}$\hspace{5mm}PUT(Gamma Database):{\color{red}${-\rightarrow}$}\\
 	\hfill PUT(Delta Tree):{\color{red}$\longrightarrow$}\hspace{5mm}GET(Gamma Database):{\color{blue}$-\rightarrow$}\\
  	\end{tabular}
	}	
\caption{Task dependency graphs of the JStar MatrixMult programs.}
\label{fig:MatrixMultdependency}
\end{figure}
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|}
\toprule
\textbf{Tuple} & \textbf{Delta Tree} & \textbf{Gamma Database}\\
\midrule
MatMultRequest & $\surd$ & $\times$ \\
MatrixHeader   & $\surd$ & $\surd$\\
MatMultRow     & $\surd$ & $\times$\\
Matrix         & $\times$ & $\surd$\\
PrintMatrix    & $\times$ & $\times$\\
\bottomrule
\end{tabular}
\caption{The inline tuple list of JStar MatrixMult program.}
\label{tab:MatrixMultOptimisation}
\end{table}
Figure~\ref{fig:MatrixMultdependency} \subref{fig:MatrixMultNativeDependency} is the task dependency graph of the JStar
MatrixMult program. It shows that \class{Matrix} tuples are never used as triggers of rules in this program and
served as the query of \method{Rule5}. Thus, \class{Matrix} tuples can be put into the Gamma table directly. Besides, as the
\class{MatMultRequest} and \class{MatMultRow} tuples are never queried by any rule, they can use the
\flag{noGamma} optimisation to skip the insertion of tuples from delta tree to Gamma table. Figure
~\ref{fig:MatrixMultdependency}\subref{fig:MatrixMultOptimizedDependency} is the task graph of the optimized JStar
MatrixMult program.
\par The summaried tuple tables are listed in Table~\ref{tab:MatrixMultOptimisation}.
The \class{PrintMatrix} tuples are not inserted into either the Delta tree or the Gamma database, because
printing out the matrix on the terminal may bias the actual execution time. Thus, we omit the requests that
prints out the whole result matrix but display the entry in the right bottom corner of the matrix to ensure the
correctness of the program.
\subsection{Optimizing the \class{Matrix} Gamma Table}
\class{Matrix3D} is an customized implementation of the \class{Matrix} Gamma Table.
The matrix basically functions like a two-dimensional array of integers, which consist of rows and columns. Thus, we
implement the Gamma set of the \class{Matrix} table with the customized \texttt{Matrix3D} class, which uses a three-dimensional
array to store all the matrices, including the Matrix A, Matrix B and Matrix AB (result matrix). 
\par The \class{Matrix} table is created with 3D array of integers whose first index represents the matrix number and each
element is a 2D array of the $N \times N$ matrix which the \texttt{row} and \texttt{col} indices vary from 0 to $N-1$.
When a \class{Matrix} tuple is moved to the Gamma Database, it assigns its value to the element by specifying three
field values, including the \keyword{Mat}, \keyword{Row} and \keyword{Col}. Similarly, to retrieve a matrix value, we
can use three fields to get the entry. The source code is shown as follows:
\begin{spacing}{1.0}
\begin{lstlisting}
/** Defines the contents of each matrix. */
package jstar.examples.matrixmult2;
import ...;
public class Matrix3D extends AbstractMatrixTable implements Table<Matrix> {
	final int[][][] data;
	...
	public Matrix moveToGamma(Matrix t) {
		data[t.getMat()][t.getRow()][t.getCol()] = t.getValue();
		return t;
	}
	
	public Matrix queryUnique(int mat, int row, int col) {
		return new Matrix(mat, row, col, data[mat][row][col]);
	}
	....
}
\end{lstlisting}
\end{spacing}
\subsection{Benchmark Results}
\begin{figure}[h]
\centering
\includegraphics[width=0.98\textwidth]{./matrixmult/figure/Speedup.eps}
\caption[Speedups of the optimized JStar MatrixMult program.]
{Speedups of the optimized JStar MatrixMult program with the \class{Matrix3D} and varying Fork/Join pool size on a
quad-CPU Intel Xeon W5590 (total of 32 cores).}
\label{fig:MatrixMultBenchmark}
\end{figure}
\pagebreak
Figure~\ref{fig:MatrixMultBenchmark} shows the speedups of the optimized JStar MatrixMult program, using
\class{Matrix3D} and varying the Fork/Join Pool size. Benchmark results show that this program is an embarrassingly
parallel program with a scalable good speedup of 17.52 (20 cores) and a maximum speedups of 19.90 (28 cores).
\par This high performance is due to the \class{Matrix3D} and the optimisation strategies.
As the \class{Matrix3D} is a fixed-sized data storage, the JVM may use an adjacent memory space to store all the
\class{Matrix} tuples and speed up the program. In addition, the optimisation strategy reduces the total number of
tuples to 1000 in the Delta tree.
\par After applying the optimisations, the Delta tree are inserted with three tuple kinds,
including the \class{MatMultRequest},
\class{MatrixHeader} and \class{MatMultRow}. There is only one \class{MatMultRequest} tuple and \class{MatrixHeader}
are the request tuples which trigger the rules to generate the matrix and start the matrix multiply. The
\class{MatMultRow} tuple is also a request to produce one row of the result matrix, and thus the total number of this
tuple kind is one thousand (each row is a \class{MatMultRow} tuple.)
\par The JStar MatrixMult program would get a better
speedup if the \method{queryUnique} method of the \class{Matrix3D} could be simplified to return the value, instead of
the \class{Matrix} object. This optimisation requires several changes to the Java code generation in the JStar compiler,
it has not been implemented yet.
\section{Conclusion}
In the matrix multiplication case study, we learned:
\begin{itemize}
  \item The JStar parallel implementation can achieve a good speedup up to 20 cores with the best speedup of 19.90 (28
  cores), compared to the JStar MatrixMult program with the optimisations and sequential data structures.
  We believe that the gradual reduction in speedup from 20-32 cores is probably due to the memory bandwidth becoming
  saturated by many memory-intensive tasks.
  \item This program is an embarrassingly parallel program (after we applied the optimisation).
  And it has a high computation to communication ratio because only 1,000 \class{MatMultRow} (per row of the result
  matrix) tuples need to be sorted in the Delta tree and thus result in a low latency between the tuple insertion and rule
  trigger.
\end{itemize}
\cleardoublepage
