3 ms·
This looks like a great course. Guy is responsible for some really good work in parallel algorithms and I still find "Prefix Sums and Their Applications" worth
by onan_barbarian 15y ago
This looks like a great course. Guy is responsible for some really good work in parallel algorithms and I still find "Prefix Sums and Their Applications" worth going back to despite it being a 21-year-old paper in a fast-changing field.
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).
- alanning 15y agoThe paper can be found here: http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf (Don't be thrown by the typo in the first example. Correct output should be: [3 4 11 11 15 16 22 25] )