Reduction operator

A reduction operator can help break down a task into various partial tasks by calculating partial results which can be used to obtain a final result. It allows certain serial operations to be performed in parallel and the number of steps required for those operations to be reduced. A reduction operator stores the result of the partial tasks into a private copy of the variable. These private copies are then merged into a shared copy at the end.

An operator is a reduction operator if:

• It can reduce an array to a single scalar value.
• The final result should be obtainable from the results of the partial tasks that were created.

These two requirements are satisfied for commutative and associative operators that are applied to all array elements.

Some operators which satisfy these requirements are addition, multiplication, and some logical operators (and, or, etc.).

A reduction operator $\backslash oplus$ can be applied in constant time on an input set $$V\; =\; \backslash left\backslash \{v\_0\; =\; \backslash begin\{pmatrix\}\; e\_0^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_0^\{m-1\}\backslash end\{pmatrix\},\; v\_1\; =\; \backslash begin\{pmatrix\}\; e\_1^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_1^\{m-1\}\backslash end\{pmatrix\},\; \backslash dots,\; v\_\{p-1\}\; =\; \backslash begin\{pmatrix\}\; e\_\{p-1\}^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_\{p-1\}^\{m-1\}\backslash end\{pmatrix\}\backslash right\backslash \}$$of $p$ vectors with $m$ elements each. The result $r$ of the operation is the combination of the elements $$r\; =\; \backslash begin\{pmatrix\}\; e\_0^0\; \backslash oplus\; e\_1^0\; \backslash oplus\; \backslash dots\; \backslash oplus\; e\_\{p-1\}^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_0^\{m-1\}\; \backslash oplus\; e\_1^\{m-1\}\; \backslash oplus\; \backslash dots\; \backslash oplus\; e\_\{p-1\}^\{m-1\}\backslash end\{pmatrix\}\; =\; \backslash begin\{pmatrix\}\; \backslash bigoplus\_\{i=0\}^\{p-1\}\; e\_i^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; \backslash bigoplus\_\{i=0\}^\{p-1\}\; e\_i^\{m-1\}\; \backslash end\{pmatrix\}$$and has to be stored at a specified root processor at the end of the execution. If the result $r$ has to be available at every processor after the computation has finished, it is often called Allreduce. An optimal sequential linear-time algorithm for reduction can apply the operator successively from front to back, always replacing two vectors with the result of the operation applied to all its elements, thus creating an instance that has one vector less. It needs $(p-1)\backslash cdot\; m$ steps until only $r$ is left. Sequential algorithms can not perform better than linear time, but parallel algorithms leave some space left to optimize.

Suppose we have an array $[2,\; 3,\; 5,\; 1,\; 7,\; 6,\; 8,\; 4]$. The sum of this array can be computed serially by sequentially reducing the array into a single sum using the '+' operator. Starting the summation from the beginning of the array yields:

$$\backslash Bigg(\; \backslash bigg(\; \backslash Big(\; \backslash big(\backslash ,\; (\backslash ,\; (2\; +\; 3)\; +\; 5\; )\; +\; 1\; \backslash big)\; +\; 7\backslash Big)\; +\; 6\; \backslash bigg)\; +\; 8\backslash Bigg)\; +\; 4\; =\; 36.$$Since '+' is both commutative and associative, it is a reduction operator. Therefore this reduction can be performed in parallel using several cores, where each core computes the sum of a subset of the array, and the reduction operator merges the results. Using a binary tree reduction would allow 4 cores to compute $(2\; +\; 3)$, $(5\; +\; 1)$, $(7\; +\; 6)$, and $(8\; +\; 4)$. Then two cores can compute $(5\; +\; 6)$ and $(13\; +\; 12)$, and lastly a single core computes $(11\; +\; 25)\; =\; 36$. So a total of 4 cores can be used to compute the sum in $\backslash log\_\{2\}8\; =\; 3$ steps instead of the $7$ steps required for the serial version. This parallel binary tree technique computes $\backslash big(\backslash ,(2\; +\; 3)\; +\; (5\; +\; 1)\backslash ,\backslash big)\; +\; \backslash big(\backslash ,(7\; +\; 6)\; +\; (8\; +\; 4)\backslash ,\backslash big)$. Of course the result is the same, but only because of the associativity of the reduction operator. The commutativity of the reduction operator would be important if there were a master core distributing work to several processors, since then the results could arrive back to the master processor in any order. The property of commutativity guarantees that the result will be the same.

