Reduce (parallel pattern): Difference between revisions

Revision as of 13:38, 28 March 2018

Revision as of 14:05, 28 March 2018

Line 1:

The reduction operation is a 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 is to apply the operator in the order given by the processor-indices to the vectors until only one is left. The reduction 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|parallel algorithms]] use the reducereduction operation 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 the reduction is the broadcast operation, which distributes data to all processors. Many reduction algorithms can be used for broadcasting by reverting them and omitting the operator.

== Definition ==