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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|