KIT | KIT-Bibliothek | Impressum | Datenschutz

Connecting MapReduce Computations to Realistic Machine Models

Sanders, Peter ORCID iD icon


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