\chapter{Case Study: Median-Finding}
The median is the number that splits a collection of numbers into two groups: the higher group and the lower group.
That is, all the numbers in the higher group are greater than or equal to the median, and the numbers in the lower group
are less than the median. To find the median, we could sort the numbers in order and find the middle one. For example,
the median of the 5 numbers \{15, 3, 1, 12, 8\} is 8 because after sorting we have \{1, 3, 8, 12, 15\}.
And if there are an even amount of numbers, then the median is the average of the middle pair (e.g. the median of \{1,
3, \textbf{8}, \textbf{12}, 15, 23\} is 10). However, using a sequential program to sort one million numbers from the
lowest values to the highest ones will take up most of the running time and block the speedup of finding the median.
\begin{table}[h] \centering
\begin{tabular}{ | l | c | l | l |}
\toprule
\textbf{Iteration} & \textbf{Pivot Value}& \textbf{Task 1}& \textbf{Task 2}\\
\midrule
0 & $-$ & \{15, 3\} &\{1, 8, 12\}\\
1 & 7.5 & \{3\} \{15\} &\{1\} \{8, 12\}\\
2 & 11.25 & \hspace{8mm}\{15\} & \{8\}\hspace{2mm}\{12\}\\
3 & $-$ & & \{8\}\\
\bottomrule
\end{tabular}
\caption[An example of the finding-median interative algorithm.]
{An example of the finding-median interative algorithm.}
\label{tab:MedianIterations}
\end{table}
\par An iterative algorithm finds the median for a huge amount of numbers ($N$) by using separate and small-sized tasks,
instead of one sequential task.
This algorithm is described with the above example. First, we split the 5 numbers into two tasks. \keyword{Task 1} gets
the first 2 numbers \{15, 3\} and \keyword{Task 2} gets the next 3 numbers \{8, 12, 1\}.
Second, in each iteration Task 1 and Task 2 both use the same \keyword{pivot value} to split their numbers into two
groups: the numbers that are greater than or equal to the pivot number are put into one group, and the others are put
into the other group. Each group size is reported back to the controller to determine the next pivot value, and the
smaller group is discarded. Repeat this procedure on the remaining groups until the median or a pair of middle numbers
is left.
The iterations are shown in Table~\ref{tab:MedianIterations}. Note that the pivot number is half of the maximal number
and minimal number.
\par The parallel tasks have less computation as each one of them processes only one part of the whole numbers.
Besides, their partition results are compared with the same pivot value at each iteration, so the final result is
guaranteed to be the global median. The JStar Median-Finding program implements this iterative algorithm.
\section{JStar Median-Finding Program}
\begin{figure}[h]
\centering
\includegraphics[height=0.5\textheight]{./median/figure/Median_TableSchema}
\caption{Table schema of the JStar Median-Finding program.}
\label{fig:MedianTableScheme}
\end{figure}
The JStar Median-Finding program finds the median of 100 million random doubles, ranging from 0 to 100 millions (the
List~\ref{sourcecodeofmedian} of Appendix~\ref{ch:mediancase} is the source code).
It is a typical two-phase program: generating the number and finding the median and its table schema is shown in
Figure~\ref{fig:MedianTableScheme}.
The \class{CmdLineArgs} and \class{InitRequest} are used to generate the 100 million doubles and the rests are used for
iterative median algorithm.
\par To ensure that all the numbers are generated in advance of finding the median, tuple orders of the
\class{InitRequest} and \class{CmdLineArg} tables are declared to come before the others, including the \class{Int}.
The \class{Data} table stores the pivot numbers that we need to find the median at each iteration. The
\class{PartitionRequest} table requests the start  of an iteration to split the numbers into two partitions by comparing
them against the pivot number. The \class{PartitionResult} table stores the partition results for each iteration. The
\class{Controller} table gets the partition results and decides the next pivot number, or stops the searching when the
median is found.
So the pattern of communication is essentially a master-slave situation, where the master \class{Controller} rule sends
\class{PartitionRequest} tuples off to $N$ parallel processes and then gets $N$ \class{PartitionResult} tuples back and
decides what to do for the next step. So this application has a lot of parallelism but is not embarrassingly parallel.
since it has a central controller which can become a bottleneck.
\section{Benchmark Configuration}
\begin{table}[h]
\centering
\subfloat[Hardware specification]{
\begin{tabular}{| l | c |}
\toprule
\multicolumn{2}{|>{\columncolor[gray]{.8}}c|}{Symphony node CN-192}\\
\midrule
CPU &  4 x Intel\textsuperscript{\textregistered} Xeon\textsuperscript{\textregistered} 8 core E7- 8837 CPUs\\
& (32 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:MedianGaia}
}\quad
\subfloat[Java Virtual Machine options]{
\begin{tabularx}{0.95\textwidth}{|X|}
\toprule
\multicolumn{1}{|c|}{\cellcolor[gray]{0.8}JVM options}\\
\midrule
\flag{-Xmx64G} sets maximum Java heap size to be 64 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
\flag{-XX:+UseCondCardMark} avoids the false sharing at the card tables in the garbage collection.\cite{website:UseCondCardMark}
\\\hline
\flag{-XX:BiasedLockingStartupDelay=0} enables the objects in the HotSpot by default to be created with biased
locking at the JVM startup.\cite{website:BiasedLockingStartupDelay}\\\bottomrule
\end{tabularx}
\label{tab:MedianJVM}
}
\caption{Benchmark configuration of the JStar Median-Finding program.}
\label{tab:MedianBenchmarkConfig}
\end{table}
The benchmark experiments were conducted on the \keyword{Gaia} computing node of the Symphony cluster in the Waikato
University. Table~\ref{tab:MedianBenchmarkConfig}\subref{tab:MedianGaia} is the hardware specification of the Gaia, and
Table~\ref{tab:MedianBenchmarkConfig}\subref{tab:MedianJVM} lists the JVM options used to benchmark the JStar Median
program. Unlike other case studies, we increased the maximum heap size to 64 GB as the unoptimised program requires a
large heap of memory space to store the numbers and search results.
\section{Performance Tuning Process}
\subsection{In-lining Tuples}
\begin{figure}[h]
\centering
\subfloat[The naive program]{
\includegraphics[width=0.45\textwidth]{./median/figure/Median_Default_Dep}
\label{fig:nativeMedianDependency}
}\quad
\subfloat[The optimized program]{
\includegraphics[width=0.45\textwidth]{./median/figure/Median_Optimized_Dep}
\label{fig:optimizedMedianDependency}
}\\
\subfloat{
	\begin{tabular}{c}
	\hfill TRIGGER(Rule):$\boldsymbol{\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 graph of the JStar Median-Finding program.}
\label{fig:medianDepdency}
\end{figure}
Figure~\ref{fig:medianDepdency} \subref{fig:nativeMedianDependency} is the task dependency graph of the naive JStar
Median program. As the \class{Data} and \class{PartitionResult} tuples are never used as triggers in the program, we 
can use the \flag{noDelta} optimisation to omit their Delta node insertion and put their tuples straight into the
Gamma database. The \class{CmdLineArg} and \class{InitRequest} tuples are used for the random number generation only,
and never queried by other rules. Thus, we can apply the \flag{noGamma} optimisation on these two tables. Similarly,
the \class{Controller} tuple is never used by other rules and acts as a trigger, which starts an iteration to partition
the tasks' numbers and stores their results. We can also apply the \flag{noGamma} optimisation on the \class{Controller}.
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\toprule
\textbf{Tuple} & \textbf{Delta Tree} & \textbf{Gamma Database}\\
\midrule
CmdLineArg		 & $\surd$ & $\times$\\
InitRequest		 & $\surd$ & $\times$\\
Data			 & $\times$ & $\surd$\\
PartitionRequest & $\surd$ & $\surd$\\
PartitionResult  & $\times$ & $\surd$\\
Controller		 & $\surd$ & $\times$\\
\bottomrule
\end{tabular}
\caption{The inline tuple list of JStar Median-Finding program.}
\label{tab:MedianOptimisation}
\end{table}
Table~\ref{tab:MedianOptimisation} is the inlined tuple list.
\pagebreak
\par The \class{Data} table has the most transactions in the JStar Median-Finding program. It is queried by two rules
( \keyword{Rule 3} and \keyword{Rule 4}) and also accepts insertion requests from \keyword{Rule 3} and \keyword{Rule
4}. These recursive insertions and queries on the \class{Data} table may cause a performance issue as the naive
\class{Data} table stores tuples with a
\class{Set} implementation, which has log-time for most operations.\cite{website:JavaSetImplementations}
That is, the JStar Median-Finding program generates 100 million doubles and all of these numbers at each iteration are
stored in the \class{Data} table, so the \class{Data} Gamma table might contain more than thousands of millions tuples
before the median is found. This huge number of tuples makes the Java Garbage Collector busy allocating the memory space
and slows down the performance. Therefore, we designed a new and efficient implementation of the \class{Data} Gamma
table.
\subsection{Optimizing the \class{Data} Gamma Table}
The \class{CHMDataTable} is the alternative \class{Data} table in the Gamma database. It uses one two-dimensional Java
array to store the \class{Data} tuples. Each of the tasks T works on one part of the numbers N and produces an array of
the numbers that will need to find the median in the next iteration. As the \class{PartitionRequest} at each iteration
just needs the \class{Data} tuples from the previous one iteration, two copies of one Java array are enough to keep all
the \class{Data} tuples during all of the iterations. The data storage of the \class{Data} tuples can be reduced to a
fixed-size amount by recursively overwriting this 2D array. That is, the tuples in the current iteration are placed into one
Java array and the tuples in the previous iteration are put into the other. And the index of the array is determined by
modulo 2 of the iteration number.
\begin{figure}[h!]
\centering
\includegraphics[width=0.6\textwidth]{./median/figure/Median_CHMDataTable.eps}
\caption{An example of the \class{CHMDataTable} data structure.}
\label{fig:Median_CHMDataTable}
\end{figure}
\par Figure~\ref{fig:Median_CHMDataTable} is one example that illustrates the 2D array in the \class{CHMDataTable}.
The \class{Data} tuples in the 7th iteration are put in the \keyword{Iter 1} (7\%2) 1D array.
When the program starts the 8th iteration, it looks up the numbers in the array of \keyword{Iter 1}, and then produces
an array of numbers and places them in the array of \keyword{Iter 0}.
\subsection{Benchmark Results}
\begin{figure}[h]
\includegraphics[width=0.95\textwidth]{./median/figure/Benchmark.Median.Speedup.eps}
\caption[Speedups of the optimized JStar Median-Finding program.]
{Speedups of the optimized JStar Median-Finding program with \class{CHMDataTable} and varying fork/join pool size on a
quad-CPU Intel Xeon E7- 8837 @ 2.67GHz (total of 32 cores).}
\label{fig:Benchmark.Median.Speedup}
\end{figure}
Figure~\ref{fig:Benchmark.Median.Speedup} shows the absolute and relative speedup graphs of the optimized JStar
Median-Finding program, using the \class{CHMDoneTable} and the naive implementations (\class{ConcurrentSkipListSet}) for
other Gamma tables. The benchmark results show that the speedups scale well up to 8 cores with a good speedup of 6.30,
and then becomes gradual with the maximum speedup of 13.8 (32 cores).
\section{Conclusion}
In the Median-Finding case study, we learned:
\begin{itemize}
  \item The JStar parallel implementation can achieve a reasonably good speedup (with efficiency greater than 0.5 over
  1\dots24 cores) for an algorithm with a central \class{Controller} bottleneck.
  \item For tables with billions of tuples, it is important to use the efficient Gamma data structures (e.g. Java native
  array) and reuse the space from previous iterations.
\end{itemize}
\cleardoublepage
