Prefix Sums and Their Applications¶
Blelloch, G. E. (1990). Prefix Sums and Their Applications.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Monoid
- Parallel and distributed computation. MapReduce combiners, tree aggregation, parallel prefix scans, GPU reductions, sharded counters, and segment trees over an arbitrary monoid all rest on the same entitlements, and all require an explicit zero because the framework, not the programmer, decides how many partitions there are and whether any is empty.
This sourceDefines the all-prefix-sums operation over a binary associative operator, with the exclusive prescan additionally requiring an identity element, so the value of a reduction is independent of how the input is partitioned across processors.
- Parallel and distributed computation. MapReduce combiners, tree aggregation, parallel prefix scans, GPU reductions, sharded counters, and segment trees over an arbitrary monoid all rest on the same entitlements, and all require an explicit zero because the framework, not the programmer, decides how many partitions there are and whether any is empty.
Mechanisms¶
- Tree Reduction
- Its strength is dramatic latency reduction — the logarithmic-depth reduction is the workhorse of parallel and distributed aggregation — while, for an exact operation, leaving the answer untouched no matter which balanced shape is used
This sourceDerives logarithmic-depth tree reduction for associative operations while preserving the exact reduction result under balanced regrouping.
- Its strength is dramatic latency reduction — the logarithmic-depth reduction is the workhorse of parallel and distributed aggregation — while, for an exact operation, leaving the answer untouched no matter which balanced shape is used
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 1 other way.
Registry ID ref:9ff5b18179c1 · see in the full table