This document is under construction.

Intent:

Many parallel algorithms involve "reduction operations", in which a collection of objects are "reduced" to a single object by combining them pairwise with a binary operator, usually one that is associative and commutative.

The most general reduction operation serially combines the results of each task. This general approach is usually inefficient and scales poorly with the number of UEs. When the reduction step is calculating (v₀ · v₁ · ... · v_M-1) where · is an associative operator, more efficient approaches can be used, such as a tree-based n log(n) algorithm, as shown in the figure below. Commutativity of · allows the implementation even more freedom and possibly improved performance.

Fortunately, the reduction pattern is so common that many programming environments provide constructs to make this update both simple and efficient, and most of the discussion of this step superfluous.