HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Parallel scheduling of task trees with limited memory

Lionel Eyraud-Dubois 1, 2 Loris Marchal 3, 4 Oliver Sinnen 5 Frédéric Vivien 3, 4
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
CNRS - Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Université Sciences et Technologies - Bordeaux 1
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents some large data. A task can only be executed if all input and output data fit into memory, and a data can only be removed from memory after the completion of the task that uses it as an input data. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The peak memory needed for the processing of the entire tree depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed. Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the makespan. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide inapproximability results even for unit weight trees. We design a series of practical heuristics achieving different trade-offs between the minimization of peak memory usage and makespan. Some of these heuristics are able to process a tree while keeping the memory usage under a given memory limit. The different heuristics are evaluated in an extensive experimental evaluation using realistic trees.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Wednesday, October 1, 2014 - 10:35:59 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Friday, January 2, 2015 - 10:41:21 AM


Files produced by the author(s)


  • HAL Id : hal-01070356, version 1
  • ARXIV : 1410.0329


Lionel Eyraud-Dubois, Loris Marchal, Oliver Sinnen, Frédéric Vivien. Parallel scheduling of task trees with limited memory. [Research Report] RR-8606, INRIA. 2014, pp.37. ⟨hal-01070356⟩



Record views


Files downloads