Reduce (parallel pattern): Difference between revisions

Revision as of 16:38, 18 March 2019

Revision as of 02:35, 20 March 2019

Line 1:

{{Merge to|Reduction Operator|date=March 2019}}

{{Orphan|date=May 2018}}

'''Reduce''' is a collective communication primitive used in the context of a [[parallel programming model]] to combine multiple vectors into one, using an [[Operator associativity|associative]] [[Binary operation|binary operator]] <math>\oplus</math>. Every vector is present at a distinct processor in the beginning. The goal of the primitive is to apply the operator in the order given by the processor-indices to the vectors until only one is left. The reduction of sets of elements is an integral part of programming models such as [[MapReduce|Map Reduce]], where a [[Function (mathematics)|function]] is applied ([[Map (higher-order function)|mapped]]) to all elements before they are reduced. Other [[parallel algorithm]]s use reduce as a primary operation to solve more complex problems. The [[Message Passing Interface]] implements it in the operations <code>MPI_Reduce</code> and <code>MPI_Allreduce</code>, with the difference that the result is available at one (root) processing unit or all of them. Closely related to reduce is the broadcast operation, which distributes data to all processors. Many reduce algorithms can be used for broadcasting by reverting them and omitting the operator.