Matching-Based Assignement Strategies for Improving Data Locality of Map Tasks in MapReduce
MARCHAL, Loris
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
See more >
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
MARCHAL, Loris
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
< Reduce
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
Language
en
Rapport
This item was published in
2017-02
English Abstract
MapReduce is a well-know framework for distributing data-processingcomputations onto parallel clusters. In MapReduce, a large computationis broken into small tasks that run in parallel on multiple machines,and scales easily ...Read more >
MapReduce is a well-know framework for distributing data-processingcomputations onto parallel clusters. In MapReduce, a large computationis broken into small tasks that run in parallel on multiple machines,and scales easily to very large clusters of inexpensive commoditycomputers. Before the Map phase, the original dataset is split intodata chunks that are replicated (a constant number of times, usually3) and distributed randomly onto computing nodes. During the Mapphase, local tasks (i.e., tasks whose data chunks are stored locally)are assigned in priority when processors request tasks. In thispaper, we provide the first complete theoretical analysis of datalocality in the Map phase of MapReduce, and more generally, forbag-of-tasks applications that behave like MapReduce. We prove that iftasks are homogeneous (in terms of processing time), as soon as thereplication factor is larger than 2, FindAssignment, a matching basedalgorithm, achieves a quasi-perfect makespan (i.e., optimal up to anadditive constant of one step) using a sophisticated matchingalgorithm. Above result is proved with high probability when thenumber of tasks becomes arbitrarily large, and we therefore complementtheoretical results with simulations that corroborate them even forsmall number of tasks. We also show that the matching-based approachleads to an improvement of data locality during the Map phase andtherefore decreases the amount of communications needed to achieveperfect makespan, compared to the classical MapReduce greedy approach.Read less <
English Keywords
Resource Allocation and Scheduling
Analysis of Randomized Algorithms
Matchings
MapReduce
Balls-into-bins
ANR Project
Solveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007
Origin
Hal imported