Optimal Workload Scheduling Algorithm for Data-Parallel Applications on Heterogeneous Platforms based on Dynamic Programming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2022

Optimal Workload Scheduling Algorithm for Data-Parallel Applications on Heterogeneous Platforms based on Dynamic Programming

Algorithme d’ordonnancement optimal basé sur la programmation dynamique pour les applications aux données parallèles sur des plates-formes hétérogènes

Laércio Lima Pilla

Résumé

This report discusses a new algorithm for makespan minimization on situations where the workload can be partitioned among heterogeneous resources. Without making any assumptions regarding the behavior or shape of the functions giving the execution time on a resource, we are able to provide optimal solutions with a dynamic programming algorithm in O(T^2n) for a workload of T tasks and n heterogeneous resources. This report includes a short state of the art, the problem's model, the algorithm, and its optimality proof.
Ce rapport discute d'un nouvel algorithme pour la minimisation du makespan dans des situations où la charge de travail peut être partitionnée entre des ressources hétérogènes. Sans faire aucune hypothèse sur le comportement ou la forme des fonctions donnant le temps d'exécution sur une ressource, nous sommes capables de fournir des solutions optimales avec un algorithme de programmation dynamique en O(T^2n) pour une charge de travail de T tâches et n ressources hétérogènes. Ce rapport comprend un bref état de l'art, le modèle du problème, l'algorithme, et sa preuve d'optimalité.
Fichier principal
Vignette du fichier
RR-9487.pdf (470.19 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03776372 , version 1 (14-09-2022)
hal-03776372 , version 2 (26-09-2022)

Identifiants

  • HAL Id : hal-03776372 , version 2

Citer

Laércio Lima Pilla. Optimal Workload Scheduling Algorithm for Data-Parallel Applications on Heterogeneous Platforms based on Dynamic Programming. [Research Report] RR-9487, CNRS; LaBRI; Inria; Université de Bordeaux; Bordeaux INP. 2022, pp.1-6. ⟨hal-03776372v2⟩
103 Consultations
55 Téléchargements

Partager

Gmail Facebook X LinkedIn More