Afficher la notice abrégée

Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBANINO, Cyril
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithms and high performance computing for grand challenge applications [SCALAPPLIX]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierDepartment of Computer Science and Engineering [Univ California San Diego] [CSE - UC San Diego]
dc.contributor.authorCARTER, Larry
hal.structure.identifierDepartment of Computer Science and Engineering [Univ California San Diego] [CSE - UC San Diego]
dc.contributor.authorFERRANTE, Jeanne
hal.structure.identifierAlgorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
dc.contributor.authorLEGRAND, Arnaud
hal.structure.identifierRegularity and massive parallel computing [REMAP]
dc.contributor.authorROBERT, Yves
dc.date.accessioned2024-04-15T09:43:58Z
dc.date.available2024-04-15T09:43:58Z
dc.date.issued2004
dc.identifier.issn1045-9219
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197806
dc.description.abstractEnWe consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous computing platform. We use a nonoriented graph to model the platform, where resources can have different speeds of computation and communication. Because the number of tasks is large, we focus on the question of determining the optimal steady state scheduling strategy for each processor (the fraction of time spent computing and the fraction of time spent communicating with each neighbor). In contrast to minimizing the total execution time, which is NP-hard in most formulations, we show that finding the optimal steady state can be solved using a linear programming approach and, thus, in polynomial time. Our result holds for a quite general framework, allowing for cycles and multiple paths in the interconnection graph, and allowing for several masters. We also consider the simpler case where the platform is a tree. While this case can also be solved via linear programming, we show how to derive a closed-form formula to compute the optimal steady state, which gives rise to a bandwidth-centric scheduling strategy. The advantage of this approach is that it can directly support autonomous task scheduling based only on information local to each node; no global information is needed. Finally, we provide a theoretical comparison of the computing power of tree-based versus arbitrary platforms.
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.title.enScheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms
dc.typeArticle de revue
dc.identifier.doi10.1109/TPDS.2004.1271181
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalIEEE Transactions on Parallel and Distributed Systems
bordeaux.page319―330
bordeaux.volume15
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00789427
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00789427v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=IEEE%20Transactions%20on%20Parallel%20and%20Distributed%20Systems&rft.date=2004&rft.volume=15&rft.spage=319%E2%80%95330&rft.epage=319%E2%80%95330&rft.eissn=1045-9219&rft.issn=1045-9219&rft.au=BANINO,%20Cyril&BEAUMONT,%20Olivier&CARTER,%20Larry&FERRANTE,%20Jeanne&LEGRAND,%20Arnaud&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