IEEE 754-2019 defines 4 kinds of sum reductions and 3 kinds of scaled-product reductions. Because the operations are reduction operators, the standards specifies that "implementations may associate in any order or evaluate in any wider format."{{Cite book |title=IEEE Standard for Floating-Point Arithmetic |series=IEEE STD 754-2019 |pages=1–84 |author=IEEE Computer Society |date=22 July 2019 |publisher=IEEE |id=IEEE Std 754-2019 |doi=10.1109/IEEESTD.2019.8766229 |isbn=978-1-5044-5924-2 |ref=CITEREFIEEE_7542019|chapter=9.4 Reduction operations}}

Matrix multiplication is not a reduction operator since the operation is not commutative. If processes were allowed to return their matrix multiplication results in any order to the master process, the final result that the master computes will likely be incorrect if the results arrived out of order. However, note that matrix multiplication is associative, and therefore the result would be correct as long as the proper ordering were enforced, as in the binary tree reduction technique.

Regarding parallel algorithms, there are two main models of parallel computation, the parallel random access machine (PRAM) 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. Both models have different implications for the time-complexity, therefore two algorithms will be shown.

This algorithm represents a widely spread method to handle inputs where $p$ is a power of two. The reverse procedure is often used for broadcasting elements.{{Cite journal|last1=Bar-Noy|first1=Amotz|last2=Kipnis|first2=Shlomo|title=Broadcasting multiple messages in simultaneous send/receive systems|journal=Discrete Applied Mathematics|volume=55|issue=2|pages=95–105|doi=10.1016/0166-218x(94)90001-9|year=1994|doi-access=}}{{Cite journal|last=Santos|first=Eunice E.|author-link=Eunice Santos|title=Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines|journal=Journal of Parallel and Distributed Computing|volume=62|issue=4|pages=517–543|doi=10.1006/jpdc.2000.1698|year=2002}}{{Cite journal|last1=Slater|first1=P.|last2=Cockayne|first2=E.|last3=Hedetniemi|first3=S.|date=1981-11-01|title=Information Dissemination in Trees|journal=SIAM Journal on Computing|volume=10|issue=4|pages=692–701|doi=10.1137/0210052|issn=0097-5397}}[[File:Binomial tree.gif|thumb|436x436px|

Visualization of the algorithm with p = 8, m = 1, and addition as the reduction operator

]]

: for $k\; \backslash gets\; 0$ to $\backslash lceil\backslash log\_2\; p\backslash rceil\; -\; 1$ do

:: for $i\; \backslash gets\; 0$ to $p\; -\; 1$ do in parallel

::: if $p\_i$ is active then

:::: if bit $k$ of $i$ is set then

::::: set $p\_i$ to inactive

:::: else if

::::: $x\_i\; \backslash gets\; x\_i\; \backslash oplus^\{\backslash star\}\; x\_\{i+2^k\}$

The binary operator for vectors is defined element-wise such that $$\backslash begin\{pmatrix\}\; e\_i^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_i^\{m-1\}\backslash end\{pmatrix\}\; \backslash oplus^\backslash star\; \backslash begin\{pmatrix\}\; e\_j^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_j^\{m-1\}\backslash end\{pmatrix\}\; =\; \backslash begin\{pmatrix\}\; e\_i^0\; \backslash oplus\; e\_j^0\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; e\_i^\{m-1\}\; \backslash oplus\; e\_j^\{m-1\}\; \backslash end\{pmatrix\}.$$

The algorithm further assumes that in the beginning $x\_i\; =\; v\_i$ for all $i$ and $p$ is a power of two and uses the processing units $p\_0,\; p\_1,\backslash dots\; p\_\{n-1\}$. In every iteration, half of the processing units become inactive and do not contribute to further computations. The figure shows a visualization of the algorithm using addition as the operator. Vertical lines represent the processing units where the computation of the elements on that line take place. The eight input elements are located on the bottom and every animation step corresponds to one parallel step in the execution of the algorithm. An active processor $p\_i$ evaluates the given operator on the element $x\_i$ it is currently holding and $x\_j$ where $j$ is the minimal index fulfilling $j\; >\; i$, so that $p\_j$ is becoming an inactive processor in the current step. $x\_i$ and $x\_j$ are not necessarily elements of the input set $X$ as the fields are overwritten and reused for previously evaluated expressions. To coordinate the roles of the processing units in each step without causing additional communication between them, the fact that the processing units are indexed with numbers from $0$ to $p-1$ is used. Each processor looks at its $k$-th least significant bit and decides whether to get inactive or compute the operator on its own element and the element with the index where the $k$-th bit is not set. The underlying communication pattern of the algorithm is a binomial tree, hence the name of the algorithm.

