hunk ./divide-conquer.tex 41
-\title{Parallel Divide-and-conquer Algorithms for Data-intensive Problems%
+%\title{Parallel Divide-and-conquer Algorithms for Data-intensive Problems%
+\title{Parallel Divide-and-conquer Algorithms as Array Code in Haskell%
hunk ./divide-conquer.tex 78
-  We show how to implement divide and conquer algorithms with Data Parallel Haskell.
+  Divide-and-conquer algorithms are an attractive category of algorithms for parallel programming.  However, the performance and scalability of list and tree-based versions is limited, especially for data-intensive problems.  Array-based versions have the potential to be more efficient, but are often harder to implement and parallelise.  We illustrate at \TODO{HOWMANY} examples that \emph{nested data parallelism}, as implemented in Data Parallel Haskell, might provide a middle ground.  It supports a purely functional, list-like array abstraction and implicit parallelism for all array operations.  We compare both the source code as well as the sequential and parallel performance of divide-and-conquer algorithms implemented with lists, the vector package, and Data Parallel Haskell.
hunk ./divide-conquer.tex 85
-Divide-and-conquer algorithms appear to be obvious candidates for parallelisation.  They split a large problem into a number of smaller subproblems that can be solved independently, possibly in parallel.  Nevertheless, the effective parallelisation of these algorithms comes with its own set of challenges.  Some of these challenges are related to load balancing and granularity: problems may be split into subproblems of strongly varying complexity and recursive problem decomposition can lead to a huge number of fine-grained work items.  Other challenges are related to the splitting of a problem into subproblems and the merging of subsolutions into overall solutions.  Both tasks can themselves be rather work intensive and require parallelisation to achieve good overall parallel scalability --- Amdahl's law tells us that even a small sequential fraction of the overall runtime can seriously limit scalability~\cite{amdahl}.
+Divide-and-conquer algorithms are obvious candidates for parallel programming.  They split a large problem into a number of smaller subproblems that can be solved independently, possibly in parallel.  Nevertheless, the effective parallelisation of these algorithms comes with its own set of challenges.  Some of these challenges are related to load balancing and granularity: problems may be split into subproblems of varying complexity and recursive problem decomposition can lead to a huge number of fine-grained work items.  Other challenges are related to the splitting of a problem into subproblems and the merging of subsolutions into overall solutions.  Both tasks can themselves be rather work intensive and require parallelisation to achieve good overall parallel scalability --- Amdahl's law tells us that even a small sequential fraction of the overall runtime can seriously limit scalability~\cite{amdahl}.