Tree traversals with task-memory affinities

Résumé : Dans ce rapport, nous nous intéressons à la complexité du traitement d'arbres de tâches utilisant de gros fichiers d'entrée et de sortie. Nous nous focalisons sur une architecture hétérogène avec deux types de ressources, utilisant chacune une mémoire spécifique, comme par exemple un noeud multicore équipé d'un accélérateur (FPGA ou GPU). Les tâches de l'arbre sont colorées suivant leur type et peuvent être exécutées si tous leurs fichiers d'entrée et de sortie peuvent être stockés dans la mémoire correspondante. La quantité de mémoire de chaque type utilisée à une étape donnée de l'exécution dépend fortement de l'ordre dans lequel les tâches sont exécutées et du moment où sont effectuées les communications entre les deux mémoires. L'objectif est de déterminer un ordonnancement efficace qui minimise la quantité de mémoire de chaque type nécessaire pour traiter l'arbre entier. Dans ce rapport, nous établissons la complexité de ce problème d'ordonnancement à deux mémoires et nous fournissons des résultats d'inapproximabilité. De plus, nous proposons plusieurs heuristiques, fondées à la fois sur des traversées d'arbres en profondeur et des traversées générales, que nous évaluons sur un ensemble complet d'arbres, comprenant des arbres aléatoires ainsi que des arbres rencontrés dans le domaine de la factorisation de matrices creuses.
Type de document :
Rapport
[Research Report] RR-8226, INRIA. 2013, pp.31
Liste complète des métadonnées

https://hal.inria.fr/hal-00787753
Contributeur : Julien Herrmann <>
Soumis le : vendredi 22 mars 2013 - 17:25:59
Dernière modification le : mardi 16 janvier 2018 - 15:34:23
Document(s) archivé(s) le : lundi 24 juin 2013 - 11:35:24

Fichier

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

Identifiants

  • HAL Id : hal-00787753, version 1

Collections

Citation

Julien Herrmann, Loris Marchal, Yves Robert. Tree traversals with task-memory affinities. [Research Report] RR-8226, INRIA. 2013, pp.31. 〈hal-00787753〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

190