Heterogeneous task scheduling : a survey

Vincent Boudet (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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

Mots clés: Different-Speed Processors; Heterogeneous Platforms; High-Performance; Mapping; Scheduling; Task Graphs

Mots clés: Processeurs de vitesses différentes; Distriibution; Ordonnancement; Graphes de tâches; calcul haute perfoamance; Plateforme hétérogène

Domaines: Informatique [cs]

Vincent Boudet. Heterogeneous task scheduling : a survey. [Research Report] LIP RR-2001-*07, Laboratoire de l'informatique du parallélisme. 2001, 2+28p. ⟨hal-02101844⟩