Reduce (parallel pattern): Difference between revisions

Revision as of 10:15, 22 March 2018

Revision as of 13:38, 28 March 2018

Line 39:

==== Runtime analysis ====

A simple analysis for the algorithm uses the BSP-model and incorporates the time <math>T_{start}</math> needed to initiate communication and <math>T_{byte}</math> the time needed to send a packet/byte. Then the resulting runtime is <math>\Theta((T_{start} + n \cdot T_{byte})\cdot log(p))</math>, as <math>m</math> elements of a vector are send in each iteration and have size <math>n</math> in total.

== Pipeline-algorithm ==

Line 72:

[[MapReduce]] relies heavily on efficient reduction algorithms to process big data sets, even on huge clusters.<ref>{{Cite journal|last=Lämmel|first=Ralf|title=Google’s MapReduce programming model — Revisited|url=https://doi.org/10.1016/j.scico.2007.07.001|journal=Science of Computer Programming|volume=70|issue=1|pages=1–30|doi=10.1016/j.scico.2007.07.001}}</ref><ref>{{Cite journal|last=Senger|first=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|url=http://onlinelibrary.wiley.com/doi/10.1002/cpe.3628/abstract|journal=Concurrency and Computation: Practice and Experience|language=en|volume=28|issue=8|pages=2503–2527|doi=10.1002/cpe.3628|issn=1532-0634}}</ref>

Some parallel [[Sorting algorithm|sorting]] algorithms use reductions to be able to handle very big data sets.<ref>{{Cite journal|last=Axtmann|first=Michael|last2=Bingmann|first2=Timo|last3=Sanders|first3=Peter|last4=Schulz|first4=Christian|date=2014-10-24|title=Practical Massively Parallel Sorting|url=http://arxiv.org/abs/1410.6754|journal=arXiv:1410.6754 [cs]}}</ref>{{User sandbox}}

<!-- EDIT BELOW THIS LINE -->

== References ==

<references />{{User sandbox}}