---
title: Parallelism
---

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.