15-499: Parallel Algorithms (Guy Blelloch)
cs.cmu.edu
cs.cmu.edu
If you don't know what a prefix sum is, and you want to do anything parallel - whether that's bit parallelism tricks on a "SIMD within a register" tricks in a x86 register, all the way up to programming parallel algorithms on a 64K-thread GPGPU - you should read this paper.
Prefix sum is the smart person's map-reduce (ok, I'm sort of trolling with that one, map-reduce is great).
(Don't be thrown by the typo in the first example. Correct output should be: [3 4 11 11 15 16 22 25] )
FYI, Guy wrote the original parallel FFT for the Thinking Machines Connection Machine, IIRC.