\documentclass[a4paper,12pt]{article}
\usepackage[
  a4paper,
  margin=2cm,
  bottom=2.5cm
]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{multicol}
\usepackage{setspace}
\usepackage[numbers]{natbib}
\usepackage[usenames]{color}
\usepackage{courier}
\usepackage{listings}
\usepackage{hyperref}
\usepackage[nottoc]{tocbibind}

% New commands
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\icf}[1]{\mbox{\texttt{#1}}} %inline code fragment
\newcommand{\milestone}[0]{\textbf{Milestone:} }

% Formatting
\onehalfspace

% Title, Author
\title{Work Scheduling on Heterogeneous Resources}
\date{\today}
\author{<NAME>\\\small{Supervisor} \and <NAME>}

\begin{document}

\begin{titlepage}

\cleardoublepage
\maketitle
\thispagestyle{empty}

\end{titlepage}

\tableofcontents

\pagebreak

\section{Introduction}
In recent years, two trends in computer hardware design have become apparent.
Firstly, the number of cores per CPU is increasing, while the rate of increase in clock speed is decreasing.
% Contradicts limits of Moore's law, add a citation. Mention silicon limits - why are we violating ML?
Secondly, GPUs are developing into generic computing units, with APIs that expose more of the power of their architecture.
As more computing problems are found to be parallelizable, there is an incentive to try and move work that would have been done on the CPU to the GPU, particularly operations on vectors and streaming data.
At the same time, research suggests that the gap between CPU and GPU processing rates is not as high as one may expect. \citep{lee_debunking_2010, gregg_where_2011}
This gives an incentive to design languages and frameworks to ease the division of work over both the CPU and GPU.

\subsection{Why GPU Programming is Painful}
Two of the most popular frameworks for GPU programming are CUDA and OpenCL, which are both low-level imperative languages. 
In theory, the problem of partitioning work over the CPU and GPU can be solved at the level of these languages. 
In practice, even for GPU-focused tasks such as tree-traversal scans, sorts, or folds, efficient implementations tend to require intimate knowledge of the memory and process architecture of the GPU. \citet{harris_parallel_2007, satish_designing_2008}
This is an added cognitive strain on users of these frameworks, and makes composing GPU tasks difficult: a map followed by a scan is substantially different to just a map, or just a scan.

These languages are also impractical for use as a single source language over multiple types of processors - for instance, while CUDA and OpenCL can target CPU architectures, the resulting binaries are substantially less performant than code originally written with a CPU architecture in mind. \footnote{See \citet{jie_shen_performance_2013} for a discussion focusing on OpenCL.}

The full semantics of the CUDA and OpenCL languages allow for arbitrary write-effects from any kernel to any array, and include operations such as global barriers. 
This makes reasoning about kernels difficult for the same reason that hidden state impedes compositional reasoning in many imperative languages. 
The effect is compounded when kernels are expected to run on separate devices; the result is that these low-level languages make for a poor foundation when trying to attack this problem.

\subsection{Why Scheduling is Painful}
There are several obstacles to effectively partitioning, let alone scheduling, a workload over different work processors. 
The major issues both revolve around memory, namely transfer speed and access patterns. 

\subsubsection*{Memory Transfer Speed} 
Inside of a single GPU, data transfer rates can reach upwards of 300 GB/s. \citep{gtx-780-spec}
However, CPUs and GPUs are typically connected over a PCIe bus.
Modern PCIe busses have a bandwidth cap of around 8GB/s. \citep{pcie-3-faq}
This places strong constraints on how frequently data can be shuttled between components. 

\subsubsection*{Memory Access Patterns} 
Parallelizable computations may have varying degrees of contiguity in their memory accesses. 
When computing a simple \texttt{map} operation, adjacent output locations depend on adjacent input locations, and so we can partition the work by index almost arbitrarily. 
Similarly, a tree-traversal monoidal fold can, at any given depth, be split over processors. 
However, any output index of a backpermute can be affected by the value at any index of the input.

\subsection{Making Things Better}

A large body of work has been produced on generation of parallel code for the GPU and for the CPU, \citep{lee_transparent_2013} however less has been done on the problem of doing so automatically for a general-purpose program. 
Previous work has investigated dynamic scheduling of a task composed of kernels, however the kernels had to have both CPU and GPU versions provided by the user of the library.  \citep{wang_cpu+gpu_2014}
Ideally, we should be able to separate the declaration of our problem from the generation of parallel code to run on whatever hardware happens to be available.
Correctly partitioning and allocating work in the light of the above issues will be a key component of this thesis.

\section{Background}
Phrase the problem as follows: you have some source code in some language, describing a computation you want performed. 
It would be nice if, given this source specification, we could partition and schedule the work on to any processing unit available. 

\subsection{Combinators}
The frameworks described previously are distinguished by being \textit{imperative:} they describe, step by step, the actions performed by the GPU.
Alternatively, we can describe our program using \textit{combinators}, which abstract the combination of computations. 
For example, \icf{map} is a combinator that takes a function \icf{f\ :\  a\ ->\ b}, along with some list \icf{as\ :\ List\ a}, and produces a new list, \icf{map\ f\ as\ :\ List\ b}, which contains the result of applying \icf{f} to every element in \icf{as}. 
We don't particularly care how \icf{map} performs this: we just care that the result is what we expect.

This separation between \textit{what} we want to happen, and \textit{how} we want it to be done, makes combinators quite useful as a source language for computations we want to perform.  
Once the user describes their program, we can interpret the description into whatever implementation we need to in order to satisfy the semantics of the given program.

\subsection{Describing Semantics}
The design of a language framework for a specialised purpose (for instance, automatically parallelised vector programming) results in a Domain Specific Language, or DSL. 
Many DSLs are implemented \textit{inside} another host language, commonly called `embedding'. There are essentially two flavours of Embedded DSLs (EDSLs):

\subsubsection*{Shallow Embeddings} 
Shallow embeddings are almost synonymous with constructing a library. 
Terms in the DSL correspond to library functions that, when evaluated, directly perform whatever computations that they represent.

\subsubsection*{Deep Embeddings} 
Alternatively, we can use the host languages' data definitions to construct a direct representation of the combinators. 
Say we define a new version of \icf{map}, call it \icf{map'}.
Instead of a function, define it as a data constructor: an object containing a function and a list, i.e \texttt{map'\ :\ (a\ ->\ b)\ ->\ List\ a\ ->\ DSL\ b}, where \icf{DSL} is a type representing our DSL embedding. 
The representation data type is typically called the Abstract Syntax Tree, or AST.

This representation has issues: we can't nest it, for instance, since \icf{map'} takes a \icf{List} yet produces a \icf{DSL}. 
However, if we change \icf{map'} to take a \icf{DSL}, we will have completely removed lists from our list operation description language! 
The solution is to introduce a way to `lift' lists into our DSL, which we can do by  including a data constructor \texttt{lift\ :\ List\ a\ ->\ DSL\ a}. 
We can then give \icf{map'} the type \icf{(a\ ->\ b)\ ->\ DSL\ a\ ->\ DSL\ b}.

In order to do anything with these data structures, we need to interpret or evaluate them. 
For instance, we can define a recursive evaluation function \icf{eval}:

\begin{verbatim}
  eval : DSL a -> List a
  eval dsl = dsl match
    lift list         -> list
    map' f anotherDsl -> map f (eval anotherDsl)
\end{verbatim}

Which essentially `replaces' \icf{map'} with \icf{map} and lifted lists with their underlying ones.

\subsubsection*{Benefits of Deep Embeddings}
This may seem like an unnecessary and over-complicated overhead, however it gives us the flexibility to do other things with our description of list computations. 
One of the most important is that once a user has constructed a term in the DSL, we can manipulate it in the host language. 
For array DSLs, many of these manipulations are for optimisation.

As an example, consider the evaluation of \icf{map\ f\ (map\ g\ as)}. 
Semantically, the final result is the application of the composition of \icf{f} and \icf{g} on the elements of \icf{as}. 
However, since \icf{map} is a simple function, the two calls to \icf{map} will produce two intermediate lists. 
On a CPU, this is a relatively small (but not ignorable!) overhead. \citep{rompf_optimizing_2013}
Yet, if we were to naively send off the work to the GPU as two separate mapping steps (presumably over arrays instead of lists), we would suddenly run into memory bottlenecks transferring the data over the PCIe bus.

Compare this with the equivalent deep emedding, \icf{map'\ f\ (map'\ g\ (lift\ as))}. 
Since this is just a nested data structure, we can `pull out' the functions and compose them, producing a new data structure \icf{map'\ (f\ .\ g)\ (lift\ as)}.
When we finally evaluate this new DSL value, it will be converted into a call to \icf{map} that only makes a single list, avoiding memory bottlenecks.
This example is called `map fusion', and is a particular instance of a family of similar `fusion' optimisations designed to reduce the number of intermediate lists (or arrays) involved in a computation.

\subsection{Accelerate}

Accelerate is an EDSL targeting general-purpose GPU programming. 
It is embedded in Haskell, a high-level general purpose functional programming language.
Accelerate models general GPU programming using a deeply-embedded AST, which is then transformed through a variety of intermediate representations and functions over them.
These transformations perform a wide variety of changes aimed at converting the AST from the high-level, user-facing description into a low-level description appropriate for compilation to machine code for the relevant platform.

All levels of the Accelerate framework make heavy use of advanced features of the Haskell compiler.
Most prominently, GADTs and type families are used to encode many properties of the AST, such as the shape of arrays, and levels of parallelism (these advanced type annotations are left out of this report for brevity).
Other features include the use of De Bruijn indices to capture lambda abstraction, and also to facilitate term reuse.
However, despite how interesting all these properties are, they mostly form a backdrop to our main focus, the compilation phases.

The final, machine-code-generating compilation step is intentionally kept separate from the AST transformations, to make changing compilation targets as straightforward as possible.
Recently, a new backend kit has been published for Accelerate, cleanly separating these compiler stages and exposing a simplified kernel-level representation compared to previous versions of Accelerate.

\subsection{Fission}
One of these changes introduced a new pair of combinators to the language, \icf{split} and \icf{concat}.
They have the intuitive semantics that their names imply, of splitting and concatenating arrays.
The combinators are used by the compilation phases to `fragment' arrays and operations on them.
For instance, \icf{map\ f\ arr} may be translated\footnote{This is pseudocode: the details of the Accelerate DSL are omitted for brevity. In particular, in the Accelerate DSL, the \icf{split} and \icf{concat} nodes contain the indices on which they were split, and only have convenient semantics when the two nodes act on the same index. Example drawn from \citet{newton_converting_2014}.} into

\begin{verbatim}
  let (x, y) = split arr in
    concat (map f x) (map f y)
\end{verbatim}

When later stages in the compiler encounter the \icf{concat} node, they may schedule the two arguments to \icf{concat} to run on different processors before combining them.
In the context of work division over processors, this process of splitting arrays is called `data fission'. \citep{newton_converting_2014}

\subsubsection*{Aside: A Frustrating Operation}
There is one family of array operations in the Accelerate DSL that is particularly non-performant for heterogeneous scheduling.
The \icf{permute} and \icf{backpermute} operations use a function from one set of array indices to another in order to permute an array.
As an example, consider the operation \icf{new\ =\ backpermute\ f\ old}.
The function \icf{f} is a mapping from the indices of \icf{new} to the indices of \icf{old}.
This will define \icf{new} such that \icf{new\ !\ i =\ old !\ (f\ i)}.

Since the range of \icf{f} is unrestricted, the value at any index of the output array may depend on the value at any index of the input array.
This complicates the partitioning of work: for instance, say we divide the computation of the output array to two processors.
Although each processor can work in isolation, both need access to the entire input array in order to perform the operation.

In many GPU use-cases, the strongest constraint on throughput is memory transfer speed, which makes copying the entire input array to each processor infeasible.
The result is that these permutations are \textit{de facto} synchronisation points: every operation before them must all have their results returned and combined before the permutation.
This has a potentially interesting interaction with data fission: normally, a map composed with a backpermute would be fused together in some fashion.
We may ask the question: when is it worth fissioning data for the map before recombining for the permutation, and when is the fused operation preferred?

\subsection{Scheduling}
Scheduling strategies can be roughly split into two categories: static and dynamic. \citep{jones_practical_2014}
Like with static and dynamic typing, the categories of scheduling are best described by what we know, and when we know it.
In this case, we're interested in where a given chunk of work is going to be processed - on the CPU, or the GPU, or maybe some remote cluster.

In the static case, we know at compilation time where a particular step of the workload will be performed.
For example, after operator fusion optimisations, the Accelerate backend currently splits arrays into some constant number of fragments.
These fragments are then partitioned and scheduled across processors in part by analysing the dependencies of the various workloads.
However the primary determinant in partitioning is a single number: what fraction of the fragments are sent to the GPU, with the rest being sent to the CPU.

In the dynamic case, the processor on which a given work fragment is performed can only be determined at runtime.
This is usually because the scheduler uses some information that is only available at runtime.
This includes performance metrics for the different processors, and the completion time of earlier fragments.

\section{Previous Work}

\subsection{Heterogeneous Scheduling}

\subsubsection*{Skynet Compiler}
\citet*{grewe_static_????} use machine learning over a feature space of OpenCL source code to determine how to partition work over processors.
The learning-based model is trained on the static code features of OpenCL programs, along with their optimal work partitions.
The trained model is used to categorise subsequent OpenCL programs by their static code features.
This categorisation subsequently guides the partitioning of work.
However, the method by which the compiler separates work is not specified.

In addition to the novel methodoloy, the paper finds very direct empirical evidence of the importance of work partitioning.
Figure 2 of the referenced paper displays the performance of several benchmarks against the ratio of work split between the GPU and CPU.
The heterogeneity of the results validates the search for effective, kernel-dependant workload partitioning.

\subsubsection*{Binary Analysis}
In work by \citet*{lee_transparent_2013}, the authors construct a framework that takes a users' data parallel OpenCL kernel and partitions the work across devices.
This is achieved through hooking into the OpenCL API layer to expose a single, large device.

Kernels are split at runtime using a decision tree heuristic, using approximations on the transfer costs of moving data between processors, and also the variance of performance of processors.
These parameters are estimated by the partitioning system, however it is not mentioned what the method of estimation is.

To determine whether a workload can be safely separated to several devices, data flow analysis is used on array indexing.
If the data flow analysis does not sufficiently guarantee safe array access patterns, the kernel is considered contiguous and thus not parallelisable.
This is an example of where a higher-level abstraction may have assisted in splitting the workload.
These are both potentially interesting directions for research on improving Accelerate, however they are beyond the current scope.

\subsubsection*{Dynamic Profiling}
\citet*{wang_cpu+gpu_2014} review several heterogeneous scheduling algorithms (which they refer to as `co-scheduling'), and compare against their own novel algorithm.
Although static scheduling is discussed, the focus is on methods that use dynamic profiling to achieve workload balance across processors.
Two competing dynamic scheduling algorithms are described: \textit{quick scheduling} and \textit{split scheduling}.
All of the dynamic scheduling algorithms discussed rely on the workload being split into some collection of iterations or fragments beforehand.

Quick scheduling uses static scheduling on some small, initial part of the workload.
By measuring performance in this first stage, the rest of the workload is appropriately partitioned between processors.
The authors remark that, since the performance of the GPU may depend on the workload, this single initial profiling step may lead to a partitioning of work that is inefficient for the rest of the program.
This is similar to one of the initial scheduling plans for this project.

Split scheduling is a form of `iterated quick scheduling': the profiling data from one chunk of workload is used to partition the workload for the next chunk.
Since data is synchronised between each work division, there is significant overhead due to the increased frequency of profiling relative to quick scheduling.

The novel algorithm proposed by the authors (Co-scheduling based on Asymptotic Profiling, or CAP) lies between quick and split scheduling.
In particular, workload chunks are only profiled if performance has changed substantially.
Otherwise, chunks are scheduled in progressively larger increments, helping to reduce synchronisation overhead.

In their results, the authors find that their algorithm is competitive with the other dynamic scheduling algorithms in terms of overall speed.
In addition, they find a reduction in the spread between GPU and CPU execution times.
The implementation of these varied algorithms may be a valuable extension for our thesis, or a future project.

The contributions of the paper are purely towards the scheduling algorithm.
The code to run workloads on the GPU and CPU was written by hand, with the scheduler taking the form of `glue code' in-between.
Although all the discussed algorithms rely on the workload being split into a large number of  `iterations', it is not specified in the paper how this workload splitting is performed.
The automation of these steps is an important part of the value of frameworks like Accelerate.

\subsection{Parallel DSLs}

\subsubsection*{Data Parallel Haskell}
Data Parallel Haskell (DPH) is a generic parallelism extension to the Glasgow Haskell Compiler.
For DPH, the focus is on \textit{nested data parallelism}, exploring and expanding on the work of the NESL language. \citep{chakravarty_data_2007}
While Accelerate uses some features of the Haskell type system to statically \textit{forbid} nested parallelism, DPH instead adds \textit{flattening} to the collection of representation transformations, converting nested parallel operations on a nested array into scalar operations on a flat array.

\subsubsection*{Copperhead}
Copperhead is a GPU programming EDSL hosted in the Python programming language. \citep{catanzaro_copperhead:_2011}
Currently, it targets the CUDA architecture.
It has a similar set of combinators to most array DSLs.
Since it is hosted in Python, expressions are untyped until executed, which leaves many potential common programmer errors unchecked until runtime.

Similarly to DPH, Copperhead supports nested parallelism.
However, while DPH follows in the tradition of handling nested parallelism through flattening, Copperhead attempts to follow the heirarchial parallelism of modern GPU architectures.
In particular, the CUDA programming model has a heirarchy of \textit{kernels} running \textit{thread blocks}, which in turn contain \textit{device threads}.
When possible, nested parallelism in Copperhead is mapped onto this heirarchy.

For fusion and similar optimisations, the compiler must perform `shape analysis' at run-time to determine the compatability of array sizes.
This contrasts with Accelerate, which uses Haskell's typeclass features and strong typing to ensure shape compatability.

Copperhead has limited support for targeting heterogeneous systems.
Devices must be declared explicitly, and any given computation targets a single device, implying that any scheduling must be done by the user.

\subsubsection*{Dandelion}
Dandelion is a .NET extension offering a compiler and runtime for heterogeneous systems, targeting the F\# and C\# languages. \citep{rossbach_dandelion:_2013}
LINQ is essentially a DSL within the .NET framework for describing operations over iterable collections in a monadic fashion.
Dandelion supports lifting most LINQ operations to the GPU.
It does so by using the Common Compiler Interface to convert .NET bytecode to CUDA source.

This binary analysis step has similar issues to those encountered by \citet{lee_transparent_2013}.
In particular, converting heap allocations to stack allocations requires data flow analysis to construct a static size for the original allocation.
If an allocation cannot be statically sized, the conversion fails.
The binary translation process also makes assumptions about purity of user-defined functions, which are not checked.
Combinator optimisations, like map fusion, are not implemented.

Dandelion uses explicit reasoning on a data-flow, task-dependency graph to implement heterogeneous scheduling and work division.
The graph is constructed through an intermediate engine called PTask, which describes various primitives for encoding iterative processes between data sources and sinks.
Many of the concepts are similar to those from stream processing; future work may try and translate some subset to Accelerate.

In addition to targeting CPU and GPU backends, Dandelion also supports distributed cluster computing as part of its model of heterogeneous systems.
This is an interesting and natural extension of the concept of `write once, parallelise everywhere' described by \citet{newton_converting_2014}.

\subsection{Heterogeneous Scheduling in Accelerate}
A recent (at the time of writing, unpublished) paper by \citet*{newton_converting_2014} describes a first foray into heterogeneous scheduling in Accelerate.
This is also the work that led to the previously described improvements to Accelerate - the separation of AST transformation phases, the improved final kernel representation, and the separation and abstraction of the hardware backends. 
In addition to these contributions, in their paper  \citeauthor{newton_converting_2014} introduce data fissioning as described previously, and explore two methods of scheduling tasks over the fissioned data.

\paragraph*{Bulk-Synchronous Parallel} 
Tasks were fissioned into some constant number of segments, which were in turn round-robin allocated onto processors.
Scheduling was performed in batches, and tasks were fissioned in dependency order.

This first method had no notion of device affinity, and so ran into memory bottlenecks since data would be frequently copied from processors to the host before the next batch was allocated.
In addition, the batch allocation added significant synchronisation overhead between rounds.
These deficiencies resulted in extreme performance degredation, and the authors do not persue the method further (which is a hint that we should not either).

\paragraph*{Single Program, Multiple Data}
As an alternative strategy, the authors use the dependency graph to ensure that at least some of the dependencies for a fragment are all allocated to the same device.
Data fissioning occured in the same manner as with the bulk-synchronous method.

The enforcement of the scheduling semantics of fissioning were split between both the fissioning stage of AST processing, and in the final device scheduler.
Namely, the fissioning algorithm is what made decisions about work ratios and so expected, for example, the first fraction of the segments to go on one device and the rest to another.
This was separately reflected in the scheduler as well. This latter method forms the foundation of this project.

\section{Work Plan}
There is much potential work within the scope of what has been discussed so far.
For the purposes of this project, the high-level goal is to have Accelerate able to fission a program written in its DSL into `jobs' that can be scheduled onto a heterogeneous set of workers (CPUs, GPUs) with a demonstrable performance boost, while also addressing some of the issues expressed in previous work.
In addition, the following are potential points of focus to provide guidance in achieving the desired result.

\subsection{Dynamic Fissioning}
The data fissioning described previously was always static: the low-level representation term would be fissioned into some finite and static number of array segments, and each work component would be sent off to the same processing unit (determined by index).

We can improve on this by determining the degree of fissioning and the allocation of fissioned segments dynamically, depending on factors such as the relative processing speeds of the processors.

\subsection{Small Array Optimisations}
Loading, running, and using the result of a GPU kernel has significant overhead.
Below a certain array size, the processing time of operations on an array is dominated by the high latencies of both loading the GPU kernel and data transfer between the CPU and GPU.

In these cases, it would be more effective to perform the operation on the CPU.
The existing Accelerate framework does not differentiate workloads by array size, and so does not take advantage of this.
Once we implement dynamic fissioning, we can look into including this optimisation.

\subsection{Extensions}
Below is a list of potentially valuable additions to the goals of this project.
Since they are not critical to the goal, they will be persued only if time permits.

\paragraph*{Improved Concatenation}
Currently, \icf{concat} nodes are converted into array generators using conditional indexing on the segments.
For instance if we have \icf{b\ =\ concat\ b1\ b2}, and if \icf{b1} and \icf{b2} are split at some index \icf{s}, this will be translated into

\begin{verbatim}
  b = generate (\i -> if (i < s) then (b1 ! i) else (b2 ! i))
\end{verbatim}

Although there are situations where the intervening \icf{generate} may be removed by inlining or through indexing with a constant value, performance may be improved otherwise by adding memory-copying primitives to the lower-level array representations.

\paragraph*{LLVM Support}
The current LLVM backend for Accelerate does not support some operations, such as stencils.
Expanding support for this feature will allow more comprehensive comparisons of fissioning transformations.

\paragraph*{Device Affinity}
Dynamic fissioning would be improved if we had a notion of `device affinity', so that data dependencies in the task graph are not unnecessarily copied between processors.

\paragraph*{Processor Affinity}
For some tasks such as sorting and general folds, CPUs may be as fast as GPUs.
For this reason, after fissioning we may prefer that a given segment of work be performed on a particular kind of processor.
Handling this form of `task affinity' may provide additional improvements to performance.

\subsection{Initial Technical Plan}
The existing framework relies on the scheduling backend reacting to \icf{split} and \icf{concat} nodes in the final representation, and splitting work accordingly.
Currently, the process of introducing these fragmenting nodes occurs in a single phase, after high-level map fusion.
Investigating the interaction of data fissioning with other operations and optimisations will involve separating out the fusion steps, so as to insert fissioning between them.
Adding information about available processors will require providing some data to most of the compilation steps: we can achieve this with something like the reader monad, if needed.
Adding affinities may involve adding metadata to the fissioning nodes themselves.

\section{Work Schedule}
As this is partially a development thesis, we must form a development plan.
The below schedule details the hopes and expectations for when parts of the development phase will be completed.
Included are milestones to be used as checks on whether these expectations have been met.
The final report is expected to be written in tandem with the development stages: each week and each milestone has an implicit requirement, `have something written down about this'.

\subsection{Timetable}

\begin{description}
  \item[Week 1 - 4:] 
    Familiarise myself with Accelerate.
    \begin{description}
      \item[Week 1:] 
        User-facing DSL. 
        \\\milestone a simple Accelerate program, say a Newtonian gravity simulation.
      \item[Week 2 - 3:] 
        Compilation phases. 
        \\\milestone implement a simple metadata-generating phase, as a test of understanding.
      \item[Week 3 - 4:] 
        Accelerate backends (mainly LLVM)
    \end{description}
  \item[Week 5 - 9:] 
    Write scheduler.
    \begin{description}
      \item[Week 5 - 6:] 
        Have fissioning working on the AST. 
        \\\milestone produce index-partitioned ASTs at kernel generation step.
        \\\milestone produce ASTs with optimisations for small array sizes.
      \item[Week 6 - 7:]
        Emit to both CPU and GPU-facing backends. 
        \\\milestone have above kernels produced and split between CPU and GPU targets, at some static fraction.
        \\\milestone implement small-array CPU optimisation as part of scheduling.
      \item[Week 7 - 9:]
        Implement dynamic scheduling.
        \\\milestone a runtime utility to determine what backends and processors are available, along with their processing speeds and bus transfer limits (both between and within processors).
        \\\milestone (Extension) have task fissioning and task allocation take into account memory dependencies and relative processing speed of processors.
    \end{description}
  \item[Week 10 - 12:]
    Benchmarks.
    \\\milestone Compare performance on common problems (Black Scholes, $n$-body) with and without scheduler.
    \\\milestone Compare vs. previous scheduler implementation from \citet{newton_converting_2014}, hopefully seeing improvement.
    \\\milestone Show improvement due to separate stages of scheduler optimisation: small-array CPU scheduling, task partitioning, preventing permute fusion.
    \\\milestone (Extension) Show improvement due to dynamically informed allocation vs. static strategy.
  \item[Week 13 - Due:] Buffer time for the inevitable. Clean-up for final report.
\end{description}

\subsection{Measures of Success}
For those milestones directly related to construction of the scheduler, there are two `parameters' for success: depth and breadth.\footnote{This conceptual divison is not due to us: we rephrase it here, but it is originally from \citet{newton_converting_2014}.} 
`Depth' in this context refers to successfully processing an AST through all the relevant compiler passes. 
`Breadth' refers to having depth completion across Accelerates' many array operations (maps, folds, permutes, and recently iteration constructs).
Cleary depth completion is a necessary prerequisite for most of the desired results concerning scheduling, however breadth is important for assessing the interaction between task fissioning and compilation optimisations like fusion.

\pagebreak

\bibliographystyle{unsrtnat}
\bibliography{./ref/bibliography,./ref/websites}

\end{document}
