%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Chapter 6. PvWatts Case
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Case Study: PvWatts}\label{ch:PvWatts}
The goal of the PvWatts program is to average the power generation (in WATTS) for each month of a year in Brisbane.
All of the hourly power data are generated from NREL's PVWATTS programs. As the amount of records is not very large
(only 8760), the parallel program would finish the computation within few mills-seconds and thus the effects of its
parallelism would be hardly visible. So we replicated each hourly record one thousand times and stored those records in
CSV file. This is the same as analyzing the hourly solar powers output of 1,000 different solar system for a period of
one year. Then we write a JStar program to read this file and calculate the average monthly production. This case study
was chosen because it involves large-scale data input from a file, plus complex dependencies for the analysis of that
data (using several reducers), so speedup is challenging.
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%JStar PvWatts program
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{JStar PvWatts Program}
To implement the JStar version of PvWatts case, we use the \class{CsvReaderTask} library to read all records in a CSV
file. CsvReaderTask provides a \method{parallelRead} method to create a number of Fork/Join tasks to process one CSV
file in parallel. The procedure of parallelRead is described in the follows. First, the CSV file is split into N
individual segments. Then the \class{CsvReaderTask} creates the same amount of Fork/Join tasks so that each segment of
the file is read by one task. Each task uses an efficient \class{FastCSVReader} to read the file segment. The
\class{FastCsvReader} process the files with a reading-on-demand pattern: reading a record at request. Thus, its
performance is improved as it creates few objects and avoids unnecessary \class{String} conversions. The source code of
JStar PvWatts program is shown in List~\ref{sourcecodeofpvwatts} of Appendix~\ref{ch:pvwattscase}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%Table Schema of JStar PvWatts ProgramTikZ
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{./pvwatts/figure/TableSchema.eps}
\caption[Table schema of the JStar PvWatts Program.]
{The table schema of the JStar PvWatts Program.}
\label{fig:PvWattsTableSchema}
\end{figure}
\par The JStar PvWatts program contains five tables: \class{CmdLineArg}, \class{PvWattsRequest}, \class{PvWatts},
\class{PvWattsException}, and \class{SumMonth}.
The table schema is shown in Figure~\ref{fig:PvWattsTableSchema}. After reading arguments from the command line, the JStar
PvWatts program creates one \class{CmdLineArg} tuple for each argument and inserts it into Delta tree.
Before the JStar runtime moves these \class{CmdLineArg} tuples to the Gamma database, it executes the rule associated
with them. This rule creates \class{PvWattsRequest} tuple with the corresponding argument values and puts all of them
into the Delta tree. Then, when each \class{PvWattsRequest} is processed by the JStar runtime, the file path information
is sent to the next rule. Thus, by creating \class{PvWattsRequest} tuples with the values of CmdLineArg tuples, the
information can be passed from the command line arguments to the JStar PvWatts program.
\par When the rule associated with \class{PvWattsRequest} tuple is triggered, multiple readers are used to read the CSV
file in parallel and then output \class{PvWatts} tuples. First, by querying the \class{CmdLineArg} tuples, the rule gets
the given number of readers and creates the same number of \class{CsvReaderTasks}. Since each task is responsible for
one separate segment of the input file, the total work of reading one CSV file can be executed by multiple threads.
Each reader reads one record at one time and parses its fields as primitive data types, such as an integer or a string.
Then one \class{PvWatts} tuple is created with these fields and inserted into the Delta tree. Then the reader reads the
next record and repeats the above procedure to output \class{PvWatts} tuples until all of records in its region of the
file have been read. Note that each reader reads slightly past the end of its region to ensure that each record is read
exactly once.
\par \class{SumMonth} tuples are sorted by yearly and monthly fields in the Delta tree. The \class{PvWatts} rule
processes each \class{PvWatts} tuple and creates a corresponding SumMonth tuple with its yearly and monthly values.
So a number of redundant \class{SumMonth} tuples are generated in this loop as most of them have the same yearly and
monthly values. Since the Delta tree uses tuples as its key values, tuples with identical values are discarded
immediately when they are added to the Delta tree, which avoids triggering duplicate rules.
By inserting \class{SumMonth} tuples into Delta tree, all the months that require calculation are recorded for
processing later, after all input records have been read.
\par Reducers are used to calculate the average monthly power. Each \class{SumMonth} rule queries a collection
of \class{PvWatts} tuples with its yearly and monthly values. Even though the tuples in this collection might be
randomly sorted, the mean calculation will not change its value because it is associative:\\
$$ \forall a,b,c,n \in int,\hspace{2mm}\frac{((a + b) + c)}{n} =\frac{(a + (b + c))}{n}$$\\
As the mean calculation is an associative operation, the \class{Statistic} object implemented from the \class{Reducer}
class of the JStar runtime can be used to average the power generation for each month and print out the final results.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Benchmarking JStar PvWatts program.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section[Benchmark of the Naive JStar PvWatts Program]
{Benchmark of the Naive JStar PvWatts Program}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CN-191 Specification and JVM
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[h]
\centering
\subfloat[Hardware specification]{
\begin{tabular}{| l | c |}
\hline
\multicolumn{2}{|>{\columncolor[gray]{.8}}c|}{Symphony node CN-191}\\
\hline
CPU &  2 x Intel\textsuperscript{\textregistered} Xeon\textsuperscript{\textregistered} quad-core W5590 CPUs\\
& (total of 8 cores @ 3.33GHz)\\\hline
L1 cache & 32K\\\hline
L2 cache & 256K\\\hline
L3 cache & 8192K\\\hline
RAM & 48GB RAM (@1333 MHz)\\\hline
Disk & 2 x 1TB 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:CN191_PvWatts}
}\quad
\subfloat[Java Virtual Machine options]{
\begin{tabularx}{0.98\textwidth}{|X|}
\toprule
\multicolumn{1}{|c|}{\cellcolor[gray]{0.8}JVM options}\\
\midrule
\flag{-Xmx8G} sets maximum Java heap size to be 8 GB.\\\hline
\flag{-verbose:gc} enables verbose garbage collector.\\\hline
\flag{-XX:+PrintCompilation} prints the message when a method is compiled.\cite{website:javahotspotvm}\\\hline
\flag{-XX:+PrintTenuringDistribution} prints the tenuring age information.\cite{website:javahotspotvm}\\\hline
\flag{-Xbatch} stops the program while the hot spot compiler is recompiling/optimising the code.\\\hline
\end{tabularx}
\label{tab:JVMPvWatts}
}
\caption{Benchmark configuration of the JStar PvWatts program.}
\label{tab:PvWattsBenchmarkConfig}
\end{table}
The CN-191 computing node of Symphony cluster is selected to run the benchmarks of JStar PvWatts program and its
specification is shown in the Table~\ref{tab:PvWattsBenchmarkConfig}\subref{tab:CN191_PvWatts}. As CN191 is one of the Symphony
cluster nodes and its computing resources are managed by yhe \keyword{Torque} and \keyword{Maui scheduler}, we followed
standard operating procedures shown in Appendix~\ref{BenchmarkingSOP} to conducted the JStar PvWatts benchmarking
experiments.
\par The performance of the JStar program would partially depend on JVM. To avoid IO communication dominating total
execution time, the output of JStar PvWatts program have been reduced to 40 lines as shown in the
List~\ref{printoutmessagesofpvwatts} of Appendix.\ref{ch:pvwattscase}. Besides, tuning the JVM options can also avoid
the Java garbage collection spending too much time reclaimming memory.
\par Table~\ref{tab:PvWattsBenchmarkConfig}\subref{tab:JVMPvWatts} is the configuration of the JVM options used to benchmark the JStar
PvWatts program. 8G of heap is required to run the JStar PvWatts program as the JStar runtime needs sufficient memory
spaces to store tuples in the Gamma database and the Delta tree which are both in-memory databases.
If the heap size is not large enough, the garbage collector(GC) would be frequently called to free the memory space,
and this would cause delays and degrade the performance.
\par The benchmark experiment measures the total execution time of both sequential and parallel versions of the
JStar PvWatts program, with no optimisation options. Each experiment is repeated 30 times. The average execution time
ignores the results of first 6 runs and takes only the later experiments (7th-30th) into account.
The number of threads ranges from 1 to 8. To illustrate the parallelism of JStar program, the absolute and relative speedup
are plotted on the graph. And their formula are defined as follows:\\
$$S_{abs}=\frac{T_s}{T_p}$$ $$S_{rel}=\frac{T_1}{T_p}$$ where:\\
$S_{abs}$ is the absolute speedup.\\
$S_{rel}$ is the relative speedup.\\
$T_s$ is the average execution time of the sequential JStar program.\\
$T_1$ is the average execution time of the parallel JStar program with one thread.\\
$T_p$ is the average execution time of the parallel JStar program with $p$ threads.
\begin{figure}[h]
	\centering
	\subfloat[Total execution time with varying Fork/Join pool size.]{
	\includegraphics[width=1.0\textwidth]{./pvwatts/figure/Benchmark.Seq.Par.Time.eps}
	}\quad
	\subfloat[Speedup with varying Fork/Join pool size.]{
	\includegraphics[width=1.0\textwidth]{./pvwatts/figure/Benchmark.Seq.Par.Speedup.eps}
	}
	\caption[Performance of the naive JStar PvWatts program.]
{Performance of the naive JStar PvWatts program with varying the Join/Fork pool size on dual-CPU Intel Xeon W5590 @
3.33GHz (total of 8 cores)}
\label{fig:naivePvWattsPerformance}
\end{figure}
\par Figure~\ref{fig:naivePvWattsPerformance} is the benchmarking results of the native JStar PvWatts program on
\keyword{sorted1000X.csv}. It shows that the JStar parallel PvWatts program runs faster than the sequential one with
more than 3 threads.
Both the relative and absolute speedup graph shows that the time of the parallel program decreases as the number of
threads increases to 8.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Performance Tuning Process
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Performance Tuning Process}
As described in Chapter~\ref{ch:tuning}, the PvWatts case is optimized by applying the performance tuning process.
The steps are shown in the following subsections:
\begin{figure}[h]
	\centering
	\subfloat[The naive program]{
		\includegraphics[width=0.30\textwidth,height=0.5\textheight]{./pvwatts/figure/dependency_defaultPvWatts.eps}
		\label{fig:NaivePvWattsTaskDependency}
	}\quad\quad
	\subfloat[The optimized program]{
		\includegraphics[width=0.30\textwidth,height=0.5\textheight]{./pvwatts/figure/dependency_inliningPvWatts.eps}
		\label{fig:InlinePvWattsTaskDependency}
	}\quad\\
	\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 PvWatts program.]
{The task dependency graphs of the native and optimized JStar PvWatts programs.}
\label{fig:pvwatttaskdependency}
\end{figure}
\subsection{Analyzing Tuple Dependency}
The JStar PvWatts program uses a map-reduce programming model for processing a large input file
(\keyword{sorted1000X.csv}).
The program uses one program parameter to locate the input file, then by reading this file with one or more readers, the
program outputs PvWatts tuples to the Delta tree and Gamma database. After the reader finishes its task, the reducers
query these tuples from the Gamma and calculate the power generation during each month. The task dependency graph of the
native JStar PvWatts implementation is shown in Figure~\ref{fig:pvwatttaskdependency}\subref{fig:NaivePvWattsTaskDependency}.
However, this program execution is inefficient because all of the tuples must be inserted into two in-memory data
structures (Delta set and Gamma database). In the PvWatts program, the number of PvWatts tuples is in proportion to the
input file size. When the number of PvWatts tuples increase, the PvWatts program dynamically requests JVM to allocate
more heap memory space. If the maximal heap memory space is not sufficient, then the JVM frequently calls garbage
collector to free and reclaim the memory space. As the garbage collection takes time, the overall performance of the
JStar PvWatts program slows down as well.
\subsection{Inlining Tuples}
\class{PvWatts} and \class{SumMonth} are the tuples which should be inlined to improve the speed of the JStar PvWatts
program.
By analyzing the task dependency graph, we see that the \class{SumMonth} tuples are never queried during the execution
of the program.
Thus, there is no need to move \class{SumMonth} tuples to Gamma database, that is, the \flag{noGamma} optimisation can
be applied to the \class{SumMonth} tuples.
\par Another optimisation strategy is to shift the summation request rule (\method{Rule 4}) to the reading phase. After
the reader loop creates a \class{PvWatts} tuple, it immediately triggers early execution of the \class{PvWatts} rule and
outputs a \class{SumMonth} tuple. That is safe, because the rule does not perform any database
query.\cite{SimonCrosby}
% Therefore, the relationship between PvWatts and SumMonth tuples is modified from a pipeline to a parallel process.
With this change, the \class{PvWatts} tuples are no longer used as the trigger of rules but only for the query in the
reducer loop.
By applying \flag{noDelta} optimisation on \class{PvWatts} table, the reader loop does not insert a \class{PvWatts} tuple
into the Delta tree but directly puts it in Gamma and triggers the \method{Rule 4}. This new strategy improves the
performance of the Delta tree and avoids the unnecessary work, and thus increases the speedup of the JStar program.
\par And the optimized program execution is shown in
Figure~\ref{fig:pvwatttaskdependency}\subref{fig:InlinePvWattsTaskDependency}.
The differences are:
\begin{itemize}
   \item The \flag{noDelta} optimisation: the \class{PvWatts} tuples are no longer put into the Delta tree but directly
   moved to the Gamma database.
   \item The \flag{noGamma} optimisation: the \class{SumMonth} tuples are put into the Delta tree only.
