Data-Locality Aware Dynamic Schedulers for Independent Tasks with Replicated Inputs

Olivier Beaumont 1 Thomas Lambert 1 Loris Marchal 2, 3 Bastien Thomas 4
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper we concentrate on a crucial parameter for efficiency in Big Data and HPC applications: data locality. We focus on the scheduling of a set of independant tasks, each depending on an input file. We assume that each of these input files has been replicated several times and placed in local storage of different nodes of a cluster, similarly of what we can find on HDFS system for example. We consider two optimization problems, related to the two natural metrics: makespan optimization (under the constraint that only local tasks are allowed) and communication optimization (under the constraint of never letting a processor idle in order to optimize makespan). For both problems we investigate the performance of dynamic schedulers, in particular the basic greedy algorithm we can for example find in the default MapReduce scheduler. First we theoretically study its performance, with probabilistic models, and provide a lower bound for communication metric and asymptotic behaviour for both metrics. Second we propose simulations based on traces from a Hadoop cluster to compare the different dynamic schedulers and assess the expected behaviour obtained with the theoretical study.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01878977
Contributor : Olivier Beaumont <>
Submitted on : Friday, September 21, 2018 - 4:38:34 PM
Last modification on : Tuesday, December 11, 2018 - 10:58:09 AM
Long-term archiving on : Saturday, December 22, 2018 - 3:26:00 PM

File

cebda.pdf
Files produced by the author(s)

Identifiers

Citation

Olivier Beaumont, Thomas Lambert, Loris Marchal, Bastien Thomas. Data-Locality Aware Dynamic Schedulers for Independent Tasks with Replicated Inputs. IPDPSW 2018 IEEE International Parallel and Distributed Processing Symposium Workshops, May 2018, Vancouver, Canada. pp.1-8, ⟨10.1109/IPDPSW.2018.00187⟩. ⟨hal-01878977⟩

Share

Metrics

Record views

483

Files downloads

143