Minimizing I/Os in Out-of-Core Task Tree Scheduling

Résumé : Les applications de calcul scientifique sont souvent décrites comme des graphes de tâches dirigés et acycliques, où les noeuds représentent les tâches et les arêtes représentent les dépendances entre tâches. Pour certaines applications, comme les méthodes multifrontales de factorisation de matrices creuses, le graphe correspondant est un arbre: chaque tâche produit un unique fichier de données en sortie qui est utilisé par une unique tâche (son père dans l’arbre). On s’intéresse ici dans le cas où les fichiers de données manipulés par les tâches sont de grande taille, ce qui est en particulier le cas dans les méthodes multifrontales. Pour traiter une tâche, ses fichiers d’entrée et de sortie doivent se trouver dans la mémoire principale. De plus, les fichiers de sortie doivent être stockés entre leur création et leur utilisation par la tâche père. Il peut donc arriver que, durant une exécution, la mémoire disponible soit inférieure à la mémoire minimum requise pour traiter l’arbre complet.Dans ce cas, certaines données doivent être temporairement transférées sur un disque pour être lues ultérieurement. Ces opérations d’Entrées/Sorties (E/S ou I/O en anglais) sont très coûteuses, d’où le besoin de les minimiser. Nous revisitons dans cet article ce problème ouvert. Plus précisément, notre objectif est de minimiser le volume total d’Entrées/Sorties effectuées en traitant un arbre de tâche donné. Nous commençons par formaliser et généraliser des résultats connus, puis nous prouvons que les solutions existantes peuvent être arbitrairement loin de l’optimal. Finalement, nous proposons une nouvelle heuristique, basée sur le parcours d’arbre minimisant l’utilisation mémoire. Nous établissons les bonnes performances de cette heuristique à travers des simulations sur des arbres synthétiques ainsi que des arbres réalistes construits à partir de matrices creuses réelles.
Type de document :
Rapport
[Research Report] RR-9025, INRIA. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01462213
Contributeur : Frédéric Vivien <>
Soumis le : mercredi 8 février 2017 - 17:26:45
Dernière modification le : mardi 16 janvier 2018 - 15:36:01
Document(s) archivé(s) le : mardi 9 mai 2017 - 13:51:43

Fichier

INRIA-9025.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01462213, version 1

Collections

Citation

Loris Marchal, Samuel Mccauley, Bertrand Simon, Frédéric Vivien. Minimizing I/Os in Out-of-Core Task Tree Scheduling. [Research Report] RR-9025, INRIA. 2017. 〈hal-01462213〉

Partager

Métriques

Consultations de la notice

402

Téléchargements de fichiers

34