\end{itemize}
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\toprule
\textbf{Tuple} & \textbf{Delta Tree} & \textbf{Gamma Database}\\
\midrule
CmdLineArg & $\surd$ & $\surd$ \\
PvWattsRequest & $\surd$ & $\surd$\\
PvWatts & $\times$ & $\surd$\\
SumMonth & $\surd$ & $\times$\\
\bottomrule
\end{tabular}
\caption{The inline tuple list of the JStar PvWatts program.}
\label{tab:inlinedTuplelistPvWattsCase}
\end{table}
\begin{figure}[h!]
\centering
\includegraphics[width=0.98\textwidth]{./pvwatts/figure/Benchmark.nodeltaPvwatts.Speedup.eps}
\caption[Speedups of the optimisation strategy.]
{Speedups of the sequential JStar PvWatts program with varying the optimisation strategies on quad-CPU Intel E7-4870
@2.40GHz (total of 32 cores).}
\label{fig:PvWattsnodeltanoGamma}
\end{figure}
\par Table \ref{tab:inlinedTuplelistPvWattsCase} is the tuple list of the optimized JStar PvWatts program. The check
symbol ($\surd$) symbol means the tuple is inserted into the data structure and the cross symbol ($\times$) means that
the tuple is not put into the data structure. To illustrate the effects of the above optimisation strategies on the
JStar PvWatts program, we benchmarked the program by applying with one optimisation separately and varying input files
sizes.
\par Figure~\ref{fig:PvWattsnodeltanoGamma} is the benchmark results on one of the computing node in the NeSI cluster
(The submission proceducre to the NeSI cluster is shown in Appendix~\ref{ch:NeSISOP} and the submission job
configuration is in Appendix~\ref{jobconfigofpvwatts}). The speedups in this figure show the effect of applying one
optimisation strategy on the JStar PvWatts program for 5 kinds of input file sizes (1$\times$, 3$\times$, 10$\times$,
300$\times$ and 1000$\times$).
The speedup is the relative speedup to the naive sequential JStar program (without any optimisation).
The results show that as the number of tuples increases, the \flag{noDelta} optimisation scales up the performance with
the maximum speedup of 5.56 on the largest input file (192Mb, 8,760,000 records). But the \flag{noGamma} optimisation
does not increase the speed and provides a little or no scalability on the JStar PvWatts program. We conclude that the
effective optimisation strategy for the sequential JStar PvWatts program is the \flag{noDelta PvWatts} option.
\begin{figure}[h!]
        \centering
        \subfloat[Total execution time with varying Fork/Join pool size ]{
        	\includegraphics[width=0.9\textwidth]{./pvwatts/figure/Benchmark.Seq-Optimized.Par-Optimized.Time.eps}
        }\quad
        \subfloat[Speedup varying with varying Fork/Join pool size]{
        	\includegraphics[width=0.9\textwidth]{./pvwatts/figure/Benchmark.Seq-Optimized.Par-Optimized.Speedup.eps}
        }
    \caption[Performance of the optimized parallel JStar PvWatts program.]
    {Performance of the optimized parallel JStar PvWatts program with two optimisations and varying the Fork/Join pool
    size on dual-CPU Intel Xeon W5590 (total of 8 cores).}
    \label{fig:OptimizedNaivePvWattsPerformance}
