On Characterizing the Data Movement Complexity of Computational DAGs for Parallel Execution

Résumé : Avec les technologies actuelles, le coût d'une communication (autant en terme de temps que d'énergie) devient de plus en plus dominant face au coût de calcul. Le ratio entre bande passante et puissance de calcul ("machine balance parameter" en anglais) dans les systèmes parallèles ne fait que décroître. Il est donc fondamental de savoir caractériser la complexité d'une application en terme de nombre de mouvements de données minimal. Cet article développe une extension du jeu des pions rouges et noirs ("red-blue pebble game") afin de dériver des bornes inférieures sur la complexité de communication d'un graphe de tâches acyclique (CDAG) dans un environnement de calcul distribué. Les systèmes modélisés à cet effet sont des multi-coeurs à mémoire distribuées, ainsi que des multi-coeurs à mémoire partagée. Les techniques développées s'appliquent à des CDAG non homogènes. Nous illustrons la méthodologie à travers l'analyse de CDAGs de plusieurs algorithmes, dérivant ainsi des bornes inférieures sur leur complexité de communication sur machines distribuées.
Type de document :
Rapport
[Research Report] RR-8522, INRIA. 2014, pp.27
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00980580
Contributeur : Fabrice Rastello <>
Soumis le : vendredi 18 avril 2014 - 11:59:37
Dernière modification le : jeudi 11 janvier 2018 - 06:27:21
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:27:02

Fichiers

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

Identifiants

  • HAL Id : hal-00980580, version 1
  • ARXIV : 1404.4767

Citation

Venmugil Elango, Fabrice Rastello, Louis-Noël Pouchet, J. Ramanujam, P. Sadayappan. On Characterizing the Data Movement Complexity of Computational DAGs for Parallel Execution. [Research Report] RR-8522, INRIA. 2014, pp.27. 〈hal-00980580〉

Partager

Métriques

Consultations de la notice

306

Téléchargements de fichiers

152