Re:Prefix Sums and Their Applications (1993) [pdf]
by lmeyerov on Monday May 26, 2014 @02:00PM
(#7800782)
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 .)
Re:Prefix Sums and Their Applications (1993) [pdf]
by apu on Monday May 26, 2014 @04:15PM
(#7801388)
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.
Re:Prefix Sums and Their Applications (1993) [pdf]
by mturmon on Monday May 26, 2014 @05:41PM
(#7801772)
Yes, "Integral Images" would seem to be the two-dimensional extension of the concept discussed in the OP (but the OP does not go there).
People who studied probability are familiar with the 1-dimensional, 2-dimensional, and the general cases, because they are just cumulative distribution functions and the inclusion-exclusion principle (http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) applied to half-spaces.
> "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."
Re:Prefix Sums and Their Applications (1993) [pdf]
by adolgert on Monday May 26, 2014 @09:42PM
(#7802449)
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.
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 .)
Curious when Micron will put scan units in RAM.
[1] http://en.wikipedia.org/wiki/Integral_image
People who studied probability are familiar with the 1-dimensional, 2-dimensional, and the general cases, because they are just cumulative distribution functions and the inclusion-exclusion principle (http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) applied to half-spaces.
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."
Please let's not build the thread around a triviality, though.
Excellent article nonetheless.