Mohamed Slim Bouguerra - Tolérance aux pannes dans des environnements de calcul parallèle et distribué : optimisation des stratégies de sauvegarde

Le passage de l’échelle des nouvelles plates-formes de calcul parallèle et distribué soulève de nombreux défis scientifiques. À terme, il est envisageable de voir apparaître des applications composées d’un milliard de processus exécutés sur des systèmes à un million de coeurs. Cette augmentation fulgurante du nombre de processeurs pose un défi de résilience incontournable, puisque ces applications devraient faire face à plusieurs pannes par jours. Pour assurer une bonne exécution dans ce contexte hautement perturbé par des interruptions, de nombreuses techniques de tolérance aux pannes telle que l’approche de sauvegarde et reprise (checkpoint) ont été imaginées et étudiées. Cependant, l’intégration de ces approches de tolérance aux pannes dans le couple formé par l’application et la plate-forme d’exécution soulève des problématiques d’optimisation pour déterminer le compromis entre le surcoût induit par le mécanisme de tolérance aux pannes d’un coté et l’impact des pannes sur l’exécution d’un autre coté.

Dans la première partie de cette thèse nous concevons deux modèles de performance stochastique (minimisation de l’impact des pannes et du surcoût des points de sauvegarde sur l’espérance du temps de complétion de l’exécution en fonction de la distribution d’inter-arrivées des pannes). Dans la première variante l’objectif est la minimisation de l’espérance du temps de complétion en considérant que l’application est de nature préemptive. Nous exhibons dans ce cas de figure tout d’abord une expression analytique de la période de sauvegarde optimale quand le taux de panne et le surcoût des points de sauvegarde sont constants.

Par contre dans le cas où le taux de panne ou les surcoûts des points de sauvegarde sont arbitraires nous présentons une approche numérique pour calculer l’ordonnancement optimal des points de sauvegarde. Dans la deuxième variante, l’objectif est la minimisation de l’espérance de la quantité totale de temps perdu avant la première panne en considérant les applications de nature non-préemptive.

Dans ce cas de figure, nous démontrons tout d’abord que si les surcoûts des points sauvegarde sont arbitraires alors le problème du meilleur ordonnancement des points de sauvegarde est NP-complet. Ensuite, nous exhibons un schéma de programmation dynamique pour calculer un ordonnancement optimal.

Dans la deuxième partie de cette thèse nous nous focalisons sur la conception des stratégies d’ordonnancement tolérant aux pannes qui optimisent à la fois le temps de complétion de la dernière tâche et la probabilité de succès de l’application. Nous mettons en évidence dans ce cas de figure qu’en fonction de la nature de la distribution de pannes, les deux objectifs à optimiser sont tantôt antagonistes, tantôt congruents. Ensuite en fonction de la nature de distribution de pannes nous donnons des approches d’ordonnancement avec des ratios de performance garantis par rapport aux deux objectifs.