\documentclass[preprint]{sigplanconf}
\usepackage[pdftex]{graphicx}
\usepackage{code}

% -- Utils --------------------------------------------------------------------
\newcommand{\TODO}[1]	{\emph{\textbf{TODO:} #1}}
\newcommand{\BL}[1]	{\emph{\textbf{BL:} #1}}



% -- Header -------------------------------------------------------------------
\begin{document}
\preprintfooter{\textbf{--- DRAFT --- DRAFT --- DRAFT --- DRAFT ---}}

\title{Unboxed Functions for Flat Data Parallelism}
\title{Unboxed Functions for Flat Data Parallelism}
\authorinfo{
  \shortstack{%
    Ben$^\dagger$ 
    \and
    Gabriele$^\dagger$ 
    \and 
    Manuel$^\dagger$ 
    \and 
    Roman$^\dagger$ 
    \and
    Simon$^\ddagger$ 
  }
}{
  \vspace{5pt}
  \shortstack{
    $^\dagger$Computer Science and Engineering \\
    University of New South Wales, Australia \\[2pt]
    \textsf{\{keller,chak,rl,benl\}@cse.unsw.edu.au}
  }
  \and
  \shortstack{
    $^\ddagger$Microsoft Research Ltd \\
    Cambridge, England \\[2pt]
    \textsf{\{simonpj\}@microsoft.com}
  }
}
{}
\maketitle

\makeatactive


% -----------------------------------------------------------------------------
\begin{abstract}
The quick fix:
\begin{itemize}
\item	A primitive polymorphic forcing function that forces all the thunks in a value, including thunks
	in the closure of a function. SDM once mentioned that something like this was proposed for Haskell'.
	
\item	For DPH functions like: \\
 	@parMap :: (a -> b) -> Array a -> Array b@ \\
	They could force all the thunks in the function argument before starting the main parallel computation.
\end{itemize}
\medskip
Separating lifted from unlifted (direct) values in the type system:

\begin{itemize}
\item	Introduce the kind unlifted value types (@&@). Make it a subkind of the regular @*@. 
	Unlifted types can be passed to polymorphic functions which makes @(&)@ different from @(#)@.
	During conversion to STG, don't suspend function applications that produce values of the unlifted kind. 
	With algebraic types of this kind, perhaps also require their data constructors to be fully applied.

\item	Use the forcing function to convert values from @(*)@ to @(&)@ versions. Say @(a :&> b)@ is the type
	of functions that do not reference suspensions in their closure. This type has kind @(&)@. One instance
	of the forcing function would have type: \\
	@force :: (a -> b) -> (a :&> b)@
\end{itemize}
\end{abstract}


% -----------------------------------------------------------------------------
\section{Introduction}
\label{section:Introduction}

The execution model of Data Parallel Haskell (DPH) is based around a ``Gang'' of threads. The Gang is created when the program starts, and persists until the entire program has finished evaluating. The Gang comprises of one worker thread for each HEC (Haskell Execution Context) / hardware thread on the host machine. There is only one gang per program. When executing the data parallel portions of the program, although each data parallel computation makes uses of all the threads in The Gang, successive parallel computations should be serialised. We do not want to have multiple independent gangs running on the same machine due to the overhead of context switching, and the fact that a computation using a single gang should already make full utilisation of the machine. This is discussed further in \S\ref{section:SingleGang}

However, as we are using Haskell as the host language, and Haskell uses lazy evaluation as the default, ensuring that data parallel computations are sequenced appropriately can be tricky. For example, the following expression produces a new array by adding the sum of the array @arr1@ to each element of @arr2@:

\begin{code}
  let x = parSum arr1
  in  parMap (\y -> x + y) arr2
\end{code}

As Haskell is lazy, ``evaluating'' this expression merely allocates two thunks, one for the application @parSum xs@ and another for the application @parMap (\y -> x + y) ys@. The function @parMap@ performs an element-wise parallel map using The Gang. In DPH, arrays are bulk-strict, meaning that when we demand any element of the result array, every element is evaluated.  However, in the above example, computing the value of the first element requires the value of @x@, which also needs The Gang. This results in nested parallelism, meaning that one parallel computation has created another, which we wish to avoid. In related work, we support Nested Data Parallelism (NDP) by performing a vectorising transform that converts a program using nested data parallelism to one that does not. Clearly, during this transform we must ensure that expressions like the one above are not inadvertently created. We also wish to ensure that hand written programs using the DPH library do not use nested parallelism. If they do, then our current implementation simply evaluates the nested computations sequentially.

If we wish the summation in the above example to run in parallel, then we must ensure that it completes before any element of the result is demanded. We can achieve this using the @parSeq@ operator that evalutes its first argument to whnf before proceeding to its second:

\begin{code}
  let x = parSum arr1 
  in  x `pseq` parMap (\y -> x + y) arr2
\end{code}

This solves the immediate problem, but is unsatisfying for two reasons. The first is that if a programmer writes @parSum arr1@ then they intend for the result to be evaluated in parallel. After unambiguously conveying their intention, if our system evaluates it sequentially, then from the programmer's point of view this behaviour is wrong. The second is that the runtime performance of large Haskell programs is already too hard to predict. For some applications this is of little consequence, but for a parallel array library it clearly matters. If we take the approach that slow programs are ``wrong'', then by rights our original example should yield a type error. 

\TODO{mention what the solution is.}

\bigskip
The main contributions of this paper are:
\begin{itemize}
\item	We discuss the practical aspects of designing a library that can serve as both the target for a vectorising transform as well as being useful directly from the source language. 

\item	We explore the design space for statically guaranteeing that parallel programs using this library run as intended.

\item	\TODO{We present a pleasing solution to all our problems.}



\end{itemize}


% -----------------------------------------------------------------------------
\section{Single Gangs of Many Threads}
\label{section:SingleGang}

\begin{itemize}
\item	Say something more convincing about not just using multiple gangs. We need to separate the fundamental problem of preventing nested parallelism from the implementation cost of using multiple gangs, and the specifics of our library. Just saying ``we're not setup to use multiple gangs'' isn't good enough.

\item	Can we try using multiple concurrent gangs and measure what the cost is?

\item	Say more about the cost-model as seen by the user. If we have @parMap@ in the program then we should be able to give a static guarantee that expression will be evaluated in parallel. 

\item	Defaulting to sequential computation also breaks load balancing. If a nested computation starts being evaluated sequentially, then the rest of gang finishes, we have to wait for that sequential computation to finish while leaving the rest of the machine idle.

\item	Dynamic load balancing could solve the previous problem, but is more complicated. The present DPH library is based on static load balancing. On @N@ processors, break the result array into @N@ chunks and evaluate one on each.

\item	We also want a lower-level language to serve as the target for the vectoriser. That language should give a static guarantee that all nested parallelism has been eliminated.
\end{itemize}

\TODO{The interesting part of the gang core is fairly small, we could discuss it directly. It's in \\ @dph-prim-par/D./A./P./Unlifted/Distributed/Gang@} 

\begin{figure}
\begin{code}
  type Req
   = ( Int -> IO ()    -- Action to run.
     , MVar () )       -- Write when done.

  newReq  :: (Int -> IO ()) -> IO Req
  waitReq :: Req -> IO ()
  execReq :: Int -> Req -> IO ()

  data Gang 
   = Gang Int          -- Threads in gang.
          [MVar Req]   -- Running requests.
          (MVar Bool)  -- Whether gang is busy.

  forkGang :: Int -> IO Gang
  forkGang n 
   = do mvs <- sequence (replicate n newEmptyMVar)
        zipWithM_ forkOnIO [0..] 
               (zipWith gangWorker [0 .. n-1] mvs)
        busy <- newMVar False
        return (Gang n mvs busy)

  gangWorker :: Int -> MVar Req -> IO ()
  gangWorker threadId reqVar
   = do req <- takeMVar reqVar
        execReq threadId req
        gangWorker threadId reqVar

  issueRequest :: Gang -> (Int -> IO ()) -> IO ()
  issueRequest gang@(Gang n mvs busy) p 
   = do b <- swapMVar busy True
        if b then mapM_ p [0 .. n-1]
             else do parIO gang p
                     swapMVar busy False
                     return ()

  parIO :: Gang -> (Int -> IO ()) -> IO ()
  parIO (Gang n mvs _) p 
   = do reqs <- sequence (replicate n (newReq p))
        zipWithM putMVar mvs reqs
        mapM_ waitReq reqs
\end{code}
\caption{The Gang}
\end{figure}


% -----------------------------------------------------------------------------
\section{Monads and Effects}
In \S\ref{section:Introduction} we mentioned that the combinator @pseq@ can be used to explicitly sequence two parallel computations, as shown in the following example.

\begin{code}
  let x = parSum arr1 
  in  x `pseq` parMap (\y -> x + y) arr2
\end{code}
The full type of @pseq@ is:

\begin{code}
  pseq :: a -> b -> b
\end{code}
With a nod to the ``free theorems'' of \cite{wadler:theorems-for-free} we note that there is something suspicious about this type. The variable @a@ appears only as a parameter and not in the result, meaning this argument is discarded. The variable @b@ appears as a parameter and in the result, meaning it is passed through unchanged. Although @pseq@ is a no-op at the value-level, its true utility is at the operational level, where it reduces its first argument to whnf \emph{before} returning its second. At this level @pseq@ causes an observable side effect. As this is a Haskell paper, once we've seen the side effect we know there's a monad lurking close by.

Define @ParM a@ to be the type of computations that produce a result of type @a@ in a data parallel fashion, possibly using The Gang. We can now create monadic versions of @parSum@ and @parMap@ that reveal the side effect in their types:

\begin{code}
  parSumM :: Num a => Array a -> ParM a
  parMapM :: (a -> b) -> Array a -> ParM (Array b)
\end{code}
Instead of using @pseq@ for sequencing, we now rewrite our example using the do-notation.

\begin{code}
  do  x <- parSumM arr1
      parMapM (\y -> x + y) arr2    
\end{code}
This ensures that the summation completes before calling @parMapM@, which ensures flat parallelism, but we have introduced a new problem. DPH programs compiled via the vectoriser are critically dependent on code-motion style optimisations and user defined rewrite rules, which are used to fuse computations and eliminate intermediate data structures. This is also true for external libraries that make use of DPH arrays, such as Repa \cite{keller:repa}. The usual thread-the-world implementation of state monads imposes a total sequential ordering of computations in that monad, which defeats these optimisations. The invariant we are trying to impose is that a new data parallel computation should not be started while another is already running, but requiring all such computations to be totally ordered is too big a hammer.


% -----------------------------------------------------------------------------
\section{Explicit versus Indirect Nesting}
Suppose the programmer had written an expression that uses nested parallelism explicitly:

\begin{code}
  parMap (\y -> parSum arr1 + y) arr2         (1)
\end{code}
Compared with our original example from \S\ref{section:Introduction}, in this case it's obvious from the form of the program that one parallel computation will invoke another. Perhaps here it would not be so bad to evaluate the inner sum sequentially. We could also permit the following:

\begin{code}
  let worker y = parSum arr1 + y              (2)
  in  parMap worker arr2
\end{code}
Once again, in this example the nesting is ``lexical''. With @(1)@ it's clear that @parSum@ will be invoked by @parMap@, and @(2)@ is just a sugared form of @(1)@. From a program transform point of view, it is always safe to convert between these two forms as doing so does not change the meaning of the program, nor does it require more work. However, our original example is different:

\begin{code}
  let x = parSum arr1                         (3)
  in  parMap (\y -> x + y) arr2
\end{code}
A compiler should never inline the @x@ binding because then it would be recomputed for each element in @arr2@. We intend to allow forms @(1)@ and @(2)@ because they are easy to spot and reason about, but reject form @(3)@. \TODO{maybe}.

\begin{itemize}
\item	What is preventing the compiler from converting form @(1)@ to form @(3)@? This is just the application of the full-laziness transform. In general we \emph{want} lifted bindings to be lazy because this guards against the case where they diverge (or take a long time to evaluate).

\item	Suppose we say: what we want is to ensure the function passed to @parMap@ does not reference a thunk that can start of a new parallel computation. We must also ensure that offending thunks cannot be created during optimisation. If we don't want to hack the optimiser then maybe we want to reject @(1)@ and @(2)@ as well.
\end{itemize}


% -----------------------------------------------------------------------------
\section{Internal versus External APIs}

\begin{itemize}
\item 	There are two aspects to this work. On one hand we want a nice language to serve as the target for the vectoriser. On the other, we want to give a static guarantee that parallel programs written directly with the DPH library, or with others such as Repa, really do run in parallel.

\item	Say more about the tradeoffs. If we're focused on providing a target language to the vectoriser, then we don't care if it's a bit ugly or verbose. If we add a new feature it may not affect the source language at all, as vectorisation is a core-to-core pass only. If the internal DPH library has to care about it then it needs to be usable, but doesn't have to be pretty. If client programmers have to use it then it needs to fit in with the rest of Haskell, and give nice error messages etc. 
\end{itemize}


% -----------------------------------------------------------------------------
\section{Unboxed functions}

Suppose we change the type of @parMap#@ to require an \emph{unboxed function} instead of a regular one.

\begin{code}
  parMap# :: (a -#> b) -> Array a -> Array b
\end{code}

An unboxed function is one that can be represented by a code-pointer only, and is thus guaranteed not to be a partial application or suspension of some other function application. Doing this also ensures that the closure of the function is empty, meaning that all the free variables it references must be defined at top-level or be an occurrence of the parameter variable. 

\begin{itemize}
\item	A constraint like ``can only reference top-level variables" complicates program transformation. What happens if we want to float a top-level binding inwards? Doing so will break the constraint.

\item	The fact that the function is unboxed isn't the important part. When a value is unboxed it means we can store it in a register, but for our purposes we're more interested in ensuring that the closure is empty.

\item	If we add ``actual'' unboxed functions we need to allow unboxed tuples on the left of function arrows. \\
	@  thing :: (# Int, Int #) -#> Int@ \\
	If we don't do that we have to worry about partial application of unboxed functions of higher arity. For example:
	@  thing2 :: Int -#> Int -#> Int@ \\
	If we want that to be an ``unboxed function of arity-2'' we'll have to prevent it from being partially applied.
\end{itemize} 

Maybe unboxed functions are useful for other things as well. Here are some nice properties:
\begin{itemize}
\item	Not $\bot$
\item	Represented as a single machine word.
\item	GC can ignore them as it doesn't need to trace the closure.
\end{itemize}


% -----------------------------------------------------------------------------
\section{DeepSeq-able and Direct functions}

If we focus on preventing a function from holding onto thunks in its closure, then we we don't actually need that closure to be empty. We can represent closure-ful functions in terms of the unboxed functions from the previous section.

Define the type of functions that have explicit closures, require that the closures can be deepSeq-ed.

\begin{code}
 data a -@> b 
  = forall c. DeepSeq c => DsClo c ((#c, a#) -#> b)
\end{code}

The version of @parMap@ taking one of these functions has type:
\begin{code}
  parMapDS :: (a -@> b) -> Array a -> Array b
\end{code}

If @parMapDS@ wants to ensure that its function parameter contains no thunks, it can simply apply @deepSeq@ to its closure before starting the main data parallel computation. Note that regular functions are not deepSeq-able, so they cannot appear in one of these closures. 


\begin{itemize}
\item	This could create problems for partial application and type-class dictionaries.
	For example, how do we convert the following expression to this form? \\
 	@zipWith (+) xs ys :: Array Int@ \\
	When this expression is translated to core it will be partially applied to the dictionary
	@Num Int@, which contains instance functions for the @Num@ class.

\item	How do we actually produce a value of type @((#c, a#) -#> b)@. What does it look like syntactically?
	Will we have trouble with the optimiser moving bindings around?

\item	Another massive complication is method calls. Suppose we try to enforce something about ``functions not referencing thunks''. What happens when someone uses a type-class method in the body of an unboxed function? We can't ``see through'' the method to check what it's really referencing.
\end{itemize}


A more heavy-weight/long-range option would be to prevent functions with thunks in their closures from ever being created. Some vague ideas:

\begin{itemize}
\item	Define a new kind @&@ as the kind of values that cannot reference thunks. This kind @&@ would be a subkind of @*@, assuming that's possible. Maybe the ~@(->) :: ?? -> ? -> *@~ business could be cleaned up and/or formalised along the way.

\item	Define some new types like @DirectInt :: &@ as the type of integers that cannot be thunks.

\item	Define a type class @Forceable@, like @DeepSeqable@ but the return type guarantees that the function doesn't contain thunks. This would be the primary means of creating objects of kind @&@. Maybe we can use associated types / representation type tricks to make this painless. \\
	@  class Forceable (a :: *) (b :: &) where@ \\
	@     force :: a -> b@ 

\item	Define the type of functions that have explicit closures, and those closures cannot reference thunks. \\
	@  data a -&> b@ \\
	@   = forall (c :: &). DsClo c ((#c, a#) -#> b)@
\end{itemize}


% -----------------------------------------------------------------------------
\section{Supercombinators}

If we focus on producing a nice target language for the vectoriser, then what we really want is a strict supercombinator language. The output of the vectoriser would consist of supercombinators only, without regular functions. Regular functions in non-vectorised parts of the program are free to call supercombinators but not vis-versa. Intuitively, a supercombinator can always be represented by a code pointer.

\subsection{Defining supercombinators}
Supercombinators are functions that are:

\begin{enumerate}
\item	Always defined at top level.
\item	Always defined with $\geq$ 1 arguments.
\item	For a super of arity-N, an occurrence is always applied to 0 or N arguments.
\item	The free variables in the body of a supercombinator are only supercombinators.
\end{enumerate}

We write supercombinator bindings with a @=#@, so an example program that mixes supercombinators and regular functions might look like:

\begin{code}
  f =# \x. \y ... f ... g x ... 
  g =# \x. ... f ... 

  h = \x. \y. ...
\end{code}

\begin{flushleft}
{\bf Alternatively:} Supercombinators are functions that are:
\end{flushleft}

\begin{enumerate}
\item	Always defined at top level.
\item	Have exactly one argument, which can be an unboxed tuple.
\item	Can be applied to zero or one argument.
\item	The free variables in the body of a supercombinator are only supercombinators.
\end{enumerate}

\begin{flushleft}
{\bf Alternatively:} Supercombinators are functions that are:
\end{flushleft}
\begin{enumerate}
\item	A variable @v@ that is bound at top-level to a value of type @-#>@.
\item	A literal unboxed function @(\# x -> e)@ must only have top level supercombinators as free variables.
\end{enumerate}

\subsection{Properties of Supercombinators}
Some other properties:

\begin{itemize}
\item	It's ok to suspend calls to them.

\item	They don't have to be strict.

\item	Supercombinators cannot refer to thunks from the outside.

\item	Semantic assumption at the moment, that functions like \\ 
	@(+) :: Num a => a -> a -> a@ don't invoke nested parallelism.

\item	Supercombinators can take regular functions as their arguments.

\item	Maybe we want to define them using positional notation for the arguments.
	@\* -> \* -> ... *1 ... *2 ...@

\item	Perhaps we can get Template Haskell to convert a function to supercombinators for us.\\
 	Something like:
	@\$(mkClo [| \x -> x+n |]) ys@
\end{itemize}

\subsection{Supercombinators vs unboxed functions}
Assuming supercombinators are given unboxed types, we can't just rely on those types to determine if something is a supercombinator. For example:

\begin{code}
 data C = C (Int -#> Int)

 f :: C ->  (Int -#> Int)
 f y = case y of (C v -> \# x -> v x)
\end{code}

Consider the inner function @(\# x -> v x)@. The variable @v@ has type @Int -#> Int@, and is fully applied. \TODO{BL: I don't get what the problem is here.} 

There is no problem with thunks due to the ``automatic evaluation'' of the ``unboxed values as first class citizens'' paper. The expression @f (C succ)@ has type @(Int -#> Int)@, which is unboxed. It will not be represented as a thunk as it'll be forced to HNF by the desugarer.
 


\bigskip
% -----------------------------------------------------------------------------
\paragraph{Acknowledgements}

\bibliographystyle{abbrvnat}
\bibliography{Main}

\end{document}















