Non-clairvoyant reduction algorithms for heterogeneous platforms

Résumé : Nous revisitons le problème classique de la primitive de communication collective de réduction dans le cadre d'un environnement hétérogène. Nous présentons et analysons quatre algorithmes non-clairvoyants, c'est-à-dire qui ne connaissent pas les coûts de calcul et de communication. D'un côté, \bins et \fibo sont des algorithmes statiques qui décident a priori de l'arbre de réduction, sans pouvoir s'adapter à l'environnement au cours de la réduction. D'un autre côté, \dyn et \dynnc sont des algorithmes complètement dynamiques pour les réductions commutatives ou non-commutatives. Lorsque les coûts de calcul sont constants, nous montrons que les algorithmes commutatifs admettent des facteurs d'approximation. Lorsque les coûts de calcul et/ou de communication sont distribués selon une loi exponentielle, nous analysons \dyn à l'aide des chaînes de Markov. Enfin, nous comparons les performances des quatre algorithmes dans un environnement hétérogène à l'aide de simulations.
Type de document :
Rapport
[Research Report] RR-8315, INRIA. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00832102
Contributeur : Equipe Roma <>
Soumis le : mardi 11 juin 2013 - 10:01:27
Dernière modification le : jeudi 15 février 2018 - 08:48:05
Document(s) archivé(s) le : mardi 4 avril 2017 - 19:17:48

Fichier

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

Identifiants

  • HAL Id : hal-00832102, version 3

Citation

Anne Benoit, Louis-Claude Canon, Loris Marchal. Non-clairvoyant reduction algorithms for heterogeneous platforms. [Research Report] RR-8315, INRIA. 2013. 〈hal-00832102v3〉

Partager

Métriques

Consultations de la notice

296

Téléchargements de fichiers

122