\section{Related Work}
Approaches to the implementation of irregular parallelism roughly fall into two categories: thread-based implementations, like Manticore \cite{Fluet:2008:Manticore} or Ct \cite{ghuloum-etal:Ct}, and those based on flattening. Both have their advantages and drawbacks. With the former approach, scheduling, synchronisation, and granularity control are a concern, as well as a more restricted set of target architectures, though they do not suffer from the complexity problem described in this paper. However, the problem we describe is a fundamental issue for all flattening based approaches, and has been identified and discussed in several publications. 

The original first-order flattening transform and array representation shown in Figure~\ref{figure:OldArrayRepresentation} was introduced by Blelloch and Sabot in in \cite{Blelloch:compiling-collection-oriented-languages}. In this work the @replicate@ function is called @distribute@ when applied to scalars and @distribute-segment@ when applied to arrays. As a possible extension to the handling of conditionals they suggest operating on sparse segments instead of first eliminating gaps between them with the @pack@ operation. This idea is not elaborated further. The single example program they present (Quicksort) only uses @distribute@ and @pack@ on arrays of scalars, and thus does not suffer problems with asymptotic complexity. 

In \cite{Blelloch:vector-models} Blelloch proves that a subset of programs written with the scan-vector instruction set can be vectorised while preserving their asymptotic work and step complexity. Such programs must be both \emph{contained}, and not use indirect memory access, which is equivalent to disallowing functions to have free variables. Appendix C of the NESL manual \cite{Blelloch:nesl-3_1} gives the work complexity of vectorised programs, and states that the contents of free variables is copied across each iteration of the @apply-to-each@ (@map@) construct. Finally, in \cite{Blelloch:provable-type-and-space-efficient} the authors present a provably time and space efficient version of NESL, but the operational semantics is based around fine grained threads instead of SIMD style vectors. 

In \cite{Palmer:work-efficient-nested-data-parallelism}, Palmer et al.\ address the issue by disallowing partial applications and removing some of the problematic cases
using rewrite rules. For Haskell, ruling out partial applications to appear anywhere in a parallel context would be neither  desirable nor statically enforceable. The rewrite rules used do not fire if the offending index space transform is applied indirectly as part of another function. This is a general drawback of using rewrite rules, which can be acceptable if the rewriting only leads to a constant improvement, but not in our case, where the failure to identify problematic expressions results in asymptotically worse performance.

In \cite{Riely:flattening-improvement}, Riely and Prins solve this problem by using vectors of references, but at the time the article was written, there was no implementation, so they could not provide any experimental data as to the absolute performance. To the best of our knowledge, they have not published any further results on this approach. The suggested representation is similar to one of the states our representation can take on, for example, as a result of creating a nested vector by
collecting a number of different flat arrays in a nested one. However, the use of purely pointer based representations can lead to poor locality and complicates distribution and load balancing. It also increases garbage collection overhead, as every subarray must be traversed individually. In contrast, our approach aims at keeping the data representation as flat as possible, and only resorts to the partially flattened representation whenever the completely flat representation would lead to 
worse work complexity. 

\eject