Matching-Based Assignement Strategies for Improving Data Locality of Map Tasks in MapReduce
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | LAMBERT, Thomas | |
| hal.structure.identifier | Optimisation des ressources : modèles, algorithmes et ordonnancement [ROMA] | |
| hal.structure.identifier | Laboratoire de l'Informatique du Parallélisme [LIP] | |
| dc.contributor.author | MARCHAL, Loris | |
| hal.structure.identifier | École normale supérieure - Rennes [ENS Rennes] | |
| dc.contributor.author | THOMAS, Bastien | |
| dc.date.accessioned | 2024-04-04T03:08:23Z | |
| dc.date.available | 2024-04-04T03:08:23Z | |
| dc.date.created | 2017-02 | |
| dc.date.issued | 2017-02 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193525 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Solveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007 | |
| dc.language.iso | en | |
| dc.subject.en | Resource Allocation and Scheduling | |
| dc.subject.en | Analysis of Randomized Algorithms | |
| dc.subject.en | Matchings | |
| dc.subject.en | MapReduce | |
| dc.subject.en | Balls-into-bins | |
| dc.title.en | Matching-Based Assignement Strategies for Improving Data Locality of Map Tasks in MapReduce | |
| dc.type | Rapport | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.type.institution | Inria - Research Centre Grenoble – Rhône-Alpes | |
| bordeaux.type.institution | Inria Bordeaux Sud-Ouest | |
| bordeaux.type.report | rr | |
| hal.identifier | hal-01386539 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01386539v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2017-02&rft.au=BEAUMONT,%20Olivier&LAMBERT,%20Thomas&MARCHAL,%20Loris&THOMAS,%20Bastien&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||