Afficher la notice abrégée

Centralized Versus Distributed Schedulers for Multiple Bag-of-Tasks Applications

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.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.identifierMiddleware efficiently scalable [MESCAL]
dc.contributor.authorLEGRAND, Arnaud
hal.structure.identifierAlgorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorMARCHAL, Loris
hal.structure.identifierAlgorithms and Scheduling for Distributed Heterogeneous Platforms [GRAAL]
dc.contributor.authorROBERT, Yves
dc.date.accessioned2024-04-15T09:44:00Z
dc.date.available2024-04-15T09:44:00Z
dc.date.issued2008
dc.identifier.issn1045-9219
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197807
dc.description.abstractEnMultiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper we consider the problem of scheduling applications to ensure fair and efficient execution on a distributed network of processors. We limit our study to the case where communication is restricted to a tree embedded in the network, and the applications consist of a large number of independent tasks (Bags of Tasks) that originate at the tree\'s root. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary for different applications. The goal of scheduling is to maximize throughput of each application while ensuring a fair sharing of resources between applications. We can find the optimal asymptotic rates by solving a linear programming problem that expresses all necessary problem constraints, and we show how to construct a periodic schedule from any linear program solution. For single-level trees, the solution is characterized by processing tasks with larger communication-to-computation ratios at children with larger bandwidths. For multi-level trees, this approach requires global knowledge of all application and platform parameters. For large-scale platforms, such global coordination by a centralized scheduler may be unrealistic. Thus, we also investigate decentralized schedulers that use only local information at each participating resource. We assess their performance via simulation, and compare to an optimal centralized solution obtained via linear programming. The best of our decentralized heuristics achieves the same performance on about two-thirds of our test cases, but is far worse in a few cases. While our results are based on simple assumptions and do not explore all parameters (such as the maximum number of tasks that can be held on a node), they provide insight into the important question of fairly and optimally scheduling heterogeneous applications on heterogeneous grids.
dc.description.sponsorshipALgorithmique des Plates-formes A Grande Echelle - ANR-05-MMSA-0006
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.title.enCentralized Versus Distributed Schedulers for Multiple Bag-of-Tasks Applications
dc.typeArticle de revue
dc.identifier.doi10.1109/TPDS.2007.70747
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalIEEE Transactions on Parallel and Distributed Systems
bordeaux.page698―709
bordeaux.volume19
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00789424
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00789424v1
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=2008&rft.volume=19&rft.spage=698%E2%80%95709&rft.epage=698%E2%80%95709&rft.eissn=1045-9219&rft.issn=1045-9219&rft.au=BEAUMONT,%20Olivier&CARTER,%20Larry&FERRANTE,%20Jeanne&LEGRAND,%20Arnaud&MARCHAL,%20Loris&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