Afficher la notice abrégée

Scheduling strategies for master-slave tasking on heterogeneous processor grids

dc.contributor.authorBANINO, Cyril
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierRegularity and massive parallel computing [REMAP]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorLEGRAND, Arnaud
hal.structure.identifierRegularity and massive parallel computing [REMAP]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorROBERT, Yves
dc.date.accessioned2024-04-15T09:43:33Z
dc.date.available2024-04-15T09:43:33Z
dc.date.issued2002
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197774
dc.description.abstractEnIn this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous grid computing platform. We use a non-oriented graph to model a grid, where resources can have different speeds of computation and communication, as well as different overlap capabilities. We show how to determine 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). This result holds for a quite general framework, allowing for cycles and multiple paths in the interconnection graph, and allowing for several masters. Because spanning trees are easier to deal with in practice (there is a single path from the master to each node), a natural question arises: how to extract the best spanning tree, i.e. the one with optimal steady-state throughput, out of a general interconnection graph? We show that this problem is NP-hard. Even worse, we show that there exist heterogeneous networks for which the optimal spanning tree has a throughput which is arbitrarily bad in front of the throughput that can be achieved by the optimal (multiple-path) solution. Still, we introduce and compare several low-complexity heuristics to determine a sub-optimal spanning tree. Fortunately, we observe that the best heuristics do achieve an excellent performance in most experiments.
dc.language.isoen
dc.title.enScheduling strategies for master-slave tasking on heterogeneous processor grids
dc.typeRapport
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.reportrr
hal.identifierhal-00807406
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00807406v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2002&rft.au=BANINO,%20Cyril&BEAUMONT,%20Olivier&LEGRAND,%20Arnaud&ROBERT,%20Yves&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