Heterogeneous task scheduling : a survey
Résumé
Scheduling computation tasks on processors is a key issue for high-performance computing. Although a large number of scheduling heuristics have been presented in the literature, most of them target only homogeneous resources. We survey here five low-complexity heuristics for heterogeneous platforms, the Best Imaginary Level (BIL), the Generalized Dynamic Level (GDL), the Critical-Path-on-a-Processor (CPOP), the Heterogeneous Earliest Finish Time (HEFT) and the Partial Completion Time (PCT) algorithms. These five heuristics aim at scheduling directed acyclic weighted task graphs on a bounded number of heterogeneous processors. We compare the performances of the heuristics using four classical testbeds.
Ordonnancer des tâches de calculs sur des processeurs est une nécessité pour du calcul haute performance. Bien qu’un grand nombre d’heuristiques d'ordonnancement existe dans la littérature, la plupart d'entre elles ne visent que des ressources homogènes. Nous présentons ici cinq heuristiques pour des architectures hérogènes : le "Best Imaginary Level" (BIL), le "Generalized Dynamic Level (GDL), le "Critical-Path-on-a-processor (CPOP), le "Heterogeneous Earlisest Finish Time" (HEFT) et le "Partial Completion Times" (PCT). Ces cinq algorithmes ont pour but d'ordonnancer des graphes de tâches acycliques et ^pondérées sur un nombre limité de processeurs kérogènes. Nous comparons les performances de ces heuristiques sur quatre problèmes classiques
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|