Parallelism
==

English prose on parallelism.

Some sources
------------

* [A programming technique for non-rectangular
  data](https://dl.acm.org/doi/pdf/10.1145/800136.804488): I think the first
  paper to present the segmented operations that are the bread-and-butter of
  flattening nested data parallelism. The paper discusses a "partition
  operator", which applies a given function to the segments of an array given by
  what we would today call a "flag array" (a vector of booleans indicating when
  a new segment begins). However, the partition operator cannot be implemented
  in APL in its full generality; instead the paper presents implementations of
  the partition operator specialised to various built-in functions (e.g. prefix
  sum, to produce segmented prefix sum).

* [An O(n² log n) parallel max-flow
  algorithm](https://www.sciencedirect.com/science/article/pii/019667748290013X?via%3Dihub):
  to my knowledge the paper with the first instance of the now-common work/span
  model for characterising parallel algorithms. It was not at this time a
  language-based parallel cost model, however - I think Blelloch may be the
  first to have had that idea.

* [More Fun with Monoids](https://okmij.org/ftp/Algorithms/monoid-fun.pdf) by
  Oleg Kiselyov describes the theory behind monoids in a map-reduce context, and
  gives a very nice explanation of *vertical* composition of monoids -
  essentially a kind of (manual) fusion. Apart from being theoretically
  beautiful, it is also eminently practical - the performance advantages can be
  quite dramatic. The most mind-bending example in this paper is implementing
  Boyer-Moore majority voting with an operator that is not *as such*
  associative, but is in fact associative given an extended definition of
  equality.