KIT | KIT-Bibliothek | Impressum | Datenschutz

Connecting MapReduce Computations to Realistic Machine Models

Sanders, Peter

Abstract:
We explain how the popular, highly abstract MapReduce model of parallel computation (MRC) can be rooted in reality by explaining how it can be simulated on realistic distributed-memory parallel machine models like BSP. We first refine the model (MRC+) to include parameters for total work w, bottleneck work ŵ , data volume m, and maximum object sizes m̂ . We then show matching upper and lower bounds for executing a MapReduce calculation on the distributed-memory machine -- $\Theta(w/p+\hat{w}+\log p)$ work and $\Theta(m/p+\hat{m}+\log p)$ bottleneck communication volume using p processors.



Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsdatum 18.02.2020
Sprache Englisch
Identifikator KITopen-ID: 1000131832
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page