Reliability and performance optimization of pipelined real-time systems

Anne Benoit 1, 2 Fanny Dufossé 1, 2 Alain Girault 3 Yves Robert 1, 2
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
3 SPADES - Sound Programming of Adaptive Dependable Embedded Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We consider pipelined real-time systems that consist of a chain of tasks executing on a distributed platform. The processing of the tasks is pipelined: each processor executes only one interval of consecutive tasks. We are interested in minimizing both the input-output latency and the period of application mapping. For dependability reasons, we are also interested in maximizing the reliability of the system. We therefore assign several processors to each interval of tasks, so as to increase the reliability of the system. Both processors and communication links are unreliable and subject to transient failures. We assume that the arrival of the failures follows a constant parameter Poisson law, and that the failures are statistically independent events. We study several variants of this multiprocessor mapping problem, with several hypotheses on the target platform (homogeneous/heterogeneous speeds and/or failure rates). We provide NP-hardness complexity results, and optimal mapping algorithms for polynomial problem instances. Efficient heuristics are presented to solve the general case, and experimental results are provided.
Liste complète des métadonnées

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-00926123
Contributor : Equipe Roma <>
Submitted on : Thursday, January 9, 2014 - 10:29:04 AM
Last modification on : Thursday, November 8, 2018 - 2:26:08 PM
Document(s) archivé(s) le : Thursday, April 10, 2014 - 2:45:17 PM

File

jpdc.pdf
Files produced by the author(s)

Identifiers

Citation

Anne Benoit, Fanny Dufossé, Alain Girault, Yves Robert. Reliability and performance optimization of pipelined real-time systems. Journal of Parallel and Distributed Computing, Elsevier, 2013, 73 (6), pp.851-865. ⟨10.1016/j.jpdc.2013.02.009⟩. ⟨hal-00926123⟩

Share

Metrics

Record views

357

Files downloads

364