Comments on "Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks''
Résumé
Min, Veeravalli, and Barlas proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that the proposed 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. Finally, we formally prove that under a linear cost model, as in the original paper, an optimal schedule has an infinite number of installments. Such a cost model can therefore not be sed to design practical multi-installment strategies.
Min, Veeravalli, and Barlas ont proposé [8,9] des stratégies pour minimiser le temps d’exécution d’une ou de plusieurs tâches divisibles sur un réseau linéaire de processeurs hétérogènes, en distribuant le travail en une ou plusieurs tournées. Sur un exemple très simple nous montrons que l’approche proposée dans [9] ne produit pas toujours une solution et que, quand elle le fait, la solution est souvent sous-optimale. Nous montrons également comment trouver un ordonnancement optimal pour toute instance, quand le nombre de tournées par tâches est spécifié. Finalement, nous montrons formellement que lorsque les fonctions de coûts sont linéaires, comme c’est le cas dans [8,9], un ordonnancement optimal au n nombre infini de tournées. Un tel modèle de coût ne peut donc pas être utilisé pour définir des stratégies en multi-tournées utilisables en pratique
Fichier principal
RR-6123.pdf (269.21 Ko)
Télécharger le fichier
RR2007-07.pdf (518.09 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...