Afficher la notice abrégée

Parallel scheduling of task trees with limited memory

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
dc.contributor.authorMARCHAL, Loris
hal.structure.identifierDepartment of Electrical and Computer Engineering [Auckland ] [ECE]
dc.contributor.authorSINNEN, Oliver
hal.structure.identifierOptimisation des ressources : modèles, algorithmes et ordonnancement [ROMA]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorVIVIEN, Frédéric
dc.date.accessioned2024-04-04T03:18:16Z
dc.date.available2024-04-04T03:18:16Z
dc.date.issued2015-07
dc.identifier.issn2329-4949
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194388
dc.description.abstractEnThis 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 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.
dc.description.sponsorshipSolveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.rights.urihttp://creativecommons.org/licenses/by/
dc.subject.enmulti-criteria optimization
dc.subject.enmemory usage
dc.subject.enApproximation algorithms
dc.subject.enscheduling
dc.subject.entask graphs
dc.subject.enpebble-game
dc.title.enParallel scheduling of task trees with limited memory
dc.typeArticle de revue
dc.identifier.doi10.1145/2779052
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalACM Transactions on Parallel Computing
bordeaux.page36
bordeaux.volume2
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-01160118
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01160118v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=ACM%20Transactions%20on%20Parallel%20Computing&rft.date=2015-07&rft.volume=2&rft.issue=2&rft.spage=36&rft.epage=36&rft.eissn=2329-4949&rft.issn=2329-4949&rft.au=EYRAUD-DUBOIS,%20Lionel&MARCHAL,%20Loris&SINNEN,%20Oliver&VIVIEN,%20Fr%C3%A9d%C3%A9ric&rft.genre=article


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