Online Scheduling of Sequential Task Graphs on Hybrid Platforms

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}-competitive$ online algorithm [3], where m is the number of CPUs and k the number of GPUs (m≥k). We prove that no online algorithm can have a competitive ratio smaller than $\sqrt{m/k}$. We also study how adding flexibility on task processing, such as task migration or spoliation, or increasing the knowledge of the scheduler by providing it with information on the task graph, influences the lower bound. We provide a $(2\sqrt{m/k}+1)$-competitive algorithm as well as a tunable combination of a system-oriented heuristic and a competitive algorithm; this combination performs well in practice and has a competitive ratio in $Θ(\sqrt{m/k})$. We extend our results to more types of processors. Finally, simulations on different sets of task graphs illustrate how the instance properties impact the performance of the studied algorithms and show that our proposed tunable algorithm performs the best among the online algorithms in almost all cases and has even performance close to an offline algorithm.Les plateformes de calcul modernes comportent souvent des accélérateurs. Nous nous intéressons au problème d’ordonnancement d’applications modélisées par des graphes de tâches, sur de telles plateformes composées de deux types de processeurs, par exemple des CPU et des GPU. On considère que les tâches sont dévoilées dynamiquement, et que l’ordonnanceur ne connaît que les tâches disponibles, i.e., les tâches dont les prédecesseurs ont tous été exécutés. Chaque tâche peut être traitée soit par un CPU soit par un GPU, et les temps de calculs correspondants sont connus. Notre étude étend un précédent algorithme online $4\sqrt{m/k}$-competitif, où m est le nombre de CPU et k le nombre de GPU (m≥k). Nous prouvons qu’aucun algorithme online ne peut avoir un facteur de compétitivité plus petit que $\sqrt{m/k}$. Nous étudions également comment cette borne inférieure est influencée par l’ajout de flexibilité sur le traitement des tâches (migration ou spoliation) ou par une meilleure connaissance du graphe par l’ordonnanceur. Nous fournissons un algorithme $(2\sqrt{m/k}+1)$-compétitif ainsi qu’une combinaison paramètrable avec un algorithme efficace en pratique qui permet d’obtenir un facteur de compétitivité en $Θ(\sqrt{m/k})$. Nous étendons nos résultats pour plus de deux types de processeurs. Enfin, des simulations sur plusieurs ensembles de graphes de tâches illustrent les performances des algorithmes étudié