Reduce (parallel pattern): Difference between revisions

Revision as of 01:39, 6 April 2018

Revision as of 05:20, 4 May 2018

Line 1:

{{AFC submission|||ts=20180328143408|u=Flogr|ns=118}}

{{AFC comment|1=Since the scope seems to be solely the use of reduce in parallel programming, then the title should reflect that more clearly, for example by being called Reduce (parallel pattern) in analogy to [[Map (parallel pattern)]]. [[User:Rolf h nelson|Rolf H Nelson]] ([[User talk:Rolf h nelson|talk]]) 05:20, 4 May 2018 (UTC)}}

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|parallel algorithms]] 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.