thesis.tex

\documentclass[a4paper,twoside,openright]{report}

\title{Automatic Parallelisation for Mercury}
\author{Paul Bone}

% According to gradresearch.unimelb.edu.au:
%
% The dissertation should be roughly 80,000 words and strictly fewer than
% 100,000 words.
%
% Printed on a4 paper.
%
% 1.5 spaced.
%
% Margins no smaller than 30mm.
%
% Page numbers must be consecutive and printed within the margin.
%
% MSGR are flexible WRT citation style, They defer to the department on this
% (as different disciplines have different rules).  I am waiting for Chris
% Leckie to reply to me about this.

% WARNING: citesort, hyperref and algorithm do not play nice together.
% This can be fixed by using natbib (which is apparently better) instead of
% citesort.
% And by using hyperref before algorithm.

\usepackage{hyperref}

% Restart numbering in each chapter.
\usepackage[chapter]{algorithm}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage[margin=3cm]{geometry}
\usepackage[sort&compress,numbers]{natbib}
\usepackage{pstricks}
\usepackage{setspace}
\usepackage{breakurl}
\usepackage{xspace}
\usepackage{graphicx}
\usepackage{subfigure}  % Subfigure references and captions
\usepackage{multirow}   % multiple rows cells in tables
\usepackage{dcolumn}    % decimal centered columns in tables.
\usepackage{multicol}   % multiple columns for small sections of text
\usepackage{float}      % Custom floats.
\usepackage{rotating}   % Sideways tables.
\usepackage{bold-extra} % Bold and small caps.
%\usepackage{varwidth}  % parbox with variable width.
\usepackage{mathtools}
%\DeclarePairedDelimiter{\ceil}{\left\lceil}{\right\rceil}
%\DeclarePairedDelimiter{\floor}{\left\lfloor}{\right\rfloor}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\usepackage[all]{nowidow}

% If you do not have this package, install texlive-math-extra, I did not want
% to include it in this directory since it brings fonts with it, (and they are
% needed)
\usepackage{stmaryrd}

\usepackage{fancyhdr}
%\setlength{\headheight}{15.2pt}
\pagestyle{fancy}
\fancyhead{}
\fancyhead[CE]{\slshape \leftmark}
\fancyhead[CO]{\slshape \rightmark}
\fancyhead[LE,RO]{\thepage}
\fancyfoot{}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.0pt}

\onehalfspacing

\input{macros}

\begin{document}

% These only work after \begin{document}
\input{alg_macros}

\begin{titlepage}
\begin{center}
\vspace*{3cm}
{\Huge \textbf{Automatic Parallelisation for}} \par
\vspace*{1em}
{\Huge \textbf{Mercury}} \par
\vspace*{2cm}
{\huge \textbf{Paul Bone}} \par
\vspace*{4cm}
{\Large Submitted in total fulfilment of the requirements of the degree of
        Doctor of Philosophy} \par
\vspace*{1cm}
% XXX: Revise this date.
{\Large December 2012} \par
\vspace*{1cm}
{\Large Department of Computing and Information Systems} \par
{\Large The University of Melbourne} \par
\end{center}

%\paul{Copyright (C) 2009-2012 Paul Bone}\\
%\paul{Draft \today, not for redistribution.}
\end{titlepage}

\thispagestyle{empty}

\chapter*{Abstract}

% XXX
\pagenumbering{roman}
\setcounter{page}{1}

\plan{300-500 words}

% Seperate file so that measuring the word count is easy.
\input{abstract}

\chapter*{Declaration}

% This is the prose that gradresearch.unimelb.edu.au said I should use.

This is to certify that:

\begin{itemize}

    \item the thesis comprises only my original work towards the PhD except
          where indicated in the Preface,

    \item due acknowledgement has been made in the text to all other material
          used,

    \item the thesis is fewer than 100,000 words in length, exclusive of
          tables, maps, bibliographies and appendices.

\end{itemize}

\vspace{1em}

\noindent Signed:

\vspace{1em}

\noindent Date:

\chapter*{Preface}

The dissertation begins with an introduction
(Chapter~\ref{chap:intro}) that
motivates the need for automatic parallelism systems.
It provides an analysis of the related literature;
using this to show why automatic parallelism is important
and why the problem is still unsolved.

Chapter~\ref{chap:backgnd} provides background material used throughout the
rest of the dissertation.
In particular it describes prior work 
that I did as part of my Honours project
for the degree of Bachelor of Computer Science Honours at the University of Melbourne.
This work occurred before my Ph.D.\ candidature commenced.
This work included:
the profiler feedback framework (Section~\ref{sec:backgnd_autopar}),
an initial rudimentary version of the automatic
parallelisation tool (also Section~\ref{sec:backgnd_autopar}),
an algorithm for determining when a sub-computation first uses
a variable (Section~\ref{sec:backgnd_var_use_analysis}),
and the initial version of the coverage profiling support in Mercury's deep
profiler (Section~\ref{sec:backgnd_coverage}).

Chapter~\ref{chap:rts} discusses a number of improvements that were made to
the runtime system, in order to make parallel Mercury programs perform
better.
Chapter~\ref{chap:rts} describes some joint work with Peter Wang.
Wang contributed about 80\% of the initial work stealing implementation 
described in Section~\ref{sec:rts_work_stealing};
I contributed the other 20\%.
An improved version of work stealing is described in
Section~\ref{sec:rts_work_stealing2},
but the work in that section is solely my own.

