loading...
Scheduling multiple divisible loads on a linear processor network
Hsinchu, Taiwan December 05-December 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICPADS.2007.444776813th International Conference on Para ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Matthieu Gallet, LIP, CNRS-ENS Lyon-INRIA-UCBL, ?cole normale sup?rieure de Lyon, France
Yves Robert, LIP, CNRS-ENS Lyon-INRIA-UCBL, ?cole normale sup?rieure de Lyon, France
Frederic Vivien, LIP, CNRS-ENS Lyon-INRIA-UCBL, ?cole normale sup?rieure de Lyon, France
Min, Veeravalli, and Barlas have recently proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments [18, 19]. We show on a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Then, we formally prove that any optimal schedule has an infinite number of installments under a linear cost model as the one assumed in [18, 19]. Such a cost model cannot be used to design practical multi-installment strategies. Finally, through extensive simulations we confirmed that the best solution is always produced by the linear programming approach.
Citation:
Matthieu Gallet, Yves Robert, Frederic Vivien, "Scheduling multiple divisible loads on a linear processor network," icpads, vol. 1, pp.1-8, 13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.