\end{figure}
\par The largest input file is used to benchmark the optimized parallel JStar PvWatts program, using the \flag{-noDelta
PvWatts} optimisation and \flag{-noGamma SumMonth} optimisation and varying the number of threads.
\par Figure~\ref{fig:OptimizedNaivePvWattsPerformance} is the benchmark results on the CN-191. From the absolute speedup
chart, the optimized strategy shortens the total execution time of the parallel implementations by 2.52 times, compared
to the sequential optimized one. And the relative speedups show that the optimized parallel program can improve the
performance as the number of threads increases from 1 to 8, with a maximum relative speedup of 3.75. That is, the parallel
optimized program with 8 threads can run 3.75 times faster than the program using one thread. From the above two
benchmark results, we conclude that the optimisation strategies not only improves the speedup but also provides the
scalability for both of the sequential and parallel JStar PvWatts program.
\subsection{Data Structures of the PvWatts Gamma Table}
Regarding the data structures, the \class{PvWattsHashTable} is an customized implmentation of the PvWatts table in
Gamma.
It uses the \keyword{category} concept to design the \class{PvWatts} table data structure.
As the \class{PvWattsHashTable} use the month as its index to insert the \class{PvWatts} tuples, the query of PvWatts
tuples in one month could be performed efficiently.
\par The naive JStar program uses \class{ConcurrentSkipListSet} to create the \class{PvWatts} table in Gamma. We
could improve its parallelism by using other thread-safe \class{Map} implementations, such as \class{ConcurrentHashMap}
or \class{ConcurrentHashMapV8}. By using a customized \class{PvWattsHashTable} and overriding the \method{createGammaSet}
method of the \class{JStarMain} class, these two types of \class{Map} data structures could be used to instantiate the
\class{PvWatts} Gamma database.
\par
\begin{figure}[h!]
\centering
\subfloat[Absolute speedup with varying Fork/Join Pool Size.]{
\includegraphics[width=0.95\textwidth]{./pvwatts/figure/Benchmark.Optimized-Par-PvWatts.AbsoluteSpeedup.eps}
% \label{fig:Benchmark.Optimized-Par-PvWatts.AbsoluteSpeedup}
}\quad
\subfloat[Relative speedup with varying Fork/Join Pool Size.]{
\includegraphics[width=0.95\textwidth]{./pvwatts/figure/Benchmark.Optimized-Par-PvWatts.RelativeSpeedup.eps}
% \label{fig:Benchmark.Optimized-Par-PvWatts.RelativeSpeedup}
}\caption[Speedups of the \class{PvWatts} Gamma table data struture.]
{Speedups of the optimized parallel JStar PvWatts program with varying the PvWatts Gamma table data structure and
the Fork/Join pool size on dual-CPU Intel Xeon W5590 (total of 8 cores).}
\label{fig:BenchmarkOptimized-Par-PvWatts}
\end{figure}
Figure~\ref{fig:BenchmarkOptimized-Par-PvWatts} are the absolute and relative speedup graphs of the optmized
parallel version of JStar PvWatts program, varying the number of threads and the data structures of \class{PvWatts}
tables in the Gamma database:
\class{ConcurrentSkipListSet}, \class{ConcurrentHashMap} and \class{ConcurrentHashMapV8}. Each Gamma table is
constructed with initial capacity of 2,000,000, so that the effect of resizing buckets of Gamma table is avoided, which
results in a better performance.
\par The optimized parallel
program with \class{ConcurrentHashMapV8} with 8 cores runs 3.66 times faster than the optimized sequential program, and
has the slightly better relative speedup than the \class{ConcurrentHashMap} (2.94 relative speedup versus 2.63).
As the \class{ConcurrentHashMap} with initial capacity of 2 million has slightly slow but similar speedups as the
\class{ConcurrentHashMapV8}, the resizing side-effect can be removed by setting up an appropriate initial capacity.
The naive parallel program (with \class{ConcurrentSkipListSet}) with 8 cores has the lowest absolute speedup of 2.49 but
has the best relative speedup of 3.66 because it has the slowest execution time with one thread. Therefore, after
applying the optimisations, we can still increase the speed of the parallel program over its native program by using one
of the concurrent data structures (\class{ConcurrentHashMap} or \class{ConcurrentHashMapV8}) with 2 million capacity.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Bottleneck benchmarks
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Phase Experiment}
Before attempting further parallelism, we need to analyze the workflow of the optimized JStar PvWatts program and find
out what rule/phase mainly limits the improvement on the program speed, so that we could use other tool to solve this
bottleneck problem.
\begin{figure}[h!]
\centering
\includegraphics[width=0.8\textwidth]{./pvwatts/figure/WorkflowOfPvWatt.eps}
\caption{The workflow of the two-phase JStar PvWatts program.}
\label{fig:twophasedJStarPvWatt}
\end{figure}
\par From the Figure~\ref{fig:twophasedJStarPvWatt}, we can see that the program is executed in two
phases: the reader loop and the reducer loop. The reader loop reads the input file and inserts the \class{PvWatts}
tuples into the Gamma database and then puts the \class{SumMonth} tuples into the Delta tree. The reducer loop gets one
\class{SumMonth} tuple from the Delta tree, and averages the PvWatts tuples of one month by making a query to the Gamma
database. The reducer loop must be started after the reader phase. As the reader and reducer are implemented with
parallelism, it is not easy to investigate the bottleneck by looking at the graph merely.
\par The phase experiment is designed to determine whether the bottleneck of the JStar PvWatts program is the reader
or the reducer.
We compiled the JStar PvWatts program with \flag{-seq} flag to generate the sequential Java source code. Then the
\class{Main} class is overridden to execute the program phase-by-phase, so that we could benchmark the reader phase and
the reducer phase individually. And we use the same data structures in all the phase experiments (the
\class{DeltaNodeInt} for the \class{SumMonth} and the \class{TreeSet} for the \class{PvWatts}). The phase experiment
design is described in the following list:
\begin{description}
\item [Phase 0] %(1.72 seconds)
benchmarks the time which JStar PvWatts program reads and parse the input file. At this phase, the program only
uses a single reader to read the file, and counts the total number of records. Hence, no tuples is inserted in either
Gamma database or Delta tree. At the ending, the program prints out the number of records to ensure that JVM actually
executes the codes. Note that as JVM uses Just-In-Time compilation for improving the performance of \keyword{Hot Spot},
JVM would sometimes optimize the program and skip some codes which are not critical for the whole program. Printing
out the variable values can avoid this JVM optimisation.
\item [Phase 1]
benchmarks the \keyword{Phase 0}, plus creating the \class{PvWatts} tuples and put them into the Gamma database.
No \class{SumMonth} tuples are created in this phase.
\item [Phase 2]
benchmarks the \keyword{Phase 0}, plus creating the \class{PvWatts} tuples, plus creating the \class{SumMonth} tuples
and insert them into the Delta tree. The \class{PvWatts} and \class{SumMonth} tuples are both created in this phase.
\item [Phase 3]
benchmarks the \keyword{Phase 0}, plus creating the \class{PvWatts} tuples and put them into the Gamma database,
plus creating \class{SumMonth} tuples and insert them into the Delta tree, plus doing the reducer loop. This phase is
running the JStar PvWatts program.
\item [Phase 10]
benchmarks the \keyword{phase 0}, plus creating the \class{SumMonth} tuples and inserting them to the Delta tree.
No \class{PvWatts} tuples are created in this phase.
\end{description}
\begin{figure}[h]
\centering
 \includegraphics[width=0.9\textwidth]{./pvwatts/figure/Benchmark.Phase.TotalExecutionTime.eps}
 \caption[Performance of the phase experiment.]
 {Performance of the phase experiment with varying the phase on dual-CPU Intel Xeon W5590 (total of 8 cores).}
 \label{fig:Benchmark.Phase.TotalExecutionTime}
