Non-Linear Divisible Loads: There is No Free Lunch

Olivier Beaumont 1, 2 Hubert Larchevêque 1, 2 Loris Marchal 3, 4
1 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : L'ordonnancement de tâches divisibles (DLT) a connu beaucoup de développements ces dernières années. Une tâche divisible est une tâche parfaitement parallélisable, qui peut être découpée en un nombre arbitraire de sous-tâches et exécutée en parallèle sur un ensemble de ressources potentiellement hétérogènes. Le succès de cette théorie vient de l'existence de nombreux algorithmes optimaux pour l'allocation et l'ordonnancement de ces tâches, au contraire des problèmes classiques d'ordonnancement qui sont habituellement NP-complets. De plus, on a récemment constaté la proximité de cette théorie, qui pose les bases théoriques de l'ordonnancement de tâches sur plates-formes hétérogènes, avec des solutions logicielles comme MapReduce, qui permettent de déployer des applications sur des plates-formes distribuées à grande échelle. Devant un tel succès, il a été proposé d'étendre ces solutions à des tâches dont la complexité en calcul n'est plus linéaire en la taille des données. Dans ce rapport, nous montrons que l'ordonnancement de tâches divisibles et MapReduce sont tous deux plus adaptés aux tâches de complexité linéaire. En particulier, nous montrons que l'ordonnancement de tâches divisibles ne peut être appliqué aux tâches de complexité quadratique, comme cela a été proposé récemment. Nous précisons les limites des résultats de cette théorie et pour les tâches non linéaires, nous proposes des solutions utilisant sur une préparation minutieuse des données et un partitionnement efficace du calcul. En particulier, par simulation, nous montrons l'impact de cette méthode sur le volume de communications généré par MapReduce sur des algorithmes de produit de matrices et de produit $u^T \times v$ de deux vecteurs.
Type de document :
Rapport
[Research Report] RR-8170, INRIA. 2012, pp.20
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00762008
Contributeur : Loris Marchal <>
Soumis le : jeudi 6 décembre 2012 - 12:13:32
Dernière modification le : samedi 21 avril 2018 - 01:27:09
Document(s) archivé(s) le : samedi 17 décembre 2016 - 21:30:16

Fichier

RR-8170.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00762008, version 1

Citation

Olivier Beaumont, Hubert Larchevêque, Loris Marchal. Non-Linear Divisible Loads: There is No Free Lunch. [Research Report] RR-8170, INRIA. 2012, pp.20. 〈hal-00762008〉

Partager

Métriques

Consultations de la notice

459

Téléchargements de fichiers

158