The next three chapters are based on published papers,
of which I am the first author and contributed the vast majority of the work.
Chapter~\ref{chap:overlap} describes our new automatic parallelism
analysis tool and its novel algorithms.
It is based on the following journal article.

\begin{quote}
\pubauthor{Paul Bone, Zoltan Somogyi and Peter Schachte.}
\pubtitle{Estimating the overlap between dependent computations for automatic
parallelization.}
\pubhow{Theory and Practice of Logic Programming,}{11(4--5):575--591, 2011.}
\end{quote}

Chapter~\ref{chap:loop_control} describes a code transformation that fixes 
a long standing performance problem in the parallel execution of most
recursive code.
It is based on the following conference paper.

\begin{quote}
\pubauthor{Paul Bone, Zoltan Somogyi and Peter Schachte.}
\pubtitle{Controlling Loops in Parallel Mercury Code.}
\pubhow{Proceedings of the 7th Workshop on Declarative Aspects and
Applications of Multicore Programming,}{Philadelphia PA USA, January 2012.}
\end{quote}

Chapter~\ref{chap:tscope} describes our use of the \tscope visual
profiler that was developed for use with Haskell and how we use it with
Mercury.
It is based on the following workshop paper.

\begin{quote}
\pubauthor{Paul Bone and Zoltan Somogyi.}
\pubtitle{Profiling parallel Mercury programs with \tscope.}
\pubhow{Proceedings of the 21st Workshop on Logic-based methods in
Programming Environments,}
{Lexington KY USA, July 2011.}
\end{quote}

Finally Chapter~\ref{chap:conc} concludes the dissertation, providing a
discussion that unifies the work presented in the four main chapters and
describes potential further work.

\chapter*{Acknowledgements}

First I will thank my supervisors,
Zoltan Somogyi,
Peter Schachte and
Aaron Harwood
for all their support, hard work, and on occasion weekends.
I have learnt a lot from you and enjoyed your company and our interesting
off-topic conversations.
I also want to thank my Mercury, G12 and programming languages colleagues:
Julien Fischer,
Mark Brown,
Ralph Becket, 
Thibaut Feydy,
Matt Guica,
Matt Davis,
Andreas Schutt,
Leslie DeKoninck,
Sebastian Brand,
Leon Mika,
and
Ondrej Bojar;
and Mercury developers outside of the University:
Peter Wang,
Ian MacLarty,
and
Peter Ross.
I also want to thank the helpful and supportive staff in the Computing and
Information Systems department at the University of Melbourne,
especially
Linda Stern,
Bernie Pope,
Harald S{\o}ndergaard, and
Lee Naish.

I would also like to acknowledge the support of the functional and logic
programming research community.
% XXX Acknowledgements.
Firstly, I want to thank everyone
who has contributed to the development of \tscope,
helped organise the \tscope summit, and
answered many of my questions,
in particular
Simon Marlow,
Simon Peyton-Jones,
Eric Kow
and Duncan Coutts.
Simon Marlow and his family were also incredibly hospitable during my visit
to Cambridge.
% I also want to thank those who helped me organise my attendance at the
% \tscope summit:
% Simon Peyton-Jones,
% Eric Kow,
I also want to thank those at the University of New South Wales who invited
me to present a seminar to their research group:
Ben Lippmeier,
Gabi Keller,
and Manuel Chakravarty.

I received financial support from the following scholarships, prizes and
organisations:
Australian Postgraduate Award,
NICTA Top-up Scholarship,
NICTA travel support,
Melbourne Abroad Travelling Scholarship,
%(ICLP \& Cambridge),
Google Travel Prize,
%(ICLP \& Cambridge),
Association for Logic Programming (ICLP),
%Mercury Project (ICLP) \paul{Zoltan, you gave me some money for ICLP, where did it
%come from?},
%NICTA (DAMP),
and
Open Parallel.
%(MW'12).

I would like to offer special thanks to those who contributed time and
effort in other ways.
%Others contributed with proof reading, shell accounts and benchmark
%programs:
Ben Stewart for shell access to his multicore system early in my candidature,
Chris King for his spectralnorm benchmark program,
Michael Richter for assistance with proof reading.
%Gert Meulyzer,
%Stefan Ljungstrand.

I would like to offer a whole lot of thanks to my friends:
Amanda \& Chas Dean,
Lucas \& Jen Wilson-Richter,
Sarah Simmonds, John Spencer,
Jeff Beinvenu, Mangai Murugappan,
Terry Williamson, Heidi Williams,
%Trent Buck for explaining the lambda calculus \emph{at} me,
Tom Wijgers,
Ha Le,
%Chris Menz,
Emil Mikulic,
Dave Grinton,
Marco Maimone,
Michael Slater,
Geoff Giesemann,
Enzo Reyes,
Dylan Leigh,
and Marco Mattiuzzo.

I want to thank my parents, Keith and Faye Bone, for their support and
encouragement,
but most of all,
for teaching me that my poor vision might be an impairment, but should never
be a limitation.
Thanks to my brother, James Bone, for always having time to listen,
even when I use incomprehensible jargon (``nerd-words'').

Finally, Liz Bone, my wife,
for her love patience understanding and caring
and being generally awesome.


\tableofcontents

\listoffigures

\listoftables

\listofalgorithms

\input{intro}
\input{backgnd}
\input{rts}
\input{overlap}
\input{loop_control}
\input{tscope}
\input{conc}

\bibliographystyle{plainnat}
\raggedright
\bibliography{bib}

\end{document}