\end{figure}
\par Figure~\ref{fig:Benchmark.Phase.TotalExecutionTime} is the benchmark results of the phase experiments.
\keyword{Phase 0} results show that the \class{FastCsvReader} takes 1.24 seconds to finish reading the input file.
We will use this execution time to calculate the phase time difference.
\keyword{Phase 10} has the same time as \keyword{Phase 0}, so putting the \class{SumMonth} tuples into the Delta tree
does not take up significant time and slows down the speed. And this observant result is also consistent to that of the
time difference between \keyword{Phase 1} and \keyword{Phase 2} (\keyword{Phase 1} is roughly equivalent to
\keyword{Phase 2}).
\par The time difference between \keyword{Phase 1} and \keyword{Phase 0} (2.84 seconds) shows that creating all the
\class{PvWatts} tuples and inserting them into the Gamma database takes 2.5 times of the reading task. The difference
between \keyword{Phase 3} and \keyword{Phase 2} (1.15 seconds) indicates that the reducers take roughly the same amount
time as the reading task. 
\par Based on the phase results, the execution time of the JStar PvWatts program can be split into three parts: the
reading task (23\%), the \class{PvWatts} tuple insertion(55\%) and the reducers (22\%). Inserting the
\class{PvWatts} tuples the Gamma database and the reducers are the bottlenecks of the JStar PvWatts program.
In the next section, we will introduce \keyword{Disruptor} to help us to remove the bottlenecks and improve the
speedups.
\section{Disruptor Version}
Disruptor is an order-matching, real-time and in-memory transaction processing system. Compared with other data exchange
approaches, Disruptor has less write contention, a lower concurrency overhead and a more friendly cache mechanism. It
implements a queue approach between concurrent threads that has low latency ad high throughput. It also provides low
levels of jitter, using new designs of producers, consumers and data storage. A key aspect of their design philosophy is
to get the best caching behaviours by having only one thread (core) writing to any memory location.\cite{tech:Disruptor}
\subsection{RingBuffer}
The \keyword{RingBuffer} design of Disruptor solves the data content problem and improves the efficiency of disruptor
applications. By preallocating a fixed size of the memory, disruptor instance uses a block of memory space and forms an
array-like queue to provide the storage for exchanging data among threads. When the consuming threads (\keyword{Consumer})
are too busy to take out the data from the ring buffer, the producing threads (\keyword{Producers}) still can put data
onto the buffer without blocking, until it becomes full.
\par The \keyword{RingBuffer} automatically retains a \class{sequence number} which links to the last item in the buffer,
and is incremented atomically after the producer places a new entry onto the ring buffer. This sequence claiming
principle does not cause any lock if only one producer finds the next available slot on the buffer.
On the other hand, the consumers are given a sequence number which determines the slot to be read from the ringbuffer.
But consumers cannot access this slot and reads data from it until its status becomes available.
Sequence number coordinates the producers and consumers to work together with minimal contention in a multi-threading
environment.
\par The \keyword{RingBuffer} uses a low-latency memory design to improve the performance of Java garbage collector.
As the \keyword{RingBuffer} is a pre-allocated and fixed-size memory space, the JVM tries to use a contiguous
area in the main memory space or possibly the cpu cache line, which can gain a fast access speed by utilizing the
\keyword{cache striding}.
Besides, each slot in the \keyword{RingBuffer} might be overwritten with new data several times during the execution of
a disruptor program. That is, most of the data in the \keyword{RingBuffer} are the short-lived and \keyword{immortal}
objects, which will be referenced once in the program and then never be used again. Because the garbage collector does
not need to move these immortal objects to the tenured memory space, the memory space of these immortal objects can
be quickly reclaimed back and returned to the JVM. The preallocated design and shorted-lived objects of \keyword{RingBuffer}
reduces effectively the burden of the Java garbage collector and works efficiently.
\par The \keyword{RingBuffer} also ensures that there is no message loss among producers and consumers. For producers,
the \keyword{RingBuffer} acts as a queue and allows them to place data in batches without any interruption.
For consumers, the \keyword{RingBuffer} is a buffer that helps them to deal with busy traffic situations without
missing any data.
For example, if the producer outpaces the consumers and puts so many events that consumers could not process immediately,
then these new upcoming events are retained in the ring buffer until the consumers start to process them.
The Disruptor system provides optimized implementations for single/multiple producers and single/multiple consumers,
which are described in the next two subsections.
\subsection{Producer}
The \keyword{single-producer} mode provides mutual exclusion and maintains the execution order. In this case, the \keyword{RingBuffer}
is always accessed by only one thread and no other threads are able to write data on the ring buffer. No writing
contention occurs during the execution and thus there is no need to ensure mutual exclusion with locks or
\keyword{CAS (Compare and Swap)} instructions. This makes the single-producer mode fast and efficient.
\begin{figure}[h!]
 \centering
 \includegraphics[width=0.65\textwidth]{./pvwatts/figure/RingBufferProducer.eps}
 \caption[The workflow between one producer and \keyword{RingBuffer}.]
 {The workflow between one producer and \keyword{RingBuffer}.}
 \label{fig:RingBufferProducer}
