Nested data parallelism
==

Notes on flattening (or otherwise handling) nested data parallelism (NDP). To my
knowledge, Guy Blelloch's work on
[NESL](https://www.cs.cmu.edu/~scandal/nesl.html) was the first to do it.

* [Compiling collection-oriented languages onto massively parallel
  computers](https://www.sciencedirect.com/science/article/abs/pii/0743731590900876):
  Very early flattening paper, and one that made the crucial observation that
  you only have to lift a function once, not at every possible nesting depth.

* [Nepal – Nested Data-Parallelism in
  Haskell](https://dl.acm.org/doi/10.5555/646666.699740)
  ([PDF](../files/../nepal-ndp-haskell-europar-2001.pdf)) is I believe the first
  paper in the series that would eventually be published about [Data Parallel
  Haskell (DPH)](https://wiki.haskell.org/GHC/Data_Parallel_Haskell), although
  it is not the first paper by the author's on the flattening technique they
  propose, which is unusual (compared to NESL's) in supporting recursive data
  structures and sum types. The language presented in the paper, Nepal, is very
  similar to DPH, and their nicest example (Barnes-Hut *n*-body) would also show
  up in several DPP papers. Although Nepal is a fairly conservative extension to
  Haskell, the main type it introduces (parallel arrays) are strict, and all
  primitive types stored in them are also strict. Laziness does not mesh well
  with NDP, and I believe DPP carried on the same design unchanged. The paper
  does not go into detail on the flattening technique

* [More Types for Nested Data Parallel
  Programming](https://dl.acm.org/doi/10.1145/357766.351249) describes the
  flattening technique used in Nepal (and by extension, DPH), which supports
  higher-order functions and recursive types (although it's not the first paper
  to do so), and user-defined sum types (which I believe is novel to this
  paper). The paper also claims that it enables separate compilation, which may
  well be true, but I do not understand why this is challenging in the presence
  of flattening, since flattening a function produces a lifted function with a
  predictable type. It is possible to apply conventional Blelloch-style
  flattening to each function in isolation and link them much later (although
  this of course precludes context-driven optimisation). The paper is worth
  reading for the clean description of the flattening algorithm as a systematic
  program transformation.