Evènement pour le groupe Algorithmique Distribuée


Date 2017-02-27  14:00-15:00
TitreStratégies d’assignation basées sur des couplages pour améliorer la localité dans les opérations de type Map/Reduce 
RésuméMap/Reduce est un paradigme d'algorithme parallèle qui cherche à séparer une tâche en plusieurs sous-tâches de tailles plus réduites afin de les traiter indépendamment et d'agréger ensuite les résultats. Dans cet exposé nous nous intéresserons à la première phase, la phase dite de "Map", c'est à dire le placement de plusieurs tâches indépendantes sur un ensemble de machines. Lors de cette phase, les fichiers d'entrées sont répliqués et pré-placés sur plusieurs processeurs de manière aléatoire afin d'augmenter le nombre de machines susceptible d'exécuter une tâche. Nous voulons ici essayer d'utiliser au mieux cette distribution initiale des fichiers afin de finir l'ensemble des tâches au plus vite (minimisation du makespan). Pour cela nous nous restreignons au cas des tâches homogènes et proposons une modélisation basée sur les graphes bipartis (les arêtes représentent les placement initiaux des fichiers d'entrées). Grâce à un algorithme inspiré des algorithmes de couplage nous montrerons qu'il est possible d’obtenir la solution optimale du problème en temps polynomial. Nous analyserons ensuite la qualité de cette solution en montrons qu'avec forte probabilité elle est au moins quasi-parfaite, c'est à dire égale à l'optimal théorique plus un. Enfin nous conclurons l'exposé sur différents résultats de simulations permettant une analyse du cas où l'on autorise le déplacement des fichiers d'entrées et où l'on cherche à minimiser ces déplacements. 
Lieu178 
OrateurThomas Lambert 



Aucun document lié à cet événement.

Retour
Retour à l'index