\end{figure}
\par The single producer claims events in an ordered and sequential manner. Thus, the consumers will see events in the
same order as the producer adds the events.
Figure~\ref{fig:RingBufferProducer} illustrates the procedure of publishing an event to the ring buffer.
The single producer first asks the \keyword{producer barrier} for the next slot. As the ring buffer keeps track of the current
sequence number(2), the barrier quickly finds the next slot by locating the slot adjacent to the current slot.
Before the producer writes data to the slot, the barrier needs to check the availability of this new slot. If the slot
is still occupied by one of the consumers, then the producer barrier will wait until none of the consumers accesses it.
\par When this slot is ready for writing data, the producer barrier updates the sequence number to the next sequence
number (3) and the producer can start to write data onto it. After completing the writing, the producer tells the
barrier to commit the changes to the \keyword{RingBuffer} and consumers. The producer barrier updates the sequence
number to 3.
And it also publish the slot (3) and notifies all the consumers that the new data on the slot (3) is ready for reading.
\par Disruptor also supports multiple producers publishing events onto the \keyword{RingBuffer} by using a concurrent
version of the claim strategy. By default, the Disruptor uses \class{SingleThreadedStrategy} claim strategy for only one
producer and applies the \class{MultiThreadedStrategy} strategy to coordinate the multiple producers.
The difference between these two claim strategies is the type of variables that they use to avoid the wrapping of the
\keyword{RingBuffer}. The single-producer uses a \class{long} variable as there is no needs for CAS operation.
But the multi-producer one uses an \class{AtomicLong} variable, which has been implemented with lock-free and
thread-safe programming to ensure the atomicity of the sequence number.
\par Producers can claim a batch of slots and publish many events in one step. This batching effect reduces the overhead
costs of the producer and producer barrier, and helps consumers to regain the pace with producers so that the whole
concurrent system is balanced. This effect increases the throughput and helps the Disruptor remain low and flat in
latency.
%as the load and contention increase.
\subsection{Consumer}
Each consumer processes every event put into the \keyword{RingBuffer}, so Disruptor can run multiple consumers
concurrently.
When a slot is claimed by the producer, the sequence number for that slot becomes unavailable and none of the consumers
can read any data from it. Once the producer publishes a slot, the \keyword{RingBuffer} notifies all the consumers that
that sequence number is ready and then consumers can either all read in parallel or take turns to read data from it.
\par To guarantee that any change in a slot would be visible for all consumers, Disruptor uses the \keyword{sequece
barrier} to force all the consumers to wait until the \keyword{RingBuffer} changes its status. And  For example,
when a slot is being written by the producer, its sequence number is blocked from every consumer. After the producer
publishes it, the sequence barrier gives out the reading notification to all consumers. All of the consumers can read
the slot concurrently.
\par The \keyword{consumer sequences} allow consumers to coordinate work on the same entry in an ordered
manner.\cite{tech:Disruptor} Consumers wait for the next sequence number to become available before they read the event
from it. Consumers do not directly interact with the each consumer but use the \keyword{consumer barrier} (that is, a
coordinator of consumers), which tracks the current available reading slot. As each consumer has a separate
\keyword{consumer sequence}, the Disruptor can assign the consumer to read the slot with respect to its own sequence.
\begin{figure}[h]
\centering
\includegraphics[width=0.65\textwidth]{./pvwatts/figure/RingBufferConsumer.eps}
\caption[The workflow among \keyword{RingBuffer} and 12 Consumers.]
{The workflow among \keyword{RingBuffer} and 12 Consumers.}
\label{fig:RingBufferConsumer}
\end{figure}
\par Figure~\ref{fig:RingBufferConsumer} shows the procedure when the barrier grabs three events from the
\keyword{RingBuffer} and sends them to consumers. After the producer publishes the event onto slot 3, the
\keyword{RingBuffer} updates the sequence number to 3 and makes the slots 1-3 all visible to the consumers. When a
consumer asks its consumer barrier about the next sequence number in the \keyword{RingBuffer}, the barrier tells that
consumer the highest sequence number and the number of available slots in the \keyword{RingBuffer} (slot 1, 2 and 3 in
this case).
Instead of directly querying the status of each slot in the \keyword{RingBuffer}, consumers passively wait for the
barrier which tells them what they should read data from.
After requesting the barrier to fetch events from these available slots, each consumer starts to process the events
individually.
The advantage of the single consumer barrier is that it allows the \keyword{RingBuffer} to be read without needing any
multi-reader lock.
% which contains a lock and condition variable to control the concurrent read access to the shared memory and sometimes
% cause a long latency.
Therefore, disruptor has a lower latency performance than other readers-writer framework.
\par A consumer barrier sometimes forces consumers to wait for the next sequence number when the \keyword{RingBuffer}
is too busy to return the number. It uses a waiting strategy to define how consumers should behave when they await the number.
The following introduces each one of these waiting strategies and describes the work flow with the example shown in
Figure~\ref{fig:RingBufferConsumer}.
\begin{itemize}
  \item \class{BlockingWaitStrategy} uses a lock and condition variable to force the consumer to wait for the next
  entries. When consumer 1 awaits the next sequence number, the barrier locks up consumer 1 and causes it to await
  until the cursor moves onto the sequence 4. Since the lock and condition are used to control the waiting
  time for consumers, chances are that this strategy causes a high latency during the execution and thus slows down the
  system performance. As a result, this strategy is not suitable for high performance applications but is suitable for
  the limited CPU resource applications, which demand more threads than the cores on the machine.
  \item \class{BusySpinWaitStrategy} uses a busy spin loop within each consumer while the cursor is moving onto the next
  sequence number. Instead of stopping the consumers working, this strategy keeps the awaiting consumers busy as much as
  possible, and thus consumes more CPU resources than other strategies. But when sufficient cores are available, it is
  the best strategy for the CPU-bounded application which needs high performance and low latency.
  \item \class{YieldingWaitStrategy} yields the threads occupied by the awaiting consumers and gives them back to the
  thread pool, so that other busy consumers can take up these new threads to speed up the overall progress. But this
  strategy occasionally causes latency spikes after some regular intervals.
  \item \class{SleepingWaitStrategy} is similar to \class{YieldingWaitStrategy} but takes a different action when the
  consumers have been waiting for a short duration. Initially this strategy keeps the awaiting consumer spinning.
  After a regular interval, if the curor still has not moved to the next sequence, then the system scheduler disables
  the consumer temporarily (a few nano seconds). When the consumer becomes disabled, it can not accept any command but
  must sleep until the sleep time elapses or the barrier interrupts the consumer.
