4 ms·
This is brilliant stuff, and has held up very well. The PRAM model seems a little dated by modern standards (it doesn't accurately model actual any parallel com
by raphlinus 5y ago
This is brilliant stuff, and has held up very well. The PRAM model seems a little dated by modern standards (it doesn't accurately model actual any parallel computer we'd want to build today), but the insight that there is a lot of parallelism and a lot of flexibility about how to extract that parallelism remains solid. Prefix sum (or parallel scan) is one of the core algorithms that works well on GPU.
Another great thing about this work is showing how flexible the generalizations of "sum" can be. A lot of problems can be restated in terms of an associative operator, and doing so unlocks all that parallel goodness.
- ravioactive 5y ago> The PRAM model seems a little dated by modern standards I was just curious to ask, as opposed to what all models?
- raphlinus 5y agoBasically a GPU, as that's the highly parallel machine you're most likely to program any time soon. I'm not sure there's anything quite like PRAM in the sense that it's a mathematically abstract model that nonetheless captures something interesting about performance, but Volkov's thesis is a pretty good start for modeling both the memory and ALU cost of a GPU computation: https://digitalassets.lib.berkeley.edu/etd/ucb/text/Volkov_berkeley_0028E_16465.pdf https://digitalassets.lib.berkeley.edu/etd/ucb/text/Volkov_b...