\chapter{Related Work}\label{ch:related}
The parallel computing divides a great deal of computation into many tasks which can be carried out in parallel.
Having many computers to work on the same problem can shorten the completion time and achieve the same or better
performance than using a single unit computer. To provide a large number of the computing resources, the High
Performance Computing (HPC) facility are either the multi-core machines or clusters of small machines that are linked
together through the local network or interconnect to work together. And currently the clusters of multi-core machines
are preferable because their prices are more affordable and have more computational power than the single-unit machines
\cite{Taboada2011}.
\par The HPC parallel programming model employs the \textbf{distributed} or \textbf{shared} memory design to parallelize
the computation across the multiple processors. The distributed memory programming model distributes the tasks and data
over the multi-core machine, where each processor owns one private memory space to store the data locally.
If the processor requires the non-local data, it must communicate with other processors and move the
remote data to its local memory. Referencing the remote data takes some extra time to find the data location and thus
could lead to an unexpected delay. Instead of data distribution, the shared memory programming model keeps all the data
with one public memory space where the processors can retrieve data from.
\par The distributed memory offers the memory locality to allow each processor to store the data in the closest (private)
memory location. As each processor mostly uses the local data, the distributed memory model can avoid the race
conditions but produce inevitable communication costs. Message Passing Interface (MPI) is the communication library
for the distributed memory model. The MPI can be called directly from \texttt{C} and \texttt{Fortran}, or packaged as a
library and imported into a \texttt{Java} project. The MPI program is efficient and portable as the MPI interface has
been widely adapted in every distributed memory systems and also optimized to provide the good performance.
\par The shared memory system uses one single memory space to store the data and provides the unified global memory
addresses to quickly locate and retrieve the data. As the same data are occasionally synchronized by more than one
processors, the shared memory program may have the performance problems, such as the race conditions. 
\section{Library-based Shared Memory Programming Languages}
Java language is considered as a option for programming on parallel hardware. With built-in multi-threading and
networking APIs, Java programmers can write a parallel application to utilize the computing power of the multi-core
machines in a cluster. But writing a low-level multi-threading application is hard and buggy as the data synchronization
requires the external mechanism and the incorrect design of parallel tasks may lead to deadlock. Therefore, Java from
1.5 specification supports the high-level shared memory programming with several concurrency utilities, including the
thread pools, the concurrent collections and the atomic variables.\cite{Taboada2011}
\par Using Java for HPC may have some difficulties. Although the performance of JVM has been continuously improved by
experts and engineers, the performance of Java HPC solutions may still be reduced by some unpredictable factors. For
example, the excessive objects allocation increases the overhead costs for the Java garbage collector and thus results
in a longer execution time. The poor cache performance from many object references may also increase the running time.
\par Despite the above issues, Java is still an important parallel programming language for some HPC application.
The reasons are that:
\begin{inparaenum}[\itshape a\upshape)]
\item there has been a number of projects developed in Java for HPC;
\item Java programs can support both of sequential and parallel implementations and achieve a good performance;
\item the recent development on Java, e.g. the low-latency communication, has overcome some performance issues.
\end{inparaenum}\cite{Taboada2011}
\par As OpenMP standard supports the multi-platform shared memory programming (in \keyword{C}, \keyword{C++} and
\keyword{Fortran}), it provides the portability to the multi-threading code across the heterogeneous hardware and
operating systems. But the OpenMP standard is not included in Java, and therefore, most Java OpenMP-like projects
are implemented in the form of a Java library to be imported in the Java project. JOMP, for example, is a library
for Java to achieve the OpenMP-like parallelism.\cite{website:JOMP}
\section{Partitioned Global Address Space Languages}
\subsection{Titanium and X10}
\keyword{Titanium} uses Java as its base and adds extra features for high performance parallel programming.\cite{Taboada2011}
Titanium adopts Partitioned Global Address Space (PGAS) programming model: all processes use one single memory space and
reference objects with global addresses. Each process allocates one region of this spaces and stores all its data objects
in its local region. Through sharing the same memory, a process can read and write the data objects that reside on
others. Moreover, Titanium adopts lightweight synchronization to ensure that single-value variables are only read and
written by one process, and have consistent values in all processes. Benchmark results show that Titanium implementations
can have or often have the better performance than the standard Fortran/MPI ones.\cite{Datta:2005:TPP:2081896.2081910}
\par \keyword{X10} is also another Java-based shared memory programming language. It uses APGAS (Asynchronous Partitioned
Global Address Space) as its execution model for distributed processing.\cite{Kawachiya:2012:DGC:2246056.2246061} The
global memory space is split into several \emph{places}, each place is implemented by one instance of JVM.
By having multiple JVMs running on different computers and connecting them through the network, X10 forms the
distributed system. Thus, a large computation work can be divided into many tasks, each of which can be distributed and
processed concurrently.
\par Regarding memory referencing, each JVM creates and stores its local data objects in a specific location of the
memory space. Thus, each object has a global address and be remotely referenced from other places, using a mechanism
named \emph{GlobalRef}. That is, all referenced objects can not be collected as garbage even if there is no local
reference to it.\cite{Kawachiya:2012:DGC:2246056.2246061}
\par Both Titanium and X10 use the syntax of JAVA language, so they inherit its imperative program paradigm: using
statements to define the computation and assign values to variables. But JStar is a declarative language which
expresses the program's computation without assignments. Regarding parallelism, Titanium and X10 programmers
need to explicitly specify where the parallelism should go whereas JStar parallelism is implicitly determined by the
JStar compiler. Like the PGAS programming model, JStar uses a global DeltaNode and Gamma database to store all local
data objects in one memory space. While it is possible to transparently distributed the JStar database across multiple
computers.\cite{SimonCrosby} This thesis will focus on the shared memory implementations.
\subsection{Chapel}
\keyword{Chapel} is an emerging parallel programming language that originated under the DARPA High Productivity
Computing Systems (HPCS) program.\cite{Chapel:Jan2013} Chapel also supports the PGAS memory model, which all the
variables are regarded as the local ones although some of them are stored in the global memory space. And the Chapel
runtime and compiler will implement the network communication for these remote variables. Chapel also supports the
programmers to introduce the explicit parallelism on the single-core machine or execute the code sequentially on the
multithreaded machine.
\par The difference between JStar and Chapel is the way of how the users specify the task parallelism. Chapel allows the
programmers to specify the task parallelism explicitly with the \keyword{sync} statements, the atomic variables and
structured parallelism.\cite{Chapel:Jan2013} But the JStar language use an implicit style of programming to implement
its parallel tasks. Regarding the data parallelism, as the explicit parallel programs would cause the race conditions
or deadlock, Chapel and JStar both uses similar and implicit features, such as \keyword{forall} loop, and reducers.
\section{Intel Concurrent Collections}
Intel Concurrent collections (CnC) aims to provide users with high level parallelism, so that users are able to write
their algorithms without detailed parallelism knowledge.\cite{IntelCnC} Writing an efficient parallel program is
difficult. Parallel programs may introduce new kinds of bugs which have never been found in sequential programming. One
of the potential bugs is race conditions. Another bug is when one thread is not able to lock the state of a shared
resource, it may infinitely block others from accessing the resources and lead to the deadlock. Besides, an inefficient
parallel program may have performed once worse than the sequential one. As many parallel programs usually divide one
task into a number of subtasks, they need to use a barrier to force all threads to wait for each other until all
results have been synchronized. But this barrier results in higher synchronizing time as finished processes have to
wait for unfinished ones. Sometimes the synchronization overhead costs may dominate the benefits of parallel
programming and cause longer execution time.
\par The concept of CnC is to make parallel programming accessible to domain experts and tuning experts.\cite{IntelCnC}
Because the CnC model hides the details of parallelism, domain experts do not need to write low-level parallel programs,
but only need to identify the dependencies which need to be run in parallel. The CnC program model specifies these
relationship in a \texttt{CnC specification graph} which defines these relationship graphically and statically.
\par Tuning experts can be involved in the team for improving the performance of CnC programs. By mapping the CNC graph
on a target parallel architecture, tuning experts can improve the performance of CnC program without needing to
understand the application. And since the deterministic semantics---the same inputs producing the same outputs---
is adopted by CnC, the correctness of the optimized CnC programs can also be ensured.
\par JStar and CnC have some similarities. They both use the determinism program model to ensure the correctness of the
program. They also provide the dependency graph to visualize their programs, but the JStar graph is dynamic. They
separate the roles of domain experts and parallelism experts. This allows the development team to include the people of
different profession to work together but still can make use of their expertises. For example, the application
developers can focus on the business logics without thinking about the implementations while the programmers can
merely concentrate on the coding and debugging.
\section{Domain-Specific Languages}
Heterogeneous computing hardware is becoming an important trend in the computer industry and can provide significant
performance increase. But in order to interact with these heterogeneous devices, application developers have to learn
a variety of programming models. These incompatible models make the applications more complicated to deploy on
different platforms and hard to maintain their source code. Therefore, a parallel heterogeneous programming model is
needed to help programmers to deal with different computing devices across systems.
\subsection{DSL Characteristics}
The Delite framework developed by Stanford University's Pervasive Parallelism Laboratory (PPL) supports this goal and
proposes the following characteristics for a parallel domain specific language:\cite{5963629}
\begin{description}
\item[Productivity.]
The application programmer can easily write the programs without the use of explicit parallel constructs. DSLs
(Domain-Specific Languages) are used to satisfy these goals. Each DSL is a programming language with high-level
abstractions. For example, LaTeX is the DSL for academic papers and SQL is for database querying. Because each DSL is
designed for a particular domain, application writers are familiar with its notation and constructs. In addition, it can
provide a sequential-like programming model for writing parallel code and using heterogeneous computing resources. So
the productivity of application writers can be improved.
\item[Performance.]
Application writers often take a lot of effort to write low-level code for better performance. But the new
programming model should not decrease their performance. The DSL approach can achieve both productivity
and performance because its compiler can trade off the generality to generate the high performance code. General-purpose
compilers have to impose some restrictions on programmers to guarantee the correctness of generated code. This
sometimes leads to low performance code. But the DSL uses implicit parallelism in a limited domain to prevent
programmers from writing inefficient programs; therefore, the DSL compiler can use aggressive implementation of
parallel patterns to optimize the code without causing any safety issues.
\item[Portability and Scalability.]
The application should be able to run on various computing resources across different systems. 
\end{description}
\subsection{The Delite Framework}
The Delite is implemented to run the same DSL programs on heterogeneous systems without changing the source code.
The workflow chart is described in the following steps:
\begin{enumerate}
\item The application developers write their programs in a DSL and submit to the Delite framework.
\item The Delite compiler starts to build IRs of all operations. IR is defined by Lightweight Modular Stage (LMS),
the framework designed for DSL embedded in Scala.
\item When the DSL programs are compiled, the LMS translate each operation into an IR node and forms symbolic
representations of the original DSL programs.
\item The Delite compiler then applies static optimizations to achieve high performance on the IR nodes. For example,
the Common Subexpression elimination (CSE) could remove redundant operations by reusing existing ones. And the linear
algebra simplification, a domain specific optimization, is also applied in this process.
\item After optimizing the IR trees, the Delite compiler generates the kernel code for any available target hardware
and forms all IR nodes into a Delite execution graph (DEG). The Delite framework also generates kernels for different
types of hardware while building the DEG.
\end{enumerate}
\par The Delite runtime uses the machine specifications (the number of CPUs and GPUs), DEG and DSL data structure to
schedule the execution of this application. The scheduling algorithm is designed to enable implicit parallelization;
therefore, a deferred execution model is proposed. The Delite runtime delays ops being received so that more "run-ahead"
ops are allowed to be submitted. Then these ops are formed into a dynamic task graph and dispatched to a thread pool by
a heuristic, which minimizes the costs of data communication and scheduling overhead.
\par The Delite runtime provides the data-parallel operations and classes, which can be extended. For example, the
OptiML is a DSL aimed at Machine learning and provides various domain-specific control structures, such as a sum
construct.
This function sums up the result of a block for each iteration and is implemented by extending the
\class{DeliteOpMapReduce} parallel pattern. Moreover, the Delite runtime assists in generating the GPU code if DSL authors use
the \texttt{@GPU} annotation to specify the operations that they want to ship to graphics processing units (GPU) on a
single machine.
\par In order to minimize the overhead of execution on heterogeneous hardware, the Delite runtime generates execution plans
for available computing resources and compiles them with the respective kernels to create executable files. The data
transfers can be minimized because DEG provides detailed dependency information. On the other hand, memory allocation is
well managed by the Delite runtime. For a CPU kernel, the Delite runtime uses the Java Virtual Machine to manage the
memory. For GPUs, the runtime pre-allocates all data structures to address the GPU memory allocation issue.
% Related to JStar.
\par The Delite framework shares similar goals with JStar. They use a runtime environment to compile and execute parallel
programs on different platforms. And they both provide a graphic representation tool to optimize the compiled programs.
Delite framework generates a DEG to optimize the execution operations on the heterogeneous parallel hardware and JStar can
assist parallel experts to tune the performance with a task dependency graph. Delite and JStar\cite{SimonCrosby} both
support the GPU compilation features to generate code running on GPUs. However, they have different purposes:
JStar is a general-purpose language based on Datalog with negation whereas Delite is a machine-learning domain-specific
programming language. JStar uses a declarative programming style and immutable data objects to guarantee the
thread-safety of any JStar operation but the Delite uses a mutable programming model, plus reducers to concurrently
sum up the values in an array.
\cleardoublepage