Reduce (parallel pattern)

reduce
Reduce is a collective communication primitive used in the context of a parallel programming model to combine multiple vectors into one, using an associative binary operator \oplus.wikipedia
20 Related Articles

MapReduce

map reducemap-reducemap/reduce
The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a function is applied (mapped) to all elements before they are reduced.
A MapReduce program is composed of a map procedure (or method), which performs filtering and sorting (such as sorting students by first name into queues, one queue for each name), and a reduce method, which performs a summary operation (such as counting the number of students in each queue, yielding name frequencies).

Parallel programming model

parallelprogramming modelconcurrency
Reduce is a collective communication primitive used in the context of a parallel programming model to combine multiple vectors into one, using an associative binary operator \oplus.

Operator associativity

right-associativeleft-associativeassociativity
Reduce is a collective communication primitive used in the context of a parallel programming model to combine multiple vectors into one, using an associative binary operator \oplus.

Binary operation

binary operatoroperationbinary
Reduce is a collective communication primitive used in the context of a parallel programming model to combine multiple vectors into one, using an associative binary operator \oplus.

Function (mathematics)

functionfunctionsmathematical function
The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a function is applied (mapped) to all elements before they are reduced.

Map (higher-order function)

map mapped
The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a function is applied (mapped) to all elements before they are reduced.

Parallel algorithm

parallel algorithmsparallelparallelized
Other parallel algorithms use reduce as a primary operation to solve more complex problems.

Message Passing Interface

MPIMessage PassingMessage Passing Interface (MPI)
The Message Passing Interface implements it in the operations and, with the difference that the result is available at one (root) processing unit or all of them.

Associative property

associativeassociativityassociative law
Formally, reduce takes an associative (but not necessarily commutative) operator \oplus, which can be evaluated in constant time and an input set of p vectors with m elements each.

Commutative property

commutativecommutecommutativity
Formally, reduce takes an associative (but not necessarily commutative) operator \oplus, which can be evaluated in constant time and an input set of p vectors with m elements each.

Parallel random-access machine

PRAMparallel random access machineconcurrent random access machine
Regarding parallel algorithms, there are two main models of parallel computation, the parallel random access machine as an extension of the RAM with shared memory between processing units and the bulk synchronous parallel computer which takes communication and synchronization into account.

Bulk synchronous parallel

BSPbulk synchronousbulk synchronous parallel computer
Regarding parallel algorithms, there are two main models of parallel computation, the parallel random access machine as an extension of the RAM with shared memory between processing units and the bulk synchronous parallel computer which takes communication and synchronization into account.

Synchronization (computer science)

synchronizationsynchronoussynchronization primitive
Regarding parallel algorithms, there are two main models of parallel computation, the parallel random access machine as an extension of the RAM with shared memory between processing units and the bulk synchronous parallel computer which takes communication and synchronization into account.

Time complexity

polynomial timelinear timeexponential time
Both models have different implications for the time-complexity, therefore two algorithms will be shown.

Distributed memory

distributeddistributed memory multiprocessingdistributed-memory
In contrast to the PRAM-algorithm, in the distributed memory model memory is not shared between processing units and data has to be exchanged explicitly between units, resulting in communication overhead that is accounted for.

Pipeline (computing)

pipelinepipeliningpipelined
Usually, linear pipelines split data or a task into smaller pieces and process them in stages.

Fibonacci number

Fibonacci sequenceFibonacciFibonacci spiral
Instead of the binomial tree, a Fibonacci tree is used which has the property that the height of the trees rooted at its two children differ by one.

Duplex (telecommunications)

half-duplexfull-duplexduplex
The animation shows the execution of such an algorithm in a full-duplex communication model.

Sorting algorithm

sortingsortsorted
Some parallel sorting algorithms use reductions to be able to handle very big data sets.