Memory-aware tree partitioning on homogeneous platforms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2017

Memory-aware tree partitioning on homogeneous platforms

Partitionnement d’arbres de tâches orienté mémoire pour les plates-formes homogènes

Résumé

Scientific applications are commonly modeled as the processing of directed acyclic graphs of tasks, and for some of them, the graph takes the special form of a rooted tree. This tree expresses both the computational dependencies between tasks and their storage requirements. The problem of scheduling/traversing such a tree on a single processor to minimize its memory footprint has already been widely studied. Hence, we move to parallel processing and study how to partition the tree for a homogeneous multiprocessor platform, where each processor is equipped with its own memory. We formally state the problem of partitioning the tree into subtrees such that each subtree can be processed on a single processor and the total resulting processing time is minimized. We prove that the problem is NP-complete, and we design polynomial-time heuristics to address it. An extensive set of simulations demonstrates the usefulness of these heuristics.
Les applications scientifiques sont couramment modélisées par des graphes de tâches. Pour certaines d'entre elles, le graphe prend la forme particulière d'un arbre enraciné". Cet arbre détermine à la fois les dépendance entre tâches de calcul et les besoins en stockage. Le problème d'ordonnancer (ou parcourir) un tel arbre sur un seul processeur pour réduire son empreinte mémoire a déjà largement été étudié. Dans ce rapport, nous considérons le traitement parallèle d'un tel arbre et étudions comment le partitionner pour une plate-forme de calcul formée de processeurs homogènes disposant chacun de sa propre mémoire. Nous formalisons le problème du partitionnement de l'arbre en sous-arbres de telle sorte que chaque sous-arbre puisse être traité sur un seul processeur et que le temps de calcul total soit minimal. Nous montrons que ce problème est NP-complet et proposons des heuristiques polynomiales. Un ensemble exhaustif,de simulations permet de montrer l'utilité de ces heuristiques.
Fichier principal
Vignette du fichier
main.pdf (1.3 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01644352 , version 1 (22-11-2017)
hal-01644352 , version 2 (21-12-2017)
hal-01644352 , version 3 (14-09-2018)
hal-01644352 , version 4 (05-04-2019)

Identifiants

  • HAL Id : hal-01644352 , version 3

Citer

Anne Benoit, Changjiang Gou, Loris Marchal. Memory-aware tree partitioning on homogeneous platforms. [Research Report] RR-9115, Inria Grenoble Rhône-Alpes. 2017, pp.1-25. ⟨hal-01644352v3⟩
342 Consultations
423 Téléchargements

Partager

Gmail Facebook X LinkedIn More