A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2001

A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors

Résumé

Scheduling computational 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. Moreover, these heuristics often rely on a model where the number of processors is bounded but where the communication capabilities of the target architecture are not restricted. In this paper, we deal with a more realistic model for heterogeneous networks of workstations, where each processor can send and/or receive at most one message at any given time-step. First, we state a complexity result that shows that the model is at least as difficult as the standard one. Then, we show how to modify classical list scheduling techniques to cope with the new model. Next we introduce a new scheduling heuristic which incorporates load-balancing criteria into the decision process of scheduling and mapping ready tasks. Experimental results conducted using six classical testbeds: (LAPLACE, LU, STENCIL, FORK-JOIN, DOOLITTLE, and LDMt) show very promising results.
Nous nous intéressons à l'ordonnancement de graphes de tâches avec des ressources de calcul hétérogènes; Nous pensons que le modèle usuel macro-dataflow n'est pas adapté, car les contentions sur les communications ne sont pas prises en compte. Nous proposons d'utiliser plutôt le modèle one-port, où un processeur donnée peut envoyer/recevoir un seul message à tout instant. Ce modèle s'avère aussi difficile que le modèle usuel : l'ordonnancement d'un simple graphe fork est prouvé NP-complet. Nous montrons comment adapter les heuristiques de liste classiques au modèle one-port. Enfin, nous proposons une nouvelle heuristique, dont la caractéristique principale est de traite un ensemble de tâches prêtes ( plutôt qu'une seule) simultanément : le but est d'assurer un meilleur équilibrage de charge et de minimiser les communications.
Fichier principal
Vignette du fichier
RR2001-37.pdf (339.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101846 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101846 , version 1

Citer

Olivier Beaumont, Vincent Boudet, Yves Robert. A Realistic Model and an Efficient Heuristic for Scheduling with Heterogeneous Processors. [Research Report] LIP RR-2001-37, Laboratoire de l'informatique du parallélisme. 2001, 2+18p. ⟨hal-02101846⟩
32 Consultations
182 Téléchargements

Partager

Gmail Facebook X LinkedIn More