Optimizing latency and reliability of pipeline workflow applications

Anne Benoit (1) , Veronika Rehn-Sonigo (1) , Yves Robert (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

(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.

L’ordonnancement et l’allocation des applications sur plates-formes hétérogènes sont des problèmes cruciaux, même pour des applications simples comme des graphes en pipeline. Le problème devient même encore plus complexe quand les processeurs peuvent tomber en panne pendant l’exécution de l’application. Dans cet article, nous étudions la complexité d’une allocation bi-critère qui vise à optimiser la latence (i.e., le temps de réponse) et la fiabilité (i.e., la probabilité que le calcul réussisse)de l’application. La latence est minimisée en utilisant des processeurs rapides, tandis que la fiabilité est augmentée en répliquant les calculs sur un ensemble de processeurs. Toutefois, la réplication augmente la latence (communications additionnelles et processeurs moins rapides). L’application échoue à être exécutée seulement si tout les processeurs échouent pendant l’exécution. Des algorithmes simples en temps polynomial peuvent être trouvés pour plates-formes complètement homogènes,tandis que le problème devient NP-dur quand on s’attaque aux plates-formes hétérogènes. C’est encore une autre illustration de la complexité additionnelle due à l’hétérogénéité.

Mots clés: Complexity results; Heterogeneity; Reliability; Response time; Scheduling

Mots clés: Fiabilité; Hétérogénéité; Ordonnancement; Résultats de complexité; Temps de réponse

Domaines: Informatique [cs]

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⟩