Scheduling Series-Parallel Task Graphs to Minimize Peak Memory

Enver Kayaaslan 1, 2 Thomas Lambert 3 Loris Marchal 1, 2 Bora Uçar 1, 2
1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum. In our main variant the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut. There is a known, polynomial time algorithm [Liu, SIAM J. Algebra. Discr., 1987] for the cases where the input graph is a rooted tree. We focus on the variant where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm. Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application. Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications.
Type de document :
Rapport
[Research Report] RR-8975, Inria Grenoble Rhône-Alpes, Université de Grenoble. 2016
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01397299
Contributeur : Equipe Roma <>
Soumis le : mardi 15 novembre 2016 - 16:17:08
Dernière modification le : samedi 21 avril 2018 - 01:27:23
Document(s) archivé(s) le : jeudi 16 mars 2017 - 13:33:09

Fichier

RR-8975.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01397299, version 1

Citation

Enver Kayaaslan, Thomas Lambert, Loris Marchal, Bora Uçar. Scheduling Series-Parallel Task Graphs to Minimize Peak Memory. [Research Report] RR-8975, Inria Grenoble Rhône-Alpes, Université de Grenoble. 2016. 〈hal-01397299〉

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

247