loading...
Off-Line and On-Line Scheduling on Heterogeneous Master-Slave Platforms
Montb?liard-Sochaux, France February 15-February 17
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PDP.2006.4914th Euromicro International Conferen ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jean-Francois Pineau, CNRS-INRIA, France
Yves Robert, CNRS-INRIA, France
Frederic Vivien, CNRS-INRIA, France
In this paper, 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 offline 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, on a small but fully heterogeneous MPIplatform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.
Citation:
Jean-Francois Pineau, Yves Robert, Frederic Vivien, "Off-Line and On-Line Scheduling on Heterogeneous Master-Slave Platforms," pdp, pp.439-446, 14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.