Prefix Sums and Their Applications (1993) [pdf]

This is one of my favorite papers, along with the accompanying language NESL and follow-up paper "more types for nested data parallelism."

As an example, we used prefix sums to optimize concurrent dynamic memory allocations in GPUs for sc-lang.com . NESL is influencing some of what we want to build next at our startup, graphistry.com. Would love to talk to folks if this sort of thing gets them excited (fast forward 30 years by doing in the cloud/browser and apply to scaling data visualization/exploration code .)

These are also related to "Integral Images" or "Summed Area Tables" [1] which are used in computer vision and graphics (resp.) for many purposes (most prominently in the Viola-Jones face detector). The benefit is that taking the sum of any axis-aligned rectangle becomes a constant time operation:

  sum = bottom right - top right - bottom left + top left 

(if numbering starts from top-left). You can also compute variances in constant time this way by summing squares of numbers, etc.

[1] http://en.wikipedia.org/wiki/Integral_image

The PRAM model itself is interesting.

http://en.wikipedia.org/wiki/Parallel_Random_Access_Machine

> "Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as synchronization and communication, but provides any (problem-size-dependent) number of processors."

It was a year after this paper that the Fenwick Tree came out. It compresses storage for the prefix sum into an N-length array instead of 2N-1. This is what's used in stochastic algorithms for chemical reactions.

Thanks, nice compilation. But is it me or is the first all-prefix-sums example wrong?