0
$\begingroup$

Prefix Sums and Their Applications states that

The all-prefix-sums operation takes a binary associative operator ⊕, and an ordered set of n elements...

Why is associativity a required property of the prefix sum operation? If a prefix sum is only ever calculated by scanning the set from left to right, why is associativity needed?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You don't need the associativity to define the problem but you need the associativity for the known efficient algorithms. $\endgroup$
    – Louis
    Feb 17 at 9:03
  • 1
    $\begingroup$ The whole point of the article is how to compute the prefix sums efficiently in parallel. This most certainly won’t evaluate the operation by “scanning the set from left to right”. The particular sums will likely end up being evaluated as if they were bracketed in some sort of balanced binary tree whose exact shape will likely not be easy to define, and sums of different prefixes (even differing just by one element) will likely get evaluated by quite different trees, bearing no simple relationship to each other. Hence the result will be essentially useless for a non-associative operation. $\endgroup$
    – Emil Jeřábek
    Feb 17 at 13:01
  • $\begingroup$ As @EmilJeřábek points out: prefix scan is a fundamental parallel computing primitive, and associativity lets you vary the evaluation order for performance. $\endgroup$
    – Martin Berger
    Feb 17 at 14:53
  • $\begingroup$ Okay, my confusion was whether the associativity requirement was only for parallel/efficient implementations, or also for defining the general class of problems. I didn't see why associativity would be required for sequential/left-to-right scan implementations. $\endgroup$
    – djlovesupr3me
    Feb 17 at 19:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.