Static worksharing strategies for heterogeneous computers with unrecoverable interruptions

Abstract : One has a large computational workload that is "divisible" (its constituent tasks' 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? 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. We deal with three versions of this problem. The simplest version ignores communication costs but allows computers to differ in speed (a heterogeneous set of computers). The other two versions account for communication costs, first with identical remote computers (a homogeneous set of computers), and then with computers that may differ in speed. We provide exact expressions for the optimal work expectation for all three versions of the problem-via explicit closed-form expressions for the first two versions, and via a recurrence that computes this optimal value for the last, most general version.
Type de document :
Article dans une revue
Parallel Computing, Elsevier, 2011, 37 (8), pp.365-378. 〈10.1016/j.parco.2010.03.001〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00945070
Contributeur : Equipe Roma <>
Soumis le : jeudi 18 octobre 2018 - 18:10:21
Dernière modification le : vendredi 19 octobre 2018 - 20:53:24

Fichier

PARCO-finalversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Anne Benoit, Yves Robert, Arnold Rosenberg, Frédéric Vivien. Static worksharing strategies for heterogeneous computers with unrecoverable interruptions. Parallel Computing, Elsevier, 2011, 37 (8), pp.365-378. 〈10.1016/j.parco.2010.03.001〉. 〈hal-00945070〉

Partager

Métriques

Consultations de la notice

221

Téléchargements de fichiers

6