Scheduling linear chain streaming applications on heterogeneous systems with failures

Anne Benoit 1, 2 Alexandru Dobrila 3 Jean-Marc Nicod 4 Laurent Philippe 5
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 AS2M/PHM
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
5 DISC/CARTOON
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
Abstract : In this paper, we study the problem of optimizing the throughput of streaming applications for heterogeneous platforms subject to failures. Applications are linear graphs of tasks (pipelines), with a type associated to each task. The challenge is to map each task onto one machine of a target platform, each machine having to be specialized to process only one task type, given that every machine is able to process all the types before being specialized in order to avoid costly setups. The objective is to maximize the throughput, i.e., the rate at which jobs can be processed when accounting for failures. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines may compute the same task type at different speeds. Several polynomial time heuristics are designed for the most realistic specialized settings. Simulation results assess their efficiency, showing that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, the throughput is close to the optimal solution in the particular cases where the optimal throughput can be computed.
Type de document :
Article dans une revue
Future Generation Computer Systems, Elsevier, 2013, 29 (5), pp.1140-1151. 〈10.1016/j.future.2012.12.015〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00926146
Contributeur : Equipe Roma <>
Soumis le : jeudi 9 janvier 2014 - 10:39:13
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : jeudi 10 avril 2014 - 14:45:38

Fichier

fgcs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Anne Benoit, Alexandru Dobrila, Jean-Marc Nicod, Laurent Philippe. Scheduling linear chain streaming applications on heterogeneous systems with failures. Future Generation Computer Systems, Elsevier, 2013, 29 (5), pp.1140-1151. 〈10.1016/j.future.2012.12.015〉. 〈hal-00926146〉

Partager

Métriques

Consultations de la notice

395

Téléchargements de fichiers

256