Scheduling Tightly-Coupled Applications on Heterogeneous Desktop Grids - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

Scheduling Tightly-Coupled Applications on Heterogeneous Desktop Grids

(1) , (2, 3) , (2, 3) , (2, 3)


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 three additional complications: (i) one should take into account that workers can become temporarily reclaimed and, for data-intensive applications; (ii) one should account for the limited bandwidth between the master and the workers; and (iii) workers are strongly heterogeneous, with different computing speeds and availability probability distributions. 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.
Fichier principal
Vignette du fichier
hcw-coupled.pdf (312.51 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00788606 , version 1 (18-02-2013)


  • HAL Id : hal-00788606 , version 1


Henri Casanova, Fanny Dufossé, Yves Robert, Frédéric Vivien. Scheduling Tightly-Coupled Applications on Heterogeneous Desktop Grids. HCW 2013 - 22nd International Heterogeneity in Computing Workshop, May 2013, Boston, United States. ⟨hal-00788606⟩
200 View
127 Download


Gmail Facebook Twitter LinkedIn More