Reduction operator

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, the reduction operator is a type of operator that is commonly used in parallel programming to reduce the elements of an array into a single result. Reduction operators are associative and often (but not necessarily) commutative. The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a reduction operator is applied (mapped) to all elements before they are reduced. Other parallel algorithms use reduction operators as primary operations to solve more complex problems. Many reduction operators can be used for broadcasting to distribute data to all processors.

In computer science, the reduction operator is a type of operator that is commonly used in parallel programming to reduce the elements of an array into a single result. Reduction operators are associative and often (but not necessarily) commutative. The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a reduction operator is applied (mapped) to all elements before they are reduced. Other parallel algorithms use reduction operators as primary operations to solve more complex problems. Many reduction operators can be used for broadcasting to distribute data to all processors.

Theory

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 \oplus can be applied in constant time on an input set V = \left\{v_0 = \begin{pmatrix} e_0^0 \\ \vdots \\ e_0^{m-1}\end{pmatrix}, v_1 = \begin{pmatrix} e_1^0 \\ \vdots \\ e_1^{m-1}\end{pmatrix}, \dots, v_{p-1} = \begin{pmatrix} e_{p-1}^0 \\ \vdots \\ e_{p-1}^{m-1}\end{pmatrix}\right\} of p vectors with m elements each. The result r of the operation is the combination of the elements r = \begin{pmatrix} e_0^0 \oplus e_1^0 \oplus \dots \oplus e_{p-1}^0 \\ \vdots \\ e_0^{m-1} \oplus e_1^{m-1} \oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix} = \begin{pmatrix} \bigoplus_{i=0}^{p-1} e_i^0 \\ \vdots \\ \bigoplus_{i=0}^{p-1} e_i^{m-1} \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)\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. \Bigg( \bigg( \Big( \big(\, (\, (2 + 3) + 5 ) + 1 \big) + 7\Big) + 6 \bigg) + 8\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 \log_{2}8 = 3 steps instead of the 7 steps required for the serial version. This parallel binary tree technique computes \big(\,(2 + 3) + (5 + 1)\,\big) + \big(\,(7 + 6) + (8 + 4)\,\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." The binary operator for vectors is defined element-wise such that \begin{pmatrix} e_i^0 \\ \vdots \\ e_i^{m-1}\end{pmatrix} \oplus^\star \begin{pmatrix} e_j^0 \\ \vdots \\ e_j^{m-1}\end{pmatrix} = \begin{pmatrix} e_i^0 \oplus e_j^0 \\ \vdots \\ e_i^{m-1} \oplus e_j^{m-1} \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,\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. The main loop is executed \lceil\log_2 p\rceil times, the time needed for the part done in parallel is in \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) = \mathcal{O}(\log(p) \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) \in \mathcal{O}\left(\frac{T_\text{seq}}{T(p, m)}\right) = \mathcal{O}\left(\frac{p}{\log(p)}\right) and therefore the efficiency is E(p, m) \in \mathcal{O}\left(\frac{S(p, m)}{p}\right) = \mathcal{O}\left(\frac{1}{\log(p)}\right) . The efficiency suffers because half of the active processing units become inactive after each step, so \frac{p}{2^i} units are active in step i . 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) = \left(T_\text{start} + \frac{n}{m} \cdot T_\text{byte}\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_\text{start} and T_\text{byte} are known. It is optimal for m = \sqrt{\frac{n \cdot (p-2)\cdot T_\text{byte}}{T_\text{start}}} , assuming that this results in a smaller m that divides the original one.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368108637 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001368108637 · captured 1786061302.0 · version history

Cite this page as: encyclopegia.org, “Reduction operator”, snapshot enwiki-001368108637. https://encyclopegia.org/a/reduction-operator

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.