\end{itemize}
\class{BlockingWaitStrategy} is the only waiting strategy we use in the disruptor version of the JStar PvWatts program.
The disruptor PvWatts program uses only one producer to output PvWatts tuples, and 12 consumers to concurrently
calculate the average power for each month of the year. As a result, there are 13 worker threads and one main thread
running in the thread pool. \class{BlockingWaitStrategy} is designed to coordinate these consumers to work well with
limited CPU resources. \class{BusySpinWaitStrategy} has bad performance when the worker threads outnumber the CPU
cores; thus, it is not a suitable strategy for benchmarking the disruptor program.
\par Instead of spinning the awaiting consumers, both of \class{YieldWaitStrategy} and \class{SleepingWaitStrategy} free
up their resources and give them to those who are busy and in need of threads. But they achieve this goal by calling an
inappropriate method (\method{Thread.Yield} method), which sometimes fails to give the throughput. For example, if only
one consumer needs to do a large workload job and others have finished their tasks, then the scheduler pauses the
threads and give one thread to the busy one.
But in this case, yielding threads does not shorten the total execution time as all the other consumers still have to
wait for the bottleneck consumer to finish the job.
\subsection{Disruptor PvWatts Program}
\begin{figure}[h]
\centering
\includegraphics[height=0.6\textheight]{./pvwatts/figure/WorkflowOfDisruptorPvWatt.eps}
\caption{The workflow of the Disruptor PvWatts program.}
\label{fig:DisruptorPvWatts}
\end{figure}
The Disruptor version of PvWatts program parallelizes the two-phased workflow of JStar PvWatts program.
It uses a single producer and multiple consumers to process all tuples during the execution.
Its work flow chart is shown in Figure~\ref{fig:DisruptorPvWatts} and described as follows.
\par The program initializes the Disruptor instance by specifying the number of consumers, the number of producers and
waiting strategy for the \keyword{RingBuffer}. After the disruptor starts up the ringbuffer, one producer and 12
consumers, the producer starts doing the \keyword{CSV read loop} tasks: reading the large input file, generating all
\class{PvWatts} tuples, publishing these tuples in batch mode and sending out a sentinel tuple after all lines in the
input file have been processed. At the same time, each consumer starts to claim the \class{PvWatts} tuples from the
\keyword{RingBuffer}.
\par To reduce the workload of \keyword{reducer loop} and improve the parallelism, the Disruptor PvWatts program assigns
a separate month value to each consumer. Thus, each consumer just needs to process the \class{PvWatts} tuples of one
month and put these tuples to its own and local Gamma database. Besides, the consumer also creates one corresponding
\class{SumMonth} tuple for each \class{PvWtts} tuple and inserts this tuple to a local Delta tree. When a consumer
receives the sentinel tuple, it processes the \class{SumMonth} tuple in its own Delta tree and triggers the reducer loop
to output the average monthly power generation. Then the reducer queries the tuples in the Gamma table, sums up the
watts values and prints out the averaged monthly power generation.
\par The producer places tuples onto the ring buffer in batch mode: claiming and publishing upto 256 events each time.
Since there is only one producer in the program, the \class{SingleThreadedStrategy} strategy is used to claim the slots
in the \keyword{RingBuffer}.
But consumers read one event from the ring buffer each time. Thus, each consumer gets the \class{PvWatts} tuple in the
same slot when they receive notification from \keyword{sequence barrier}.
As the same slot could be accessed by 12 consumers concurrently, \class{BlockWaitStrategy} is set up for defining the
behaviour of multiple reading operation on the \keyword{RingBuffer}. According to the sequence number, each consumers
reads one slot in parallel and the publisher is blocked from writing to the slot until all the consumers finish their
reading.
\begin{table}[h]
\centering
\begin{tabularx}{\textwidth}{| l | X | X |}
\toprule
\textbf{Category} & \textbf{Parameter} & \textbf{Value}\\
\midrule
RingBuffer & Event & PvWatts(Builder)\\\hline
RingBuffer & Size & 1024\\\hline
RingBuffer & Wait Strategy & BlockingWaitStrategy\\\hline
RingBuffer & Claim Strategy & SingleThreadedClaimStrategy\\\hline
Producer & Number of Producer & 1\\\hline
Producer & Batching Size & 256\\\hline
Producer & Task & Read input file, create PvWatts tuples and place tuples onto the ring buffer .\\\hline
Consumer & Number of Consumers & 12\\\hline
Consumer & Batch Size & 256\\\hline
Consumer & Task & Put PvWatts tuples to Gamma database and process the SumMonth tuple from Delta Tree.\\
\bottomrule
\end{tabularx}
\caption{The configuration of the Disruptor PvWatts program.}
\label{tab:DisruptorOPs}
\end{table}
\pagebreak
\par The single-producer and multiple-consumer design removes the possibilities of contention occurring in the procedure
of JStar PvWatts program, provides data locality and pipelines the reducer and the consumers.
The summarized Disruptor configuration is shown in Table~\ref{tab:DisruptorOPs}.
\subsection{Benchmark Result}
\begin{figure}[h!]
\centering
\includegraphics[width=0.95\textwidth]{./pvwatts/figure/Benchmark.Disruptor.TotalExecutionTime.eps}
\caption[Performance of the JStar and Disruptor PvWatts Programs.]
{Performance of the sequential optimized JStar and Disruptor PvWatts Programs on two kinds of input files
(\keyword{sorted} and \keyword{unsorted}) on an 8-core machine (Intel i7-2600 with 4 cores + hyperthreading).}
\label{fig:Benchmark.Disruptor.TotalExecutionTime}
\end{figure}
The benchmark experiments were carried out on an Intel i7-2600 quad-core machine to evaluate the speed up of PvWatts
program between the Disruptor version and the sequential optimized version. The performance of this experiments is
measured by using speedup, which is computed on the basis of the total execution time of sequential inlined JStar
PvWatts program.
According to the \keyword{Amdahl's Law}, the theoretical maximum speedup with one producer and N consumers is:
$$Speedup(N)=\frac{1}{B+\frac{1-B}{N}} $$
\par Assume that $B$ is the percentage of the program that must be run in
sequential.
From the phase experiments, the reading phase takes 1.24 seconds. The sequential percentage of JStar PvWatts program is
$19.5\% (1.24/6.351)$. The maximum speedup with 12 consumers is 3.8 ($\frac{1}{0.195+\frac{0.805}{12}}$).
Figure~\ref{fig:Benchmark.Disruptor.TotalExecutionTime} shows that the Disruptor PvWatts program has the speedup of 3.3
on the unsorted input file (\keyword{large1000X.csv}) and the speedup of 2.5 on the sorted input file. This speedup is
fairly good, compared to the theoretical speedup.
\section{Conclusion}
In the PvWatts study, we learned:
\begin{itemize}
  \item The optimized JStar parallel code gives a reasonably good speedup upto 4 cores with the maximal speedup of 3.53
  (8 cores), compared to the sequential optimized JStar PvWatts program.
  \item This program is a two-phase program and hard to parallelize as it has the bulky I/O communication and uses
  the complex data structures.
  And it is Gamma database dependent because at least 8.7 million \class{PvWatts} tuples must be inserted in or queried
  from the Gamma database.
  \item The Disruptor PvWatts program obtains a fairly good speedup of 3.3 with a single \keyword{RingBuffer}
  (size of 1024), one producer and 12 consumers. This speedup is very closed to the theoretical speedup from the
  Amdahl's Law.
\end{itemize}
\cleardoublepage
