Mapping pipelined applications with replication to increase throughput and reliability

Abstract : apping and scheduling an application onto the processors of a parallel system is a difficult problem. This is true when performance is the only objective, but becomes worse when a second optimization criterion like reliability is involved. In this paper we investigate the problem of mapping an application consisting of several consecutive stages, i.e., a pipeline, onto heterogeneous processors, while considering both the performance, measured as throughput, and the reliability. The mechanism of replication, which refers to the mapping of an application stage onto more than one processor, can be used to increase throughput but also to increase reliability. Finding the right replication trade-off plays a pivotal role for this bi-criteria optimization problem. Our formal model includes heterogeneous processors, both in terms of execution speed as well as in terms of reliability. We study the complexity of the various sub problems and show how a solution can be obtained for the polynomial cases. For the general NP-hard problem, heuristics are presented and experimentally evaluated. We further propose the design of an exact algorithm based on A* state space search which allows us to evaluate the performance of our heuristics for small problem instances.
Type de document :
Communication dans un congrès
International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2010, Petropolis, Brazil. pp.55-62, 2010, 〈10.1109/SBAC-PAD.2010.16〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01059633
Contributeur : Equipe Roma <>
Soumis le : lundi 1 septembre 2014 - 14:38:54
Dernière modification le : mardi 16 janvier 2018 - 15:35:23

Identifiants

Collections

Citation

Anne Benoit, Loris Marchal, Oliver Sinnen. Mapping pipelined applications with replication to increase throughput and reliability. International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2010, Petropolis, Brazil. pp.55-62, 2010, 〈10.1109/SBAC-PAD.2010.16〉. 〈hal-01059633〉

Partager

Métriques

Consultations de la notice

150