thesis.tex

\documentclass[phd,icsa,twoside,logo,11pt]{infthesis}

\usepackage{appendix}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[numbers]{natbib}
\usepackage[hidelinks]{hyperref}
\usepackage{cleveref}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{caption}
\usepackage[table]{xcolor}
\usepackage{calligra}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{tcolorbox}
\tcbuselibrary{theorems}
\usepackage{mathptmx}
\usepackage{enumitem}
\usepackage{pgfplots}
\usepackage{courier}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{lscape}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\renewcommand*{\thefootnote}{*}

\DeclareCaptionFormat{listing}{\linespread{1}\selectfont{}\parfillskip=0pt{#1#2#3}}
\captionsetup[lstlisting]{format=listing,labelfont=bf}
\captionsetup[figure]{format=listing,labelfont=bf}
\captionsetup[table]{format=listing,labelfont=bf}

\usetikzlibrary{patterns}
\pgfplotsset{compat=1.13}

\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}

\hyphenpenalty=100000
\apptocmd{\sloppy}{\hbadness 2591\relax}{}{}

\Crefname{lstlisting}{Listing}{Listings}

\newtcbtheorem[auto counter,number within=chapter]{theorem}{Theorem}{
 label type=theorem,
 colback=white,
 colframe=black,
 fonttitle=\bfseries,
 title={Theorem \thetcbcounter}
}{theo}

\newtcbtheorem[auto counter,number within=chapter]{definition}{Definition}{
 label type=definition,
 colback=white,
 colframe=black,
 fonttitle=\bfseries,
 title={Definition \thetcbcounter}
}{def}

\newtcolorbox{blackbox}[1]{
 top=0mm,
 bottom=0mm,
 left=0mm,
 right=0mm,
 boxsep=0mm,
 toptitle=1mm,
 bottomtitle=1mm,
 colback=black,
 colframe=black,
 fonttitle=\centering\bfseries,
 title=#1
}

\newtcolorbox{blackwhitebox}[1]{
 colback=white,
 colframe=black,
 fonttitle=\centering\bfseries,
 title=#1
}

\newtcolorbox{graybox}[0]{
 top=0mm,
 bottom=0mm,
 left=0mm,
 right=0mm,
 colback=white!90!black,
 colbacktitle=white!90!black,
 colframe=white!50!black,
 lower separated=false
}

\definecolor{color_strings}{HTML}{0F4D0F}
\definecolor{color_keywords}{HTML}{191980}
\definecolor{color_types}{HTML}{801919}
\definecolor{color_comment}{HTML}{FF0000}

\lstset{
 basicstyle       = \linespread{1}\ttfamily,
 stringstyle      = \color{color_strings}\bfseries,
 keywordstyle     = \color{color_keywords}\bfseries,
 keywordstyle     = [2]\color{color_types}\bfseries,
 keywordstyle     = [3]\bfseries,
 commentstyle     = \color{color_comment}\itshape,
 numberstyle      = \scriptsize,
 numbersep        = 10pt,
 frame            = lines,
 numbers          = left,
 xleftmargin      = 1.5em,
 framexleftmargin = 1.5em,
 captionpos       = b,
 escapeinside     = {([}{])},
 literate         = {∧}{$\land$}1{∨}{$\lor$}1{∈}{$\in$}1{≠}{$\neq$}1{Φ}{$\Phi$}1
                    {@}{@}1
}

\lstdefinelanguage{MyCpp}{
 morekeywords = {return, class, struct, public, private, goto, for, if, else,
                 virtual, override, while, template, auto, using, namespace},
 morekeywords = [2]{const, int, double, float, bool, size\_t, unsigned, void,
                    vector, array, shared\_ptr, pair, map, string, dyn\_cast,
                    Instruction, CallInst, Value, Function,
                    SkipResult, BacktrackingPart, Tree, ElementOfShared,
                    ElementOfPart, ConjunctionPart, AddInstruction,
                    FirstArgument, SecondArgument, Conjunction},
 morekeywords = [3]{true, false, FAIL, PASS, CHANGE, SUCCESS},
 morecomment  = [l]{//},
 morecomment  = [s]{/*}{*/},
 morestring   = [b]{"}
}

\lstdefinelanguage{BNF}{
 morecomment  = [s][\color{color_strings}\bfseries]{<}{>}
}

\lstdefinelanguage{CAnDL}{
 morekeywords = { with, collect, for, foreach, forany,
                  if, then, else, endif, not, otherwise, specified},
 morekeywords = [2]{Constraint, End, include},
 morekeywords = [3]{SqrtOfSquare, ValueChain, Sum, SumOfSums, CollectArguments,
                    FloatingPointInstruction, SESE, Loop, LocalConst,
                    PointerAccess, ArrayAccess, LoopWithOnlyArrayAccesses,
                    SimpleAddition, ComplexFactorisation,
                    FloatingPointAssociativeReorder, VectorMulChain,
                    ScalarHoist, SCoP, For, StructuredControlFlow,
                    AffineControlFlow, AffineMemAccesses,
                    SideEffectFreeCalls, ScopeValue, IfBlock, MemoryAccess,
                    AffineCalc, PotentialSESE, ArgumentsPermuted,},
 morecomment  = [s][\color{color_strings}\bfseries]{\{}{\}}
}

\lstdefinelanguage{IDL}{
 morekeywords = { with, collect, for, all, some, and, or, at, as,
                  if, then, else, endif, not, otherwise, specified},
 morekeywords = [2]{Constraint, End, inherits},
 morekeywords = [3]{KernelFunction, LocalConst, ScalarPart, ScopeValue, Concat,
                    HistoPart, ConditionalReadModifyWrite,
                    ComplexReductionsAndHistograms, For, VectorRead,
                    SideEffectFreeCalls, ArgumentsPermuted, MaxOnceInScope,
                    Loop, SESE, Reduction, Stencil, ForNest, StencilRead,
                    PermMultidStore, SPMV, SPMV_CSR, SPMV_JDS, GEMM,
                    VectorStore, VectorRead, DotProductLoop, DotProductFor,
                    MatrixStore, MatrixRead, Histogram,
                    ForLoop, OffsetAdd, InductionVar, RangeCheck,
                    FactorizationOpportunity, ReadForLoopRanges,
                    Addition, ReadForLoopIterations,
                    DotProductForAlphaBeta},
 morecomment  = [s][\color{color_strings}\bfseries]{\{}{\}}
}

\lstdefinelanguage{LIFT}{
 morekeywords = {return, gemm\_in\_lift, map, fun, reduce, zip, transpose},
 morekeywords = [2]{float}
}

\title{From Constraint Programming\\to Heterogeneous Parallelism}
\author{Philip Ginsbach}

\newenvironment{laysummary}
   {\renewcommand{\abstractname}{Lay Summary}\begin{mainabs}}
   {\end{mainabs}\renewcommand{\abstractname}{}{}}


\begin{document}
\abstract{\input{latex/abstract}}
\begin{preliminary}
\maketitle
\begin{abstract}

\end{abstract}
\begin{laysummary}
\input{latex/laysummary}
\end{laysummary}
\begin{acknowledgements}
    First of all, I want to thank my adviser, Michael O'Boyle, for his guidance
    and sound advice throughout my PhD studies.
    I would also like to thank my other advisers at the university,
    Björn Franke and Adam Lopez, and my mentors at ARM,
    Chris Ryder and Pablo Barrio, whom I could rely on for additional insights
    and suggestions.

    My time as a PhD student would not have been half as enjoyable without the
    PPar cohort.
    Amna, Caoimhín, Dan, Daniel, Floyd, Jakub, Paul, Rajkarn, Reese, Vanya,
    Victor, you made Edinburgh a great place to be for the last few years!
    Paul, Vanya, Reese, Dan, I will miss our lunches in particular.
    Caoimhín and Braedy, thank you for helping me polish this thesis.
    Thank you also to Reese, Lewis, and Vanya for some additional proofreading.

    Finally, I am grateful to my parents, who have always supported and
    encouraged me.

\end{acknowledgements}
\begin{declaration}

    \includegraphics[width=\columnwidth]{SignedDeclaration.pdf}

\textcolor{white}{
\citet{Ginsbach:2018:CDS:3178372.3179515}
\citet{ginsbach2017discovery}
\citet{Ginsbach:2018:AML:3173162.3173182}}

\end{declaration}
\tableofcontents
\end{preliminary}

\chapter*{List of Symbols and Notation}
\addcontentsline{toc}{chapter}{List of Symbols and Notation}  
    \input{latex/notation}

\chapter{Introduction}
    \label{chapter:introduction}
    \input{latex/chapter1}

\chapter{Constraint Programming on Static Single Assignment Code}
    \label{chapter:theory}
    \input{latex/chapter2}

\chapter{Related Work}
    \label{chapter:literature}
    \input{latex/chapter3}

\chapter[The Compiler Analysis Description Language]
        {The Compiler Analysis Description Language\footnote{This
         chapter is based on published research:
         \citet{Ginsbach:2018:CDS:3178372.3179515}.}}
    \label{chapter:candl}
    \input{latex/chapter4}

\chapter[Automatic Parallelisation of Reductions and Histograms]
        {Automatic Parallelisation of Reductions and Histograms\footnote{This
         chapter is based on published research:
         \citet{ginsbach2017discovery}.}}
    \label{chapter:reductions}
    \input{latex/chapter5}

\chapter[Heterogeneous Acceleration via Computational Idioms]
        {Heterogeneous Acceleration via Computational Idioms\footnote{This
         chapter is based on published research:
         \citet{Ginsbach:2018:AML:3173162.3173182}.}}
    \label{chapter:idioms}
    \input{latex/chapter6}

\chapter{Conclusions}
    \label{chapter:conclusion}
    \input{latex/chapter7}

\bibliographystyle{unsrtnat}
\bibliography{references}

\begin{appendices}
\chapter{Full Grammar of CAnDL}
    \label{appendix:CAnDLgrammar}
    \input{latex/appendixA}
\chapter{Polyhedral Code Sections in CAnDL}
    \label{appendix:CAnDLpoly}
    \input{latex/appendixB}
\chapter{Full Grammar of IDL}
    \label{appendix:IDLgrammar}
    \input{latex/appendixC}
\chapter{Complex Reductions and Histograms in IDL}
    \label{appendix:IDLreductions}
    \input{latex/appendixD}
\end{appendices}

\end{document}