Mapping Tightly-Coupled Applications on Volatile Resources

Abstract : Platforms that comprise volatile processors, such as desktop grids, have been traditionally used for executing independent-task applications. In this work we study the scheduling of tightly-coupled iterative master-worker applications onto volatile processors. The main challenge is that workers must be simultaneously available for the application to make progress. We consider two additional complications: one should take into account that workers can become temporarily reclaimed and, for data-intensive applications, one should account for the limited bandwidth between the master and the workers. In this context, our first contribution is a theoretical study of the scheduling problem in its off-line version, i.e., when processor availability is known in advance. Even in this case the problem is NP-hard. Our second contribution is an analytical approximation of the expectation of the time needed by a set of workers to complete a set of tasks and of the probability of success of this computation. This approximation relies on a Markovian assumption for the temporal availability of processors. Our third contribution is a set of heuristics, some of which use the above approximation to favor reliable processors in a sensible manner. We evaluate these heuristics in simulation. We identify some heuristics that significantly outperform their competitors and derive heuristic design guidelines.
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00697621
Contributor : Fanny Dufossé <>
Submitted on : Tuesday, May 15, 2012 - 5:10:36 PM
Last modification on : Thursday, August 1, 2019 - 10:42:20 AM
Long-term archiving on : Friday, November 30, 2012 - 11:45:56 AM

File

RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00697621, version 1

Collections

Citation

Henri Casanova, Fanny Dufossé, Yves Robert, Frédéric Vivien. Mapping Tightly-Coupled Applications on Volatile Resources. 2012. ⟨ensl-00697621⟩

Share

Metrics

Record views

423

Files downloads

234