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

13:30
Lundi
2
Avr
2012
Organisé par : 

Mohamed Slim Bouguerra

Intervenant : 

Mohamed Slim Bouguerra

Information détaillée : 

Soutenance : Lundi 2 Avril 2011 à 13h:30 dans le grand amphithéâtre de l’INRIA Montbonnot (655 avenue de l’Europe 38334 MONTBONNOT SAINT ISMIER, Rhône-Alpes).

Jury :

  • M. Yves Robert Professeur ENS Lyon, Rapporteur
  • M. Emmanuel Jeannot Directeur de recherche INRIA Bordeaux Sud-Ouest, Rapporteur
  • M. Pierre Sense Professeur Paris 6, Examinateur
  • M. Alain Girault Directeur de recherche INRIA Rhone-aples, Président
  • M. Mohamed Jemni Professeur Ecole supérieure de sciences et techniques de Tunis, Examinateur
  • M. Denis Trystram Professeur Grenoble INP, Directeur de thèse
  • M. Thierry Gautier Chargé de recherche INRIA Rhone-alpes, Codirecteur de thèse
Résumé : 

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.