Optimizing latency and reliability of pipeline workflow applications

Abstract : (ENG) Mapping applications onto heterogeneous platforms is a difficult challenge, even for simple application patterns such as pipeline graphs. Theproblem is even more complex when processors are subject to failureduring the execution of the application. In this paper, we study thecomplexity of a bi-criteria mapping which aims at optimizing the la-tency (i.e., the response time) and the reliability (i.e., the probabilitythat the computation will be successful) of the application. Latency isminimized by using faster processors, while reliability is increased byreplicating computations on a set of processors. However, replicationincreases latency (additional communications, slower processors). Theapplication fails to be executed only if all the processors fail duringexecution. While simple polynomial algorithms can be found for fullyhomogeneous platforms, the problem becomes NP-hard when tacklingheterogeneous platforms. This is yet another illustration of the additional complexity added by heterogeneity.
Document type :
Reports
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102604
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 3:03:18 PM
Last modification on : Wednesday, November 20, 2019 - 7:24:03 AM

File

RR2007-43.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102604, version 1

Collections

Citation

Anne Benoit, Veronika Rehn-Sonigo, Yves Robert. Optimizing latency and reliability of pipeline workflow applications. [Research Report] LIp RR-2007-43, Laboratoire de l'informatique du parallélisme. 2007, 2+11p. ⟨hal-02102604⟩

Share

Metrics

Record views

37

Files downloads

44