Avec l'évolution des machines parallèles, l’utilisation des protocoles de
tolérance aux fautes devient nécessaire. Les techniques utilisées devront
permettre de minimiser les effets des défaillances tout en garantissant de
bonnes performances en exécution sans faute. Les protocoles de tolérance aux
fautes existants nécessitent soit un redémarrage global (protocoles de sauvegarde
de points de reprise coordonnés) soit l’enregistrement de l’ensemble des messages
(protocoles à enregistrement de messages) et ne sont donc pas adaptées à ces
architectures.

Nous avons étudié les caractéristiques des protocoles existants. Dans un premier
temps, nous avons étudié le déterminisme des applications, étant donné que les
protocoles existants supposent des exécutions non déterministes (protocoles de
sauvegarde de points de reprise) ou déterministes par morceaux (protocoles à
enregistrement de messages). Dans notre étude, nous nous sommes intéressés au
modèle par échange de messages, et plus précisément aux applications MPI. Nous
avons analysé 26 applications MPI et avons mis avant une nouvelle
caractéristique appelée "déterminisme des émissions" qui correspond à
la majorité des applications étudiées. Dans un second temps, nous nous sommes
intéressés aux schémas de communications des applications afin d'étudier
l'existence des groupes de processus dans ces schémas. L'étude a montré que
pour la plupart des applications, il est possible de créer des groupes de
processus de façon à minimiser la taille des groupes et le volume des messages
inter-groupe.

A partir de là nous avons proposé deux protocoles de tolérance aux fautes.
Le premier est un protocole de sauvegarde de points de reprise non coordonnés
pour les applications à émissions déterministes qui évite l'effet domino en
n'enregistrant qu'un sous ensemble des messages de l'application. Nous avons
également adapté le protocole pour l'utiliser sur des groupes de processus. Par
la suite, nous avons proposé HydEE, un protocole hiérarchique fondé sur le
déterminisme des émissions et les groupes de processus. Il combine un protocole
de sauvegarde de points de reprise coordonnés au sein des groupes à un
protocole à enregistrement de messages entre les groupes. Ces deux protocoles
ont été mis en œuvre dans la bibliothèque MPICH2 et l’évaluation de leurs
performances montrent que ces deux protocoles ont un faible impact sur les
performances des applications.


Abstract:

With the evolution of parallel computers, the use of fault
tolerance protocols is required. The techniques used must allow to
minimize the impact of failures while providing good failure free perfromances.
Existing fault tolerance protocols force either a global restart (coordinated
checkpointing protocols) or the log of all messages (message logging protocols)
and thus they are not adapted to these architectures.

We studied the characteristics of the existing protocols. We first studied the
determinism of the applications, since existing protocols assume non deterministic
executions (checkpointing protocols) or piecewise deterministic ones (message
logging protocols). In our study, we focused on the message passing model, and more
specifically on MPI applications. We have analyzed 26 MPI applications and
highlighted a new characteristic called "send-determinism" which corresponds to
most studied applications. In a second step, we focused on the communication
patterns of the applications to study the existence of clusters of processes in
these patterns. The study showed that for most applications, it is possible to
create clusters of processes to minimize the size of clusters and the volume of
inter-cluster messages.

Then we designed two fault tolérance protocols. The first one is an uncoordinated
checkpointing protocol which is based on the send-deterministic assumption and
avoids domino effect while logging only a subset of the application messages. We
have also adapted the protocol to clusters of processes. Then, we proposed HydEE,
a hierarchical protocol that is also based on the send-deterministic assumption and
that is used on clusters of processes. It combines a coordinated checkpointing
protocol inside clusters to a message logging protocol for inter-cluster
messages. Both protocols have been implemented in MPICH2 library and the
performance evaluation showed that they both have a low impact on the
applications failure free performances.