Show simple item record

Scheduling on Two Types of Resources: a Survey

hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierHigh-End Parallel Algorithms for Challenging Numerical Simulations [HiePACS]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierFranche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) [FEMTO-ST]
dc.contributor.authorCANON, Louis-Claude
hal.structure.identifierUniversité de Bordeaux [UB]
hal.structure.identifierHigh-End Parallel Algorithms for Challenging Numerical Simulations [HiePACS]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierLaboratoire de Conception, Optimisation et Modélisation des Systèmes [LCOMS]
dc.contributor.authorLUCARELLI, Giorgio
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.identifierData Aware Large Scale Computing [DATAMOVE]
dc.contributor.authorMOMMESSIN, Clement
hal.structure.identifierUniversität Bremen [Deutschland] = University of Bremen [Germany] = Université de Brême [Allemagne]
dc.contributor.authorSIMON, Bertrand
hal.structure.identifierData Aware Large Scale Computing [DATAMOVE]
dc.contributor.authorTRYSTRAM, Denis
dc.date.accessioned2024-04-04T02:48:43Z
dc.date.available2024-04-04T02:48:43Z
dc.date.issued2020-05-01
dc.identifier.issn0360-0300
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/191767
dc.description.abstractEnWe study the problem of executing an application represented by a precedence task graph on a parallel machine composed of standard computing cores and accelerators. Contrary to most existing approaches, we distinguish the allocation and the scheduling phases and we mainly focus on the allocation part of the problem: choose the most appropriate type of computing unit for each task. We address both off-line and on-line settings and design generic scheduling approaches. In the first case, we establish strong lower bounds on the worst-case performance of a known approach based on Linear Programming for solving the allocation problem. Then, we refine the scheduling phase and we replace the greedy List Scheduling policy used in this approach by a better ordering of the tasks. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of computing units, achieving an approximation ratio which depends on the number of different types. In the on-line case, we assume that the tasks arrive in any, not known in advance, order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. In this setting, we propose the first on-line scheduling algorithm which takes into account precedences. Our algorithm is based on adequate rules for selecting the type of processor where to allocate the tasks and it achieves a constant factor approximation guarantee if the ratio of the number of CPUs over the number of GPUs is bounded. Finally, all the previous algorithms for hybrid architectures have been experimented on a large number of simulations built on actual libraries. These simulations assess the good practical behavior of the algorithms with respect to the state-of-the-art solutions, whenever these exist, or baseline algorithms.
dc.description.sponsorshipMIAI @ Grenoble Alpes - ANR-19-P3IA-0003
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.title.enScheduling on Two Types of Resources: a Survey
dc.typeArticle de revue
dc.identifier.doi10.1145/3387110
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalACM Computing Surveys
bordeaux.volume53
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-02432381
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-02432381v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=ACM%20Computing%20Surveys&rft.date=2020-05-01&rft.volume=53&rft.issue=3&rft.eissn=0360-0300&rft.issn=0360-0300&rft.au=BEAUMONT,%20Olivier&CANON,%20Louis-Claude&EYRAUD-DUBOIS,%20Lionel&LUCARELLI,%20Giorgio&MARCHAL,%20Loris&rft.genre=article


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record