Nested data parallelism

Notes on flattening (or otherwise handling) nested data parallelism (NDP). To my knowledge, Guy Blelloch's work on NESL was the first to do it.

• Compiling collection-oriented languages onto massively parallel computers: 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 (PDF) is I believe the first paper in the series that would eventually be published about Data Parallel Haskell (DPH), 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 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.