\chapter{Introduction}\label{ch:intro}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Chapter 1. Introduction %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Goals}
% Short description JStar.
JStar is a new declarative language for parallel programming that encourages programmers to write their applications
with implicit parallelism.\cite{tech:datalog} With JStar, programmers do not have to think how to make the program run
in parallel, and they can just focus on the semantic of their algorithms and the order of execution. A key goal of JStar
is that by applying optimization options, the JStar compiler can translate a JStar program into efficient sequential or
parallel Java source code for a given architecture, without changing the JStar source.
% Single-core.
\par Computers are all composed of at least one central processing unit (CPU) and a memory space for reading and
executing the program instructions. Modern cores are implemented as silicon chips, which contain computing
components and small circuits on it. Due to a large number of required circuits, early cores were large and
power-consuming. Since the integrated circuit technology was invented, the transistor size has greatly reduced each
decade by the continuous drive of \keyword{Moore� law}, allowing faster clock speeds and more sophisticated architectures.
By making the line width as small as 20 nano-meters, a CPU is able to contain over billions
of transistors and electronic components, and thus the computing power can also be improved. However, this method is
facing technological and financial challenges as the transistor size is approaching the miniaturization limit.
% Multi-core core.
\par Adding more cores on a single CPU is an alternative to increase the computing power. Ideally, the multi-core
CPUs can multiply the speed of a program by the number of cores and shorten the communication time by sharing the
same cache and bus interface. In fact, the parallel program often fails to scale up to large number of cores and
has difficulties to be portable across heterogeneous platforms. Before this thesis started, the JStar compiler could
generate sequential Java code, and a prototype parallel runtime based on the Fork/Join library and splittable
\class{Hashsets} has been developed, but this has only been applied to one case study (matrix multiplication), where
it showed the poor scalability\cite{JamesBridgewater}.
% Describe project goals: speed, scalability, and cpu usage.
\par This project aims to improve the performance of parallel JStar programs with concurrent data structures and
efficient utilization of computing resources. Our goals are described as follows:
\begin{description}
\item[Speed] is the execution time that a JStar program completes a given problem. The goal is to maximize the
speed and minimize the total execution time of a JStar program.
%  in comparison to the hand-written Java programs.
\item[Scalability] is the ability of a JStar program to increase its speed as the number of cores increases. The
goal is to make the scalability as linear as possible.
\item[Resource Usage] is the total amount of computing resources which a JStar program uses. The
goal is to minimize the usage, including the heap size, memory bandwidth, CPU usage, and garbage collection.
\item[Portability] is the ability of a JStar program to be run on multi-platforms. The goal is to directly run
a JStar program across different platforms without extra efforts, such as rewriting the source codes or re-compilation.
\end{description}
\par All of our goals will be explained with a photovoltaic (PV) energy system example in the next section.
\section{PvWatts Example}
% Compared against pure java version of program.
% Describe the PvWatt example.
A photovoltaic (PV) station is a solar energy production system with arrays of solar panels. It can continuously convert
the sunlight into the direct current electricity (DC Power). Compared to other power generation methods, the PV energy
generation method produces no pollution when operating and uses sustainable energy sources.
Furthermore, the solar panels are easily mounted on the rooftop or on the ground.
The solar power has many benefits to the environment and human beings so that many people have started to be interested
in the PV station installation.
But the energy production of a PV station is mainly determined by the weather. Thus, the location becomes an important
issue for a PV system.
\par NREL(National Renewable Energy Laboratory) provides a tool to assist people to make this decision. The
\keyword{PvWatts} program\footnote[1]{See http://www.nrel.gov/rredc/PvWatts/} is an energy calculator, simulating a PV
energy system in a area and estimating the hour-by-hour power production.\cite{pvwatts:2001} The PvWatts program uses
the historic weather data in a location to determine the intensity of solar radiation on the PV arrays. By using the
parameters of solar arrays and the efficiency of power conversion, the PvWatts program estimates the energy generation
(in Watts) for each hour of the year. And all the estimated records for a typical meteorological year (TMY) are exported
to a data file (a CSV file). This file consists of one year of records, where each row in the table represents one
energy record.
The hourly record is composed of the time data and the AC power. The time data has 4 fields: year, month, day, and hour.
And the AC power is the electricity wattage generated during an hour.
% Speed and Resource Usage.
\par The parallel JStar PvWatts program could make use of the multi-core computing power to shorten the execution time and
increase the speed. As this program calculates the total power generation for each month of the year, it reads each
hourly record in the file and averages the monthly energy production. The program starts by parsing
command line arguments, and ends with printing out monthly power production for a PV station. Because the PvWatts program
uses readers to read each record in the table, I/O communication between the data file and system memory may limit its
execution time. Through the JStar parallelism, the speed of a JStar program could increase as the number of employed cores.
\par The parallel JStar PvWatts program could reduce the memory usage during the execution.
As the input file contains a large number of hourly records, the program could use most of the memory space to create
the data objects, which are used at one time. These short-lived objects may cause load on the Java garbage collector,
or worse, may lead to the out-of-memory error. To avoid downgrading the performance from the busy garbage collector,
the JStar parallelism should efficiently utilize the memory space on the multi-core machine and also ensure the program
to function correctly.
\par The parallel JStar PvWatts program should be run on the multi-core machine without changing the original JStar
source program but simply by setting the number of cores (threads). As each parallel hardware has different
characteristics, porting a parallel program often requires the programmer to rewrite and recompile the source code.
But rewriting the program sometimes may have a good performance but introduce unexpected errors during the execution.
The JStar parallelism should implicitly hide the parallel hardware and provide a simple mechanism to make use of the
multiple cores.
\section{Definitions}%speedup, scalability, performance
\subsection{Workload}
% Introduce the JVM
The Java application is a sequence of actions expressed in Java language. A Java program needs to be compiled into the
platform-independent byte-code, so that the Java Virtual Machine (JVM) can execute it.\cite{JDK7API} JVM is not real
hardware but a computer program. It provides a run-time environment for the Java byte-code and can be run on
heterogeneous computer systems. JVM makes the Java applications to be portable across a variety of platforms.
Apart from dynamic memory allocation, the JVM can use a fixed-size memory space (heap) to store objects during the
execution of a program.
The JVM has three definition for computation workload\cite{JDK7API}:
\begin{description}
\item[Task] is a set of the program instructions. It is the smallest unit to measure the application's
workload. In JStar language, a task is regarded as a \keyword{Rule} which use the input tuples to do some computation
and output the tuples.
For example, one rule in the JStar PvWatts program is triggered after a request from command line argument is
received. It reads lines from the input file, parses the fields and creates \class{PvWatts} tuples with the
the date and time and the hourly power production.
\item[Thread] is used to execute one or more tasks.
\item[Process] is an execution environment which can manage its own memory space and execute many threads in
parallel. A single process can execute the threads in the thread pools to run tasks.
\end{description}
\par The process and thread both have many common characteristics.\cite{website:JavaProcessesandThreads} They both
provide a execution environment. But a process has better control over its memory space.
The JVM is an example of a single process. As the threads are created and executed in one pool inside the JVM, threads
inside a process can use the process's memory space to communicate with each other.
% Therefore, the chances of
% \keyword{context switch} among the threads (the overhead costs of inter-threading communication) are reduced and result
% in a better speedup of thread execution.
A thread is a light-weight process, taking up fewer resources than a process and quickly being created and destroyed.
A thread can execute short-lived tasks efficiently while a process can execute the threads concurrently.
\par Multi-process applications are more complicated. Because inter-process communication requires additional
implementations, such as the message passing interface, or the remote procedure calls.
Thus exchanging the messages among the processes takes longer than in an multi-threading application and may cause
latency problems.
% Ideally, a parallel task is independent of others, that is, the starting and ending time of a thread is irrelevant to
% others. With multiple threads and parallel tasks, a process is able to execute the program concurrently on a
% multi-core or multiple-cores machine.
\subsection{Executors}
The \keyword{Executors} class is one of these high-level concurrent objects provided by the Java platform.\cite{JDK7API}
% \keyword{concurrent} data structures, and \keyword{atomic} variables.
The \keyword{Executors} class provides a separate way of launching and managing the threads in a Java concurrent
application.\cite{website:JavaTutorial} Using the executor can separate the application from the thread management.
The executor creates all the threads automatically in a pool.
When a thread finishes its task, the executor would either reuse it to do other tasks or destroy it permanently.
As the executor manages the threads from creation to termination, Java programmers do not need to write extra
code to deal with the thread life-cycle issues, which would sometimes cause dead lock. Two executor implementations are:
\begin{description}
\item [Thread Pool] is introduced in JDK 1.5 and widely used in concurrent applications.\cite{JDK7API} In the pool,
the executor creates a number of \keyword{worker threads}, which are able to perform tasks on behalf of the
application. A worker thread can normally execute multiple tasks, so the number of threads is often less than
the number of tasks. After a thread completes its task and returns its result, it would continue taking up a new task
until all the tasks have been processed.
\item [Fork/Join Framework] is implemented on JDK 7 and tries to use all computing power of the multi-cores machine.\cite{JDK7API}
Like other Java threading frameworks, the Fork/Join framework uses a \class{ForkJoinPool} to host all worker threads and
distribute tasks to them. The \class{ForkJoinTask} is a task that runs within the \class{ForkJoinPool}.
At the beginning, an initial ForkJoinTask is submitted to the pool and executed by a worker thread automatically.
This main ForkJoinTask is split into more ForkJoinTasks by recursively calling the \method{Fork} method and these subtasks
are asynchronously executed by other available threads. When a worker thread receives a task, the thread will either
split the task or process it immediately. If the task work is too heavy, then the thread will split this task into two
sub-tasks, submit them to the pool for future execution (waiting for their result).
Otherwise, the thread will execute the task and return its result immediately. The \keyword{split-merge} procedure will
not stop until all of the sub-tasks have been completed and the main task gets its results.
\end{description}
\begin{figure}[h!]
\centering
\includegraphics[width=0.8\textwidth]{./intro/figure/ForkJoinTask.eps}
\caption{The \class{ForkJoinTask} diagram}
\label{fig:ForkJoinTask}
\end{figure}
\par Figure ~\ref{fig:ForkJoinTask} illustrates the procedure of the Fork/Join framework. When the \keyword{main}
ForkJoinTask is submitted to the ForkJoinPool, this main task will be split into two sub-ForkJoinTasks (B and C) by one thread.
When a thread starts computing the left subtask, the right sub-task will be split into two sub-tasks (D and E). When two
individual threads start to run Task D and Task E, Task B is being held and waiting for the completion of Task D and Task E.
After summing up the results of Task D and Task E, Task B rejoins the Task A. Once Task C finishes,
Task A aggregates the results of Task B and Task C, and outputs the final result.
\subsection{Dependency and Granularity}
\begin{figure}[h!]
\centering
\includegraphics[height=0.6\textheight]{./intro/figure/Dependency.eps}
\caption{Task dependency graph of a JStar program.}
\label{fig:Dependency}
\end{figure}
\keyword{Dependencies} define the execution sequence of tasks. Dependencies can ensure that the behaviour of a program is run
according to what users expected. We will demonstrate the task dependencies with the JStar PvWatts example.
Each JStar task is composed of one rule and its output tuples, and optional the query tuple.
The \keyword{Rule} is the task and sometimes needs tuples from other tables (query tuples).
After finishing the computation, each rule/task outputs tuples which is used to trigger other tasks. The order
of tuple execution are formed in a connected graph, as shown in the  Figure~\ref{fig:Dependency}.
Even though the task dependencies may limit the parallelism, they provide a way of reasoning the correctness of a JStar
program. For example, sorters are used to categorize the \class{PvWatts} tuples by the month value.
The sorters in this program are used to force the reducers to wait until the readers finish their work.
Even though the sorters prevents the concurrent execution of the reducers and the readers, they ensure that the reducers
obtain a complete and full set of the \class{PvWatts} tuples and output the correct final result.
\par The \keyword{granularity} can relax the constraint caused by the task dependencies. Based on the frequency across
the threads, the granularity is classified as \keyword{coarse} or \keyword{fine}. The coarse-grain computation refer to
the loose dependencies among threads while the fine-grain one refer to the close dependencies.
For example, if the JStar PvWatts program uses two readers to read the input file in parallel, then the file will be
divided into two segments and two readers are created to read each one of them concurrently.
Since each reader just needs to read one half of the whole records, the reading time can be shorten.
However, if the file is chopped too fine, then the program will create too many readers and cause the increase of the
overhead costs and reduce the benefits of granularity. For example, if we use millions of parallel readers, then
streaming each file segment will take up a lot of time and slow down the performance.
Besides, compared with a single reader, the parallel readers need to spend the extra time synchronizing records.
So the level of granularity should be set up to meet the hardware specification and the users' needs.
\subsection{Latency and Throughput}
\begin{figure}[h!]
\centering
\includegraphics[width=0.8\textwidth]{./intro/figure/Latency.eps}
\caption{The Low-Latency and High-Latency diagram.}
\label{fig:latency}
\end{figure}
The \keyword{latency} refers to the amount of time to complete a unit of work and the \keyword{throughput} are the
amount of work that can be finished per unit time. They are both used to measure the performance of a parallel program
but have different ways of achieving the parallelism. Figure~\ref{fig:latency} illustrates the difference between the
low and high latency. The low-latency runs each task one after one and the high-latency run each task with an overlap of
starting time. The low-latency method has the shorter task time but a longer completion time than the high-latency as
the task needs to waiting for the last task. The low-latency method can have a shorter task time but the high-latency
have a better throughputs. Note that the latency can be hidden by using the multi-core machine. When one thread
is executing a high-latency task, the multi-core machine may create two or more threads to do other tasks on the same
core.
As these threads share the data in the cache of the core, the latency from the memory can be hidden and thus the
execution time will be shorten.
But this method does not really reduce the latency but the number of requests to the main memory.
\subsection{Locality}
\begin{figure}[h!]
\centering
\includegraphics[width=0.8\textwidth]{./intro/figure/IntelCoreI7Sandy.eps}
\caption{The Intel multi-core processor diagram.}
\label{fig:IntelCore}
\end{figure}
The \keyword{cache} is the memory space between the cores and the main memory space and has been implemented widely in
the modern CPUs for its low-latency performance. By pre-fetching the recent data off the main memory, a core can
directly read and write the data in the caches without the communication between the memory buses and the controllers.
As the cache increase accessing speed, the overall performance can be improved. Figure~\ref{fig:IntelCore} illustrates
the memory reference in a multiple cores environment.\cite{website:Inteli72600} According to the cache block size, the
caches are classified into three hierarchies: Level 1 (L1), Level 2 (L2) and Level 3 (L3).
\begin{itemize}
  \item \keyword{L1 cache} is the smallest and fastest cache. It stores the copies of data which are the most
  frequently used in main memory.
  \item \keyword{L2 cache} is the next larger but slower cache, compared with L1. It can hold a chunk of data items near 
  or next to the recently used data. 
  \item \keyword{L3 cache} is the largest but slowest cache. It can hold a bigger chunk of data items than L1 and L2.
\end{itemize}
\par L1 cache and L2 cache are usually located inside an core whereas the L3 cache is shared among multiple cores.
After receiving a request for making data reference, the core first checks L1 cache, followed by L2 cache and L3 cache.
If the data reside in any local or shared cache, the core will make a direct and fast reference (\keyword{cache Hit}).
Otherwise, the core has to access the data from the external main memory (\keyword{cache
Miss}).\cite{Lin:2008:PPP:1796038}
\par The cache miss causes a higher latency than the cache hit for the requests to access the main memory through the
system bus. Besides, when the multiple threads update the same data in the memory, they may compete each other for its
ownership, which results in \keyword{race conditions}.\cite{Lin:2008:PPP:1796038} The effect of race conditions may slow
down the performance as threads are racing each other to access the data. But using the \class{mutex} may avoid this
problem. Assume that the PvWatts program uses a mutex to ensure the mutual exclusion: only one thread can access the
shared data file.
When a thread is reading the file, the file's mutex is set to be \keyword{locked} and other threads have to wait until
its state becomes \keyword{unlocked}. Even though the atomicity of this file is guaranteed by the mutex, the parallel
PvWatts program will run slower than the sequential one as each thread has to spend the extra time waiting until the
mutex becomes unlocked.
\par A program frequently reuses the data in the same location or within the nearby memory space. Based on the time
duration and data reference, the locality of reference is divided into two categories:\cite{Lin:2008:PPP:1796038}
\begin{itemize}
  \item Temporal locality: the program might reuse the specific data which have been referenced recently.
  \item Spatial locality: the program might reuse the data items which are relatively close to the recently accessed item.
\end{itemize}
\par The locality rule is to maximize the number of the local references and minimize the number of non-local reference.\cite{Lin:2008:PPP:1796038}
This rule tries to reduce the dependency between the threads and tasks, so that the parallel program can run faster
because most of the communication latency and memory contention are avoided.
To illustrate the locality rule, consider the multiple PvWatts reducers which are used to sum up the power for each
month.
Each reducer queries the tuples from the same table in the database.
The tuples of a month are stored in the neighbouring area of the memory space, because they have been sorted by their
date and time field values. Thus, the program would fetch a chunk of tuples to the CPU cache and the reducer might get
the tuples directly from the cache without the access of the main memory. The performance can be improved as the cache
provides the faster speed than the memory.
\subsection{Speedup}
The \keyword{speedup} is the main performance index for a parallel program. The \keyword{execution time} is from the
time when the first core begin executing the program to the time which the last core completes execution. But execution
time does not indicate how the parallelism scale up the program. The speedup is defined as the execution time of a
sequential program divided by the execution time of a parallelized program that has the same result. But speedup has
many issues and may lead to wrong interpretation. The follows are some factors that may affect the speedup and lead to
performance loss.\cite{Lin:2008:PPP:1796038}
\begin{enumerate}
  \item The different parallel machines may affect the speedup although they use the same architecture. This is because
   some of the components they use are slightly different or may have been upgraded with the new generation of technology.
  \item The JVM options would affect the speedup. For example, turning off the compiler optimization may increase the
  execution times of a parallel program. This change affects the speedup and leads to the incorrect interpretation.
  To avoid this error, the compiler options should be reported along with the program execution.
  \item The relative speedup is the speedup relative to the execution time that the program runs with a single core (thread).
  It is necessary when the problem size is too large to be fit into a sequential program.
  \item The JVM warm-up affects the final execution time. The cache behaviour in the first few runs is not
  well-formed and have more chances of cache misses than the later runs. So the total execution time
  in the first run is always the longest one.
  Running the program several times or more can warm up the caches and reduce the chances of cache misses.
  So averaging the execution time in the later runs can get a stable and real speedup.
  \item Some off-core activities (e.g. writing to/reading from disk) could dominate the execution time and completely
  destroy the parallelism.
\end{enumerate}
\subsection{Efficiency}
\begin{figure}[h!]
	\centering
	\includegraphics[width=0.8\textwidth]{./intro/figure/Efficiency.eps}
	\caption{The efficiency chart of a program on a 8-core machine.}
	\label{fig:Efficiency}
\end{figure}
%Give an example of efficiecy and draw a garph.
The efficiency of a program is the normalized speedup (the speedup divided by the number of cores).\cite{REF03}
It shows how much time faster each CPU is used on the parallel program than on the sequential one.
The efficiency of 1.0 means that the speed increases linearly to the number of cores.
The efficiency is always less than 1 and decreases as the number of cores increase. As shown in
Figure~\ref{fig:Efficiency}, the parallel program using a single thread takes up most of CPU time whereas the same
program executed with 8 threads has the least amount of CPU time.
\par Some programs can solve the problem faster by simply adding more number of threads. But the speedup can not always
be improved in such a way and has a theoretical limitation, depending on how much a program is parallelized.
A parallel program contains a sequential part and a parallel part.
Using a multi-core machine can speed up the parallel part but not the sequential one.
So the speedup of a parallel program is limited by the sequential part.
The more of a sequential part in a program relative to the parallel part, the poorer speedup the program gets.
\par \keyword{Amdahl's law} defines the maximal speedup a parallel program can achieve with additional computing
resources. Assume that we have a machine with $N$ cores and $F$ is the sequential fraction of the program.
The maximal/theoretical speedup is\cite{REF03}:
\[
 Speedup \leq \frac{1}{F+\frac{(1-F)}{N}}
\]
As the $N$ increases to an infinite, the speedup is close to $1/F$. This means that the speed of a parallel program
would converge to a constant (the inversion of its serial fraction) and could not have any improvement by adding more
number of cores to the machine. For example, the program with a quarter of sequential parts can at best have a speedup
of four regardless of the number of cores.
\subsection{Scalability}
% Definition of scalabity and relate it with speedup and efficiency.
Deciding a problem size is difficult. If the problem size of a program is small enough to fit or be handled on the
single-core machine, then it is unreasonable to run this program on the multi-core machine. In order to get a fairly
good performance on the multicore machine, the problem of a parallel program should be scaled up as the number of cores
increases.
The scalability of the problem implies\cite{REF03}:
\begin{enumerate}
\item The design of the many-core or multi-core machine does not requires a high-frequency CPU as the multicore machine
with low-frequency CPU can achieve a similar or close performance as the high-speed single core.
\item The software batching technique will be widely used in the parallel program as it decreases the overhead costs of
communication among threads and improves the efficiency by performing the latency-hiding technique.
\item The problem size of a parallel program should be scalable to maintain the efficiency when more cores are added
to run the program.
\end{enumerate}
\subsection{Performance Trade-Offs}
The performance of a parallel program can be affected by a variety of factors, e.g. the communication costs, task
dependencies and the CPU idle time. And the factors are dynamic as they may vary from one problem to another.
And each factor may have a trade-off relationship with the others. That is, lowering one factor may result in an
increase of others. The common performance trade-offs in a parallel program are described as follows:\cite{REF03}
\begin{enumerate}
\item Communication costs are reduced by the independent parallel tasks.\\
Each independent computation can be run by one thread without any communication cost or waiting time among tasks.
But the independent task may create some redundant computations to remove the task dependencies. For example, an input
file needs to be split into several parts so that each reader can take one part to process in parallel.
Even though the redundant computations increase the costs, the communication costs can be reduced.
\item The parallelism often requires a large amount of memory.\\
If the data are too big to fit into the cache, then they will be moved into the main memory space which has the slower
speed than the cache. To make use of the cache as much as possible, the \keyword{privatization} and \keyword{padding}
methods can be used to reduce the memory usage in a program.
The privatization is to replace the shared/global variables with the private/local ones.
The benefit is that the thread does not have to interact with shared memories all the time even though the privatization
requires the additional memory costs.
The padding is to make each thread to do the same portion of a task so as to keep the variables on the same cache line.
Padding can make those dependent variables to be independent, that is, to remove the false sharing and improve the
performance.\cite{website:UseCondCardMark}
\item Overhead costs prevent the parallelism.\\
Consider the following three trade-offs between the overhead cost and the parallelism.
\begin{inparaenum}[\itshape a\upshape)]
\item 
The overhead cost occurs when one reducer accumulates the results from all of the threads. This reducer can be the
bottleneck for the performance in this case. But if the intermediate combiners are used to categorize the data before
the reducer, then the summation workload can be parallelized by using the multiple reducers.
\item 
The fine-graned task can improve the load balance than the coarse-grained one. The coarse tasks have different workload
and different completion time. This unbalanced workload may cause some threads to be busy all the time while some are
idle and waiting for other threads. But over-decomposing a task may lead to an increase in the communication costs.
\item Batching technique can improve the parallelism by performing a group of tasks rather than one task at one time.
But batching processing may cause the contention or the race conditions and reduce the efficiency.
\end{inparaenum}
\end{enumerate}
\subsection{Perfect Parallelism}
Perfect parallelism is when the execution time of a program is sped up in proportion to the number of cores.
The following reasons explain why it is hard to achieve perfect parallelism.\cite{REF03}
\begin{enumerate}
\item Parallelism has expensive overhead costs.\\
The overhead costs of parallelism are communication costs, synchronization costs and memory usage.
Some communication costs can be avoided but some can not (e.g. the shared memory communication).
Synchronization costs are hard to detect as the messages are passed between threads. And the memory size sometimes can
constrain the performance of a parallel program.
\item Some computations are non-parallelized.\\
Non-parallelizable parts in a program are those which must be executed in sequential.
Amdahl� law shows that the maximum performance of a parallel implementation is determined by its sequential fraction
(the ratio of its sequential computations over all its computations).
That is, the sequential computation limits the maximal speedup of a program.
\item The idle time is never avoided.\\
The CPU idle time results from the unbalanced and memory-bound computation.
The unbalance load means that each core has different amount of workloads.
Running a sequential program on the multi-core machine would incur this problem.
The memory bandwidth constraint is still a problem to the parallel programming when the CPUs write/read the data from
the memory.
\item Contention causes the slowdown of whole system.\\
Contention decreases the speed of a program because it increases the workloads on the memory and shared memory bus.
\end{enumerate}
\section{Contributions}
This section lists the main improvements to the JStar compiler, methods, results, and tools that have been achieved.
During this thesis, they include:
\begin{enumerate}
  \item Added the \flag{-seq} and \flag{-par} options to the JStar compiler, so that users can easily generate code for
  either sequential or parallel machines. Before our thesis, a Fork/Join prototype was developed for JStar. It was
  based on splitable hashsets of tuples, so this prototype had poor speedups and significant overheads for tuples with
  small amount of computation.\cite{JamesBridgewater}
  \item Defined two optimisations (\flag{noDelta} and \flag{noGamma}) to reduce the number of tuples in the JStar data
  storages and the latency of triggering the tuple rules.
  \item Extended the JStar runtime to allow users to specify the debugging verbosity to report different kinds of
  runtime information about the execution of JStar programs.
  \item Added \keyword{tuple grouping} feature to the JStar runtime so that Delta
  nodes with many tuples can group multiple tuples into a single fork/join task, to reduce the overhead of having many
  small tasks.
  \item Extended the JStar runtime to allow users to choose between alternative Gamma table and Delta tree data
  structures at runtime. This makes it easy to measure the performance of alternative data structures.
  \item Evaluated the performance of different Gamma data structures.
  \item Developed a \keyword{Task Dependency Graph Tool} for visualising the dependencies between rules and tables in an
  execution of a JStar program.
  \item Added logging features to the JStar runtime, and wrote the \keyword{JStar Tuple Timing Graph} that visualises
  the log output as a timeline of tuple executions. This is helpful for identifying bottlenecks and performance
  problems within some JStar programs.
  \item Defined the standard operating procedure (S.O.P) to benchmark the JStar programs on the Symphony cluster or the
  NeSI cluster.
  \item Defined a performance tuning process for JStar programmers to follow.
  \item Applied that tuning process to several case studies (with different styles of parallelism) and demonstrated that
  it produces efficient programs, usually with quite good speedup.
  \item Used the Disruptor data structures to speed up one JStar program without changing the JStar source code.
\end{enumerate}
\cleardoublepage
