Skip to Main content Skip to Navigation

Parallel scheduling of DAGs under memory constraints

Loris Marchal 1 Hanna Nagy 2 Bertrand Simon 1 Frédéric Vivien 1 
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Scientific workflows are frequently modeled as Directed Acyclic Graphs (DAG) of tasks, which represent computational modules and their dependencies, in the form of data produced by a task and used by another one. This formulation allows the use of runtime sys- tems which dynamically allocate tasks onto the resources of increasingly complex and hetero- geneous computing platforms. However, for some workflows, such a dynamic schedule may run out of memory by exposing too much parallelism. This paper focuses on the problem of transforming such a DAG to prevent memory shortage, and concentrates on shared memory platforms. We first propose a simple model of DAG which is expressive enough to emulate com- plex memory behaviors. We then exhibit a polynomial-time algorithm that computes the max- imum peak memory of a DAG, that is, the maximum memory needed by any parallel schedule. We consider the problem of reducing this maximum peak memory to make it smaller than a given bound by adding new fictitious edges, while trying to minimize the critical path of the graph. After proving this problem NP-complete, we provide an ILP solution as well as several heuristic strategies that are thoroughly compared by simulation on synthetic DAGs modeling actual computational workflows. We show that on most instances, we are able to decrease the maximum peak memory at the cost of a small increase in the critical path, thus with little im- pact on quality of the final parallel schedule.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, October 24, 2017 - 6:21:54 PM
Last modification on : Friday, September 30, 2022 - 4:12:17 AM
Long-term archiving on: : Thursday, January 25, 2018 - 2:23:54 PM


Files produced by the author(s)


  • HAL Id : hal-01620255, version 2



Loris Marchal, Hanna Nagy, Bertrand Simon, Frédéric Vivien. Parallel scheduling of DAGs under memory constraints. [Research Report] RR-9108, LIP - ENS Lyon. 2017. ⟨hal-01620255v2⟩



Record views


Files downloads