Static Worksharing Strategies for Heterogeneous Computers with Unrecoverable Failures

Abstract : One has a large workload that is "divisible" (its constituent work's granularity can be adjusted arbitrarily) and one has access to p remote computers that can assist in computing the workload. How can one best utilize the computers toward this end? Two features complicate this question. First, the remote computers may differ from one another in speed. Second, each remote computer is subject to interruptions of known likelihood that kill all work in progress on it. One wishes to orchestrate sharing the workload with the remote computers in a way that maximizes the expected amount of work completed, given the risk of interruptions. We consider three versions of the preceding problem. Two versions envision heterogeneous computing resources: the remote computers may differ from one another in speed; one version envisions homogeneous computing resources: the remote computers are identical. One of the heterogeneous versions ignores communication costs (i.e., assumes that they are negligible); the other two versions account explicitly for communication costs. We provide exact expressions for the optimal work expectation for all three versions of the problem. For the most general version (heterogeneous resources, with communication costs), we provide a recurrence for computing this expectation; for the other two versions, we provide closed-form expressions.
Type de document :
Communication dans un congrès
Lin, Hai-Xiang and Alexander, Michael and Forsell, Martti and Knüpfer, Andreas and Prodan, Radu and Sousa, Leonel and Streit, Achim. HeteroPar 2009, Aug 2009, Delft, Netherlands. Springer Berlin Heidelberg, 6043, pp.71-80, 2010, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-14122-5_11〉. 〈10.1007/978-3-642-14122-5_11〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01062559
Contributeur : Equipe Roma <>
Soumis le : mercredi 10 septembre 2014 - 09:41:26
Dernière modification le : vendredi 20 avril 2018 - 15:44:25

Lien texte intégral

Identifiants

Collections

Citation

Anne Benoit, Yves Robert, Arnold L. Rosenberg, Frédéric Vivien. Static Worksharing Strategies for Heterogeneous Computers with Unrecoverable Failures. Lin, Hai-Xiang and Alexander, Michael and Forsell, Martti and Knüpfer, Andreas and Prodan, Radu and Sousa, Leonel and Streit, Achim. HeteroPar 2009, Aug 2009, Delft, Netherlands. Springer Berlin Heidelberg, 6043, pp.71-80, 2010, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-14122-5_11〉. 〈10.1007/978-3-642-14122-5_11〉. 〈hal-01062559〉

Partager

Métriques

Consultations de la notice

108