Reduce (Parallel Pattern)

Version	Summary	Created by	Modification	Content Size	Created at	Operation
1	handwiki	Sirius Huang	--	2707	2022-11-30 01:34:43

The content is sourced from: https://handwiki.org/wiki/Reduce_(parallel_pattern)

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 [math]\displaystyle{ \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 Map Reduce, where a function is applied (mapped) to all elements before they are reduced. Other parallel algorithms use reduce as a primary operation to solve more complex problems. The Message Passing Interface implements it in the operations MPI_Reduce and MPI_Allreduce, 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.

parallel programming parallel algorithms collective communication

References

Bar-Noy, Amotz; Kipnis, Shlomo (1994). "Broadcasting multiple messages in simultaneous send/receive systems". Discrete Applied Mathematics 55 (2): 95–105. doi:10.1016/0166-218x(94)90001-9. https://dx.doi.org/10.1016%2F0166-218x%2894%2990001-9
Santos, Eunice E. (2002). "Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines". Journal of Parallel and Distributed Computing 62 (4): 517–543. doi:10.1006/jpdc.2000.1698. https://dx.doi.org/10.1006%2Fjpdc.2000.1698
Slater, P.; Cockayne, E.; Hedetniemi, S. (1981-11-01). "Information Dissemination in Trees". SIAM Journal on Computing 10 (4): 692–701. doi:10.1137/0210052. ISSN 0097-5397. https://dx.doi.org/10.1137%2F0210052
Rabenseifner, Rolf; Träff, Jesper Larsson (2004-09-19) (in en). More Efficient Reduction Algorithms for Non-Power-of-Two Number of Processors in Message-Passing Parallel Systems. Lecture Notes in Computer Science. 3241. Springer, Berlin, Heidelberg. 36–46. doi:10.1007/978-3-540-30218-6_13. ISBN 9783540231639. https://dx.doi.org/10.1007%2F978-3-540-30218-6_13
Bar-Noy, A.; Kipnis, S. (1994-09-01). "Designing broadcasting algorithms in the postal model for message-passing systems" (in en). Mathematical Systems Theory 27 (5): 431–452. doi:10.1007/BF01184933. ISSN 0025-5661. https://dx.doi.org/10.1007%2FBF01184933
Sanders, Peter; Sibeyn, Jop F (2003). "A bandwidth latency tradeoff for broadcast and reduction". Information Processing Letters 86 (1): 33–38. doi:10.1016/s0020-0190(02)00473-8. https://dx.doi.org/10.1016%2Fs0020-0190%2802%2900473-8
Pješivac-Grbović, Jelena; Angskun, Thara; Bosilca, George; Fagg, Graham E.; Gabriel, Edgar; Dongarra, Jack J. (2007-06-01). "Performance analysis of MPI collective operations" (in en). Cluster Computing 10 (2): 127–143. doi:10.1007/s10586-007-0012-0. ISSN 1386-7857. https://dx.doi.org/10.1007%2Fs10586-007-0012-0
Lämmel, Ralf (2008). "Google's MapReduce programming model — Revisited". Science of Computer Programming 70 (1): 1–30. doi:10.1016/j.scico.2007.07.001. https://dx.doi.org/10.1016%2Fj.scico.2007.07.001
Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar A. C.; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício A.B. (2016-06-10). "BSP cost and scalability analysis for MapReduce operations" (in en). Concurrency and Computation: Practice and Experience 28 (8): 2503–2527. doi:10.1002/cpe.3628. ISSN 1532-0634. https://dx.doi.org/10.1002%2Fcpe.3628
Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2014-10-24). "Practical Massively Parallel Sorting". arXiv:1410.6754 [cs.DS]. //arxiv.org/archive/cs.DS

©Text is available under the terms and conditions of the Creative Commons-Attribution ShareAlike (CC BY-SA) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.

Upload a video for this entry

Information

Subjects: Computer Science, Theory & Methods

Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :

HandWiki

View Times: 2.4K

Entry Collection: HandWiki

Update Date: 05 Dec 2022

Table of Contents

Video Upload Options

References