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]
Leer más >
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]
< Leer menos
Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
Laboratoire de l'Informatique du Parallélisme [LIP]
Idioma
en
Rapport
Este ítem está publicado en
2017-02
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Palabras clave en inglés
Resource Allocation and Scheduling
Analysis of Randomized Algorithms
Matchings
MapReduce
Balls-into-bins
Proyecto ANR
Solveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007
Orígen
Importado de HalCentros de investigación