Only $p\_0$ holds the result in the end, therefore it is the root processor. For an Allreduce operation the result has to be distributed, which can be done by appending a broadcast from $p\_0$. Furthermore, the number $p$ of processors is restricted to be a power of two. This can be lifted by padding the number of processors to the next power of two. There are also algorithms that are more tailored for this use-case.{{Cite book|last1=Rabenseifner|first1=Rolf|last2=Träff|first2=Jesper Larsson|title=Recent Advances in Parallel Virtual Machine and Message Passing Interface |chapter=More Efficient Reduction Algorithms for Non-Power-of-Two Number of Processors in Message-Passing Parallel Systems |date=2004-09-19|volume=3241|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=36–46|doi=10.1007/978-3-540-30218-6_13|isbn=9783540231639}}

The main loop is executed $\backslash lceil\backslash log\_2\; p\backslash rceil$ times, the time needed for the part done in parallel is in $\backslash mathcal\{O\}(m)$ as a processing unit either combines two vectors or becomes inactive. Thus the parallel time $T(p,\; m)$ for the PRAM is $T(p,\; m)\; =\; \backslash mathcal\{O\}(\backslash log(p)\; \backslash cdot\; m)$. The strategy for handling read and write conflicts can be chosen as restrictive as an exclusive read and exclusive write (EREW). The speedup $S(p,\; m)$ of the algorithm is $S(p,\; m)\; \backslash in\; \backslash mathcal\{O\}\backslash left(\backslash frac\{T\_\backslash text\{seq\}\}\{T(p,\; m)\}\backslash right)\; =\; \backslash mathcal\{O\}\backslash left(\backslash frac\{p\}\{\backslash log(p)\}\backslash right)$ and therefore the efficiency is $E(p,\; m)\; \backslash in\; \backslash mathcal\{O\}\backslash left(\backslash frac\{S(p,\; m)\}\{p\}\backslash right)\; =\; \backslash mathcal\{O\}\backslash left(\backslash frac\{1\}\{\backslash log(p)\}\backslash right)$. The efficiency suffers because half of the active processing units become inactive after each step, so $\backslash frac\{p\}\{2^i\}$ units are active in step $i$.

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 processing units. Therefore, data has to be exchanged explicitly between units, as can be seen in the following algorithm.

: for $k\; \backslash gets\; 0$ to $\backslash lceil\backslash log\_2\; p\backslash rceil\; -\; 1$ do

:: for $i\; \backslash gets\; 0$ to $p\; -\; 1$ do in parallel

::: if $p\_i$ is active then

:::: if bit $k$ of $i$ is set then

::::: send $x\_i$ to $p\_\{i-2^k\}$

::::: set $p\_k$ to inactive

:::: else if

::::: receive $x\_\{i+2^k\}$

::::: $x\_i\; \backslash gets\; x\_i\; \backslash oplus^\backslash star\; x\_\{i+2^k\}$

The only difference between the distributed algorithm and the PRAM version is the inclusion of explicit communication primitives, the operating principle stays the same.

The communication between units leads to some overhead. A simple analysis for the algorithm uses the BSP-model and incorporates the time $T\_\backslash text\{start\}$ needed to initiate communication and $T\_\backslash text\{byte\}$ the time needed to send a byte. Then the resulting runtime is $\backslash Theta((T\_\backslash text\{start\}\; +\; n\; \backslash cdot\; T\_\backslash text\{byte\})\backslash cdot\; log(p))$, as $m$ elements of a vector are sent in each iteration and have size $n$ in total.

File:Pipeline reduce.gifFor distributed memory models, it can make sense to use pipelined communication. This is especially the case when $T\_\backslash text\{start\}$ is small in comparison to $T\_\backslash text\{byte\}$. Usually, linear pipelines split data or a tasks into smaller pieces and process them in stages. In contrast to the binomial tree algorithms, the pipelined algorithm uses the fact that the vectors are not inseparable, but the operator can be evaluated for single elements:{{Cite journal|last1=Bar-Noy|first1=A.|last2=Kipnis|first2=S.|date=1994-09-01|title=Designing broadcasting algorithms in the postal model for message-passing systems|journal=Mathematical Systems Theory|language=en|volume=27|issue=5|pages=431–452|doi=10.1007/BF01184933|issn=0025-5661|citeseerx=10.1.1.54.2543|s2cid=42798826}}

:for $k\; \backslash gets\; 0$ to $p+m-3$ do

:: for $i\; \backslash gets\; 0$ to $p\; -\; 1$ do in parallel

::: if

