Afficher la notice abrégée

Scheduling Series-Parallel Task Graphs to Minimize Peak Memory

hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorKAYAASLAN, Enver
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorLAMBERT, Thomas
hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorMARCHAL, Loris
hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorUÇAR, Bora
dc.date.accessioned2024-04-04T03:13:04Z
dc.date.available2024-04-04T03:13:04Z
dc.date.created2016-11
dc.date.issued2016-11
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193923
dc.description.abstractEnWe 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.
dc.description.sponsorshipSolveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007
dc.language.isoen
dc.title.enScheduling Series-Parallel Task Graphs to Minimize Peak Memory
dc.typeRapport
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionInria Grenoble Rhône-Alpes, Université de Grenoble
bordeaux.type.reportrr
hal.identifierhal-01397299
hal.version1
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01397299v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2016-11&rft.au=KAYAASLAN,%20Enver&LAMBERT,%20Thomas&MARCHAL,%20Loris&U%C3%87AR,%20Bora&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée