Scheduling Associative Reductions with Homogeneous Costs when Overlapping Communications and Computations

Louis-Claude Canon 1 Gabriel Antoniu 1
1 KerData - Scalable Storage for Clouds and Beyond
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Résumé : L'opération de réduction est centrale au calcul parallèle. Optimiser son coût peut avoir un fort impact sur le temps d'exécution d'une application, en particulier dans le cas de MPI ou de MapReduce. Dans ce rapport, nous proposons une solution optimale pour ordonnancer des réductions associatives. Nous considérons que les communications et les calculs peuvent se recouvrir afin d'exploiter pleinement les ressources. Notre algorithme construit gloutonnement un arbre couvrant en commençant par le puits et en rajoutant un parent à chaque itération. Des bornes sur les temps d'exécution d'ordonnancements optimaux sont ensuite caractérisées. Pour montrer l'extensibilité de l'algorithme, nous l'adaptons à des variations du modèles dans lesquelles les communications ou les calculs sont limités. D'autre part, nous étudions deux arbres couvrants spécifiques: tandis que l'arbre binomial est optimal lorsqu'il n'y a soit aucun calcul, soit aucune communication, l'arbre de Fibonacci est optimal lorsque les temps de transfert et les temps de calcul sont égaux. Finalement, les facteurs d'approximation des stratégies dérivées de ces arbres sont déterminés.
Type de document :
Rapport
[Research Report] RR-7898, INRIA. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00675964
Contributeur : Louis-Claude Canon <>
Soumis le : vendredi 2 mars 2012 - 14:38:15
Dernière modification le : mardi 16 janvier 2018 - 15:54:18
Document(s) archivé(s) le : vendredi 23 novembre 2012 - 15:31:12

Fichier

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

Identifiants

  • HAL Id : hal-00675964, version 1

Citation

Louis-Claude Canon, Gabriel Antoniu. Scheduling Associative Reductions with Homogeneous Costs when Overlapping Communications and Computations. [Research Report] RR-7898, INRIA. 2012. 〈hal-00675964〉

Partager

Métriques

Consultations de la notice

303

Téléchargements de fichiers

240