:::: send $x\_i^\{k-i\}$ to $p\_\{i+1\}$

::: if

:::: receive $x\_\{i-1\}^\{k+i-1\}$ from $p\_\{i-1\}$

:::: $x\_\{i\}^\{k+i-1\}\; \backslash gets\; x\_\{i\}^\{k+i-1\}\; \backslash oplus\; x\_\{i-1\}^\{k+i-1\}$

It is important to note that the send and receive operations have to be executed concurrently for the algorithm to work. The result vector is stored at $p\_\{p-1\}$ at the end. The associated animation shows an execution of the algorithm on vectors of size four with five processing units. Two steps of the animation visualize one parallel execution step.

The number of steps in the parallel execution are $p\; +\; m\; -2$, it takes $p-1$ steps until the last processing unit receives its first element and additional $m-1$ until all elements are received. Therefore, the runtime in the BSP-model is $T(n,\; p,\; m)\; =\; \backslash left(T\_\backslash text\{start\}\; +\; \backslash frac\{n\}\{m\}\; \backslash cdot\; T\_\backslash text\{byte\}\backslash right)(p+m-2)$, assuming that $n$ is the total byte-size of a vector.

Although $m$ has a fixed value, it is possible to logically group elements of a vector together and reduce $m$. For example, a problem instance with vectors of size four can be handled by splitting the vectors into the first two and last two elements, which are always transmitted and computed together. In this case, double the volume is sent each step, but the number of steps has roughly halved. It means that the parameter $m$ is halved, while the total byte-size $n$ stays the same. The runtime $T(p)$ for this approach depends on the value of $m$, which can be optimized if $T\_\backslash text\{start\}$ and $T\_\backslash text\{byte\}$ are known. It is optimal for $m\; =\; \backslash sqrt\{\backslash frac\{n\; \backslash cdot\; (p-2)\backslash cdot\; T\_\backslash text\{byte\}\}\{T\_\backslash text\{start\}\}\}$, assuming that this results in a smaller $m$ that divides the original one.

Reduction is one of the main collective operations implemented in the Message Passing Interface, where performance of the used algorithm is important and evaluated constantly for different use cases.{{Cite journal|last1=Pješivac-Grbović|first1=Jelena|last2=Angskun|first2=Thara|last3=Bosilca|first3=George|last4=Fagg|first4=Graham E.|last5=Gabriel|first5=Edgar|last6=Dongarra|first6=Jack J.|date=2007-06-01|title=Performance analysis of MPI collective operations|journal=Cluster Computing|language=en|volume=10|issue=2|pages=127–143|doi=10.1007/s10586-007-0012-0|s2cid=2142998|issn=1386-7857|citeseerx=10.1.1.80.3867}}

Operators can be used as parameters for MPI_Reduce and MPI_Allreduce, with the difference that the result is available at one (root) processing unit or all of them.

OpenMP offers a reduction clause for describing how the results from parallel operations are collected together.{{cite web |title=10.9. Reduction — OpenMP Application Programming Interface Examples |url=https://passlab.github.io/Examples/contents/Chap_data_environment/9_Reduction.html |website=passlab.github.io}}

MapReduce relies heavily on efficient reduction algorithms to process big data sets, even on huge clusters.{{Cite journal|last=Lämmel|first=Ralf|title=Google's MapReduce programming model — Revisited|journal=Science of Computer Programming|volume=70|issue=1|pages=1–30|doi=10.1016/j.scico.2007.07.001|year=2008|doi-access=}}{{Cite journal|last1=Senger|first1=Hermes|last2=Gil-Costa|first2=Veronica|last3=Arantes|first3=Luciana|last4=Marcondes|first4=Cesar A. C.|last5=Marín|first5=Mauricio|last6=Sato|first6=Liria M.|last7=da Silva|first7=Fabrício A.B.|date=2016-06-10|title=BSP cost and scalability analysis for MapReduce operations|journal=Concurrency and Computation: Practice and Experience|language=en|volume=28|issue=8|pages=2503–2527|doi=10.1002/cpe.3628|issn=1532-0634|hdl=10533/147670|s2cid=33645927|hdl-access=free}}

Some parallel sorting algorithms use reductions to be able to handle very big data sets.{{Cite arXiv|last1=Axtmann|first1=Michael|last2=Bingmann|first2=Timo|last3=Sanders|first3=Peter|last4=Schulz|first4=Christian|date=2014-10-24|title=Practical Massively Parallel Sorting|eprint=1410.6754|class=cs.DS}}

• Fold (higher-order function)

{{Reflist}}

Category:Parallel computing