Parallelism

English prose on parallelism.

Some sources

• A programming technique for non-rectangular data: 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: 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.