Back to Search
Start Over
Off-line and on-line scheduling on heterogeneous master-slave platforms
- Source :
- PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2006, Montbéliard-Sochaux, France, [Research Report] RR-5634, LIP RR-2005-31, INRIA, LIP. 2005, pp.23, PDP
- Publication Year :
- 2006
- Publisher :
- HAL CCSD, 2006.
-
Abstract
- In this work, we deal with the problem of scheduling independent tasks on heterogeneous master-slave platforms. We target both off-line and on-line problems, with several objective functions (makespan, maximum response time, total completion time). On the theoretical side, our results are two-fold: (i) For off-line scheduling, we prove several optimality results for problems with release dates; (ii) For on-line scheduling, we establish lower bounds on the competitive ratio of any deterministic algorithm. On the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper. We studied experimentally these heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.; Nous nous intéressons ici au problème de l'ordonnancement d'un ensemble de tâches indépendantes sur une plate-forme maître esclave hétérogène. Nous considérons les problèmes en ligne (ou à la volée) et hors-ligne, pour des fonctions objectives différentes (durée totale d'exécution, temps de réponse maximum temps de réponse moyen). D'un point de vue théorique, nous obtenons deux types de résultats : (i) pour le problème hors-ligne, nous avons établi plusieurs résultats d'optimalité pour des problèmes avec dates d'arrivée ; (ii) pour le problème en ligne, nous avons établi des bornes inférieures sur le facteur de compétitivité des algorithmes déterministes. D'un point de vue pratique, nous avons implémenté plusieurs heuristiques, certaines classiques, d'autres issues du présent travail. Nous avons étudié expérimentalement ces heuristiques sur une petite plate-forme MPI totalement hétérogène. Les résultats expérimentaux montrent la supériorité des heuristiques qui prennent complètement en compte les capacités relatives des différents liens de communication.
- Subjects :
- Rate-monotonic scheduling
Earliest deadline first scheduling
020203 distributed computing
Computer science
Distributed computing
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
02 engineering and technology
Dynamic priority scheduling
Flow shop scheduling
Round-robin scheduling
01 natural sciences
heterogeneous computing
Fair-share scheduling
master-slave platforms
Fixed-priority pre-emptive scheduling
010201 computation theory & mathematics
release dates
Two-level scheduling
0202 electrical engineering, electronic engineering, information engineering
scheduling
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
on-line
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, PDP'2006, 14th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2006, Montbéliard-Sochaux, France, [Research Report] RR-5634, LIP RR-2005-31, INRIA, LIP. 2005, pp.23, PDP
- Accession number :
- edsair.doi.dedup.....ff02bbfa79b8ed78a9390fbddb02826a