-
Notifications
You must be signed in to change notification settings - Fork 0
/
01-introduction.tex
62 lines (32 loc) · 6.67 KB
/
01-introduction.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
%% We use `subfiles' package
\documentclass[preamble.tex]{subfiles}
\begin{document}
\clearpage
\chapter{Introduction}
\label{ch:introduction}
The past decade has seen a rise in development of increasingly sophisticated multi-core and multi-processor computer systems. From the early hyperthreaded solutions to the modern architectures comprising a number of independent processing cores, the horsepower for demanding applications is now available even in the most affordable consumer grade systems. To offer a large amount of parallelism, the high grade systems may have multiple multi-core processors, where each core can run a number of hardware scheduled threads.
While the hardware for running highly parallel computations is readily available and is improving at a high pace, the development of applications that make use of this capability is often a challenging task. The problems involved are finding an appropriate parallel implementation of the task at hand, implementing it so that the computations are evenly distributed across processing elements and synchronising parallel computations when necessary. The latter two require a substantial programmer's intervention to get the algorithm running fast.
% It is not uncommon for the initial parallel implementation to run only slightly faster than the sequential version.
The resulting application is a mixture of the actual algorithm and the implementation specific code, dealing with concurrency and parallelism. This obscures code clarity and may generally be error-prone.
One alternative to this practice of explicit parallelisation is to provide a common set of collective operations\icollop on large data structures. Programs implemented in terms of these operations would be automatically parallelised across available processing elements. This approach is successfully exercised by a multitude of frameworks covering many host languages, target architectures and suitable application domains \cite{PLKC08,KCL+10,CKL+11,AS07}.
However, in the pursuit of a high level approach to programming a major inefficiency is introduced. Having provided a number of collective operations, the problem of multiple traversals arises. In each program there is likely to be a number of such operations composed together in some way to compute the desired result. With each collective operation potentially traversing a large data structure, the memory traffic is considerably increased.
In a program written by hand without the use of collective operations the programmer would naturally recognise all the operation that could be performed in one pass over the data structure. The program would only traverse the data structure as few times as required, keeping the memory traffic to the necessary minimum and utilising cache correctly.
On the other hand, using a straight-forward implementation of a high level library of collective operations would result in code that traverses data many times while potentially performing only a small change in each pass. For large data structures this may lead to poor cache utilisation and high memory traffic, noticeably reducing the overall performance.
Additionally, each operation may need to store its result in a new data structure, which is especially true for languages where values are immutable by default. Allocating temporary data structures to store the intermediate results\idx{intermediate value} leads to further memory and runtime penalties.
Optimising out the superfluous data structure traversals and allocations is collectively referred to as \term{Loop Fusion}.\ifusion It allows a program expressed in terms of high level operations, also called \term{combinators},\icomb to be transformed into a program that would be comparable to a handwritten one in operation and speed.
In this thesis I explore the problem of loop fusion in the context of purely functional data parallel programs. In particular I explore the challenges of fusing programs written for the \*nested data parallel* frameworks such as \name{Data Parallel Haskell (DPH)}.
In the following I summarise the areas of my contribution, explicitly noting which are my individual work:
\begin{itemize}
\item We propose a novel system, \LiveFusion, for fusing collective array operations at the run-time of the program in a purely functional setting (Chapter~\ref{ch:frontend}).
\item I implement the proposed system as a embedded domain-specific language for the \Haskell programming language which includes automatic recovery of shared terms (Section~\ref{sec:sharing-recovery}), explicit tupling of results and a scalar language (Section~\ref{sec:Scalar-language}).
\item I devise a generic representation of loops as a more structured and composable alternative to @while@ and @for@ loops found in procedural languages. I implement the new looping construct as an intermediate language, \Loop, inside \LiveFusion (Chapter~\ref{ch:Loops}).
\item I present the mapping of \term{flat} (Sections \ref{sec:loop-generation}, \ref{sec:Loops-flat-combinators}) and \term{segmented} (Section~\ref{sec:Loops-segmented-combinators})\footnote{The term \term{segmented} describes combinators that operate on nested arrays. It owes its name to the way such arrays are represented and is discussed in Section~\ref{sec:Flattening}. \term{Flat} combinators operate on regular arrays.} array combinators onto the generic loop representation designed to enable fusion in the \name{Data Parallel Haskell} framework (Chapter~\ref{ch:NDP}).
\item I implement a dynamic code generator which translates fused loops expressed in the intermediate \Loop language into \Haskell source code. I also implement dynamic code compilation and loading facilities enabling highly efficient execution of the generated code (Chapter~\ref{ch:Code-Generation}).
\item I present performance benchmarks evaluating \LiveFusion against the types of programs resulting from the use of \*nested data parallel* frameworks such as \name{Data Parallel Haskell} (Chapter~\ref{ch:Results}).
% \item I develop a suite of invariants in the form of \name{QuickCheck} \*properties* for automatic testing of individual combinators.
\end{itemize}
The source code for \LiveFusion is available at \url{https://github.com/roldugin/LiveFusion}. The source code for \name{Data Parallel Haskell} is available at \url{https://github.com/ghc/packages-dph}.
I shall begin by introducing the reader to the problem of fusion and the context of my work. In the next chapter I will outline the challenges of array fusion finding a solution to which has motivated my work in the prior years.
% The work described in this thesis is aimed at introducing a new fusion mechanism in \name{Data Parallel Haskell (DPH)}\idph framework.
\IfNotCompilingAll{\printbibliography}
\end{document}