Skip to Main content Skip to Navigation
Conference papers

Revisiting dynamic DAG scheduling under memory constraints for shared-memory platforms

Gabriel Bathie 1, 2 Loris Marchal 1, 2 Yves Robert 1, 2 Samuel Thibault 3, 4
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 STORM - STatic Optimizations, Runtime Methods
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Abstract : This work focuses on dynamic DAG scheduling under memory constraints. We target a shared-memory platform equipped with p parallel processors. We aim at bounding the maximum amount of memory that may be needed by any schedule using p processors to execute the DAG. We refine the classical model that computes maximum cuts by introducing two types of memory edges in the DAG, black edges for regular precedence constraints and red edges for actual memory consumption during execution. A valid edge cut cannot include more than p red edges. This limitation had never been taken into account in previous works, and dramatically changes the complexity of the problem, which was polynomial and becomes NP-hard. We introduce an Integer Linear Program (ILP) to solve it, together with an efficient heuristic based on rounding the rational solution of the ILP. In addition, we propose an exact polynomial algorithm for series-parallel graphs. We provide an extensive set of experiments, both with randomly-generated graphs and with graphs arising form practical applications, which demonstrate the impact of resource constraints on peak memory usage.
Document type :
Conference papers
Complete list of metadatas
Contributor : Equipe Roma <>
Submitted on : Wednesday, November 25, 2020 - 9:57:59 PM
Last modification on : Wednesday, December 2, 2020 - 2:04:09 PM


Files produced by the author(s)


  • HAL Id : hal-03024626, version 1



Gabriel Bathie, Loris Marchal, Yves Robert, Samuel Thibault. Revisiting dynamic DAG scheduling under memory constraints for shared-memory platforms. IPDPS - 2020 - IEEE International Parallel and Distributed Processing Symposium Workshops, May 2020, New Orleans / Virtual, United States. pp.1-10. ⟨hal-03024626⟩



Record views


Files downloads