Partitioning tree-shaped task graphs for distributed platforms with limited memory - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue IEEE Transactions on Parallel and Distributed Systems Année : 2020

Partitioning tree-shaped task graphs for distributed platforms with limited memory

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. The present paper considers the parallel processing of such a tree and studies how to partition it 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 (i.e., it must fit in memory), and the goal is to minimize the total resulting processing time. We prove that this problem is NP-complete, and we design polynomial-time heuristics to address it. An extensive set of simulations demonstrates the usefulness of these heuristics.
Fichier principal
Vignette du fichier
TPDS.pdf (2.72 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03024579 , version 1 (25-11-2020)

Identifiants

Citer

Changjiang Gou, Anne Benoit, Loris Marchal. Partitioning tree-shaped task graphs for distributed platforms with limited memory. IEEE Transactions on Parallel and Distributed Systems, 2020, 31 (7), pp.1533 - 1544. ⟨10.1109/TPDS.2020.2971200⟩. ⟨hal-03024579⟩
30 Consultations
141 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More