1
Tolérance automatique aux défaillances par points de reprise et retour en arrière dans les systèmes hautes performances à passage de message
Aurélien Bouteiller - Séminaire ID-IMAG - 14 septembre 2006
Grand Large
Aurélien Bouteiller – Séminaire ID-IMAG – 14 septembre 2006
Open MPIOpen MPI
Grid’5000
2
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
3
Calcul hautes performancesPourquoi ?
4
Calcul hautes performancesÉvolution du nombre de processeurs
0
50
100
150
200
250
300
Nombrede machines
19931994199519961997199819992000200120022003200420052006
12
3-45-8
9-1617-32
33-6465-128
129-256257-512
513-10241k-2k
2k-4k4k-8k
8k-16k16k-32k
32k-64k64k-128k
Nombrede processeurs
1998 1998 ASCI REDASCI RED
1TFlop1TFlop10k Ppro@33310k Ppro@333
2006 Xbox 3601TFlop1 GPU
2006 AMD 2006 AMD OpteronOpteron
3Gflop3Gflop
5
Calcul hautes performancesProgrammation des machines parallèles
6
Calcul hautes performancesProgrammation des machines parallèles
11 22 33
55 664411
22 33
4411
22
11 2233 44
55 66
Communications entre processusMémoire partagée : OpenMP Passage de message : MPI
7
Calcul hautes performancesFiabilité et temps moyen entre deux fautes
8
Calcul hautes performancesÉvolution du MTBF dans le futur
1 PetaFlop = 200k 5Gflop CPU
Avec du matériel fiable actuel (ASCI white), une machine de cette dimension subit
1 défaillance par heure
BlueGene/L
9
Calcul hautes performancesSurvivre aux défaillances
Constatations :
• Les défaillances sont trop fréquentes pour être ignorées
• Le logiciel est la part majoritaire du coût d’exploitation
• Rendre une application tolérante aux fautes est difficile
• De nombreuses applications utilisent MPI
Conséquence : Tolérance aux fautes automatique intégrée dans MPI
P0
P1
P2
m1m2
m5
m4
m3
10
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
11
Système distribué : modélisationRéseauFiabilité : garanties sur le bon acheminement du message (UDP/TCP)
Ordre de livraison :
• Sans ordre
• Ordre par canal, si p0 envoi m1 puis m2 vers p1, p1 reçoit d’abord m1 puis m2
• Ordre causal, si un évènement f est causé ou influencé par e, alors tout le système doit observer e avant f
13
Système distribué : modélisationDéfaillances
Panne crash (arrêt total)• Un processus n’émet plus aucun message à partir de la faute
• C’est le type de faute le moins grave
Panne de réseau• Le réseau ne respecte pas sa spécification (non respect de la fiabilité,
livraison dans le désordre)
Panne byzantine• Un processus présente n’importe quel comportement arbitraire
• C’est le type de faute le plus grave (corruption mémoire, virus, etc).
14
Système distribué : modélisationConcensus dans le cas général
Consensus asynchrone• Terminaison : Les processus décident en un temps fini
• Agrément : tous les processus non défaillants décident d’une même valeur
• Validité : Si les processus partagent tous une même valeur initiale, ils décident de cette valeur
• Type de fautes : des processus peuvent s’arrêter totalement
Fischer, Lynch, Paterson, Impossibility of distributed concensus with one faulty process (journal of ACM 32(2), April 1985)
0
1
…
P0
P1
15
Modèle synchrone• Les processus réalisent une étape de calcul de façon synchronisée (Horloge
globale). • A la fin de la phase, tous les messages envoyés ont été reçus • On peut résoudre le problème, mais ne correspond pas au monde réel.
Modèle asynchrone• pas d’horloge globale• un message peut transiter un temps arbitrairement long dans un canal• Modèle très expressif (Internet), mais on ne peut rien faire!
Modèle(s) Pseudosynchrone(s)• Pas d’horloge globale• Il existe une borne sur le temps de transit d’un message dans un canal• Equivalent avec l’existence d’un détecteur de défaillances (appelé Oracle)
(Chen, Toueg, Aguilera: On the QoS of failure detectors, proc. Of ICDSN/FTCS-30, June 2000)
• Représente bien les réseaux de diamètre connu constitué de compostants temps réels (typiquement LAN/Clusters), permet de résoudre le problème! (Chen, Toueg: Unreliable failure detectors for reliable distributed systmes, Journal of the ACM 43(2) march 1996)
Système distribué : modélisationPseudosynchronisme
16
Algorithmes de tolérance aux fautesChoix d’une méthode générale
• Autostabilisation
• RéplicationP1#1 P1#2 P1#3
P2#1
Active
P1#2 P1#1 P1#3
P2#1
Passive
Stabilisation
17
Algorithmes de tolérance aux fautesPoints de reprise
P0 P1 P2
P0
P1
P2C3 C1
m1m2
m5
C2
m4
m3
m5
Ckpt
18
Algorithmes de tolérance aux fautesPoints de reprise
P0 P1 P2
P0
P1
P2C3 C1
m1m2
m5
C2
m4
m3
Ckpt
P0
19
Algorithmes de tolérance aux fautesPoints de reprise
P0
P1
P2C3 C1
m1m2
m5
C2
m4
m3
Points de reprise non coordonnés : état global incohérent• L’ordre des réceptions est non déterministe• Les messages reçus non envoyés par rapport à la
ligne de reprise sont incohérents• L’effect domino peut provoquer le retour jusqu’au début même
avec une seule faute• Perte de toute l’exécution, coût d’une faute imprévisible
20
Algorithmes de tolérance aux fautesÉtat global incohérent
P0
P1
P2C3 C1
m1m2
C2
m4
m3
Définition : coupe
collection de points de reprises Ci,k (k ieme point de reprise du processus i) telle qu’elle contient un unique point de reprise par processus.
Type de message par rapport à une coupe C• Passé : émission et réception sont avant C (m2 par rapport à C1)• Futur : émission et réception sont après C (m5 par rapport à C1)• En-transit: émission avant C, réception après C (m4 par rapport à C1)• Orphelin: émission après C, réception avant C (m2 par rapport à C2)
Définition : Coupe cohérente• Pas de message orphelin• Tous les messages en-transit sont enregistrés
m5
21
Algorithmes de tolérance aux fautesCoupe cohérente (Chandy&Lamport)
P0
P1
P2
22
Algorithmes de tolérance aux fautesCoupe cohérente (Chandy&Lamport)
P0
P1
P2
23
Algorithmes de tolérance aux fautesCoupe cohérente (Chandy&Lamport)
P0
P1
P2
24
Algorithmes de tolérance aux fautesCoupe cohérente (Chandy&Lamport)
P0
P1
P2
25
Algorithmes de tolérance aux fautesCoupe cohérente (Chandy&Lamport)
P0
P1
P2
• Coût négligeable sur l’exécution sans faute
• Synchronisation globale (temps d’enregistrement d’une coupe cohérente long)
• Une faute unique provoque le retour de tous les processus à leur point de reprise : coût de récupération élevé
26
Algorithmes de tolérance aux fautesEnregistrement de messages
P0
P1
P2C3 C1
m1m2
m5
C2
m4
m3
• Si un processus est déterministe par parties, enregistrer les évènements non déterministes permet de rejouer l’exécution initiale
• L’ordre des réceptions sur le réseau est non déterministe
27
Algorithmes de tolérance aux fautesEnregistrement pessimiste sender-based
P0
P1
P2m1
3 problèmes : • Messages en-transit : enregistrement du message sur l’émetteur
• Ordre des réceptions non déterministe : enregistrement de l’ordre des évènements sur un support stable
• Propagation transitive de dépendance avec des évenements non déterministes interdite : Retardement des émissions
m2 m3
SP0
rm1 rm2{rm1 ,rm2}
{rm1 ,rm2}
Ok-2
?m2
?m1
m2
m1
[m1]
[m2]m4
28
Algorithmes de tolérance aux fautesEnregistrement pessimiste sender-based
P0
P1
P2m1
Messages en-transit et fautes multiples : • Messages en-transit : enregistrement du message sur l’émetteur
• Si l’émetteur disparaît, les messages disparaissent : enregistrement en même temps que le point de reprise
• En l’absence de point de reprise, le message est regénéré
m2 m3
SP0
rm1 rm2{rm1 ,rm2}
{rm1 ,rm2}
Ok-2
?m2
?m1
m2
m1
[m1]
[m2]m4Ckpt + [m2]
Ckpt
[m2]
29
Algorithmes de tolérance aux fautesEnregistrement causal
P0
P1
P2m1
problème : • Interdiction des dépendences transitives : Latence
multipliée par 3 avec algo pessimiste
• Lever l’interdiction : propager les évènements vers ceux qui en dépendent
m2 m3
SP0
rm1 rm2{rm1 ,rm2}
{rm1 ,rm2}
Ok-2
?m2
?m1
m2
m1
[m1]
[m2]m4
{rm1 ,rm2}
{rm1 ,rm2, rm3}
30
Algorithmes de tolérance aux fautesEnregistrement causal : graphe
P0
P1
P2m1
problème : • La propagation d’évènements coûte cher en bande passante
• Certains évènements envoyés sont déjà connus du destinataire
• La structure de graphe de causalité permet de détecter de tels évènements
m2 m3
rm1 rm2
m5
{rm1 ,rm2}
{rm1 ,rm2, rm3}m6
{rm1 ,rm2, rm3, rm5}
m4
rm4
{rm3 }rm3
rm5
31
Algorithmes de tolérance aux fautesEnregistrement causal : graphe
P0
P1
P2m1
m2 m3
rm1 rm2
m5
{rm1 ,rm2}
{rm1 ,rm2, rm3}m6
{ rm3, rm5}
m4
rm4
{rm3 }rm3
rm5
rm2
P0
P1
P2
rm1
rm3
rm4
rm5
32
Objectif : Etude expérimentale des protocoles de tolérance aux fautes
• Modèle pseudosynchrone – Pannes crash – Automatique – points de reprise : bien adapté pour le calcul hautes performances
• Concevoir des algorithmes originaux adapté au calcul hautes performances
• Explorer des optimisations techniques
• Plusieurs familles d’algorithmes (coupe cohérente, enregistrement de message pessimiste, causal) : comparaison expérimentale
• Environnement équitable pour exprimer les algorithmes et les comparer
• Classification suivant des critères de performance et de résistance aux fautes
33
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
34
MPICH-V : comparaison avec les implémentations existantes
Classification des implémentations suivant deux critères• Niveau dans la pile logicielle MPI• Algorithme de tolérance aux défaillances utilisé
35
MPICH-V : gestion des communicationsMPI
36
MPICH-V : cas particulier de ch_v1Enregistrement de message distant
37
MPICH-V : environnement partagé Architecture générale
38
code
CSAC
libmpichv
OrdreCkpt
(1) fork
fork(2) Terminer les comms en cours(3) Fermer les canaux(4) Appeler ckpt_and_exit()
Le point de reprise est transféré à la volée sur le support stable : serveur, disque ou les deux
L’exécution reprend après (4), on réouvre les canaux de communication et reprend les opérations
Bibliothèque de point de reprise Condor Stand Alone Checkpointing
Copie locale du processus avec fork() et transfert non bloquant
MPICH-V : enregistrement non bloquant des points de reprise
39
MPICH-V : ordonnancement des points de
reprise (enregistrement de messages)
Mémoire P1
Serveur ckpt
Mémoire P0P0
P1
1 1 2
3 doit êtreenregistré
123
1 1 2 123
1 et 2 peuvent être effacés Garbage collector
1, 2 et 3 peuvent être effacés Garbage collector
Rien à enregistrer
La non coordination des points de reprise implique que tous les messages peuvent être en-transit
• L’enregistrement local occupe de la mémoire• Le transfert vers le serveur occupe du débit• Diminution du coût en effaçant les messages devenus inutiles (preuve que seuls les
messages orphelins et dans le passé sont effacés)
L’ordonnancement des points de reprise permet de maximiser le nombre de messages effacés
40
MPICH-V : enregistrement de message causal paresseux
Nouvelle stratégie causale paresseuse • non optimale mais de moindre coût en calcul
• Preuve de correction fournie
41
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
42
noeud
Réseau
noeud
noeud
Un noeud fiableDistributeur et détecteur+Serveur de point de reprise+enregistreur d’évènement (si requis)+ordonnanceur de points de reprise
PerformancesConditions expérimentales
Programmes étalons :
• NetPIPE : ping-pong MPI
• NAS Parallel Benchmark• CG : fort taux de communication, nombreux messages courts• SP, BT : taux de communication moyen, nombreux messages longs• FT : opérations collectives, messages de grande taille• LU : très grand nombre de messages de taille moyenne
43
Validation de MPICH-V : Points de reprises
BT.A.4 BT.B.1
44
Validation de MPICH-V : communications MPI
Latence 100Mb/s (1octet) (µs)
45
Validation de MPICH-V : performance d’application
46
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
47
Stratégies d’adjonction de causalitéPing-pong
½ sans causalité
48
Stratégies d’adjonction de causalitéQuantité de données de causalité
Données de causalité échangées (% total des messages)
49
Stratégies d’adjonction de causalitéTemps de manipulation de la causalité
50
Stratégies d’adjonction de causalitésPerformance d’applications
51
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
52
Comparaison des protocolesPing-pong
53
Comparaison des protocolesPerformance d’applications 1/2
LU : enregistrement sur l’émetteur dépasse la capacité mémoire
54
Comparaison des protocolesPerformance d’applications 2/2
55
Comparaison des protocolesRésistance aux fautes
Coupe cohérente : plus performant hors faute
Enregistrement de message : plus performant à haute fréquence de fautes
Extrapolation : une application occupant 1Go de RAM par nœud, 200 nœuds par serveur de pt de reprise
Croisement = 1 faute / 10 heures
Causal améliore la latence par rapport à pessimiste, au prix d’une diminution du débit
56
• Le calcul hautes performances et les défaillances
• Introduction à la tolérance aux fautes
• Environnement MPICH-V
• Performances• Validation de l’environnement MPICH-V• Réduction des adjonctions de causalité• Comparaison des protocoles
• Cas des réseaux hauts débits – OpenMPI-V
57
Réseaux rapidesSupprimer les copies mémoires
• La performance des réseaux rapide est diminuée par les copies mémoires
• Supprimer les copies mémoires dans C&L est uniquement technique
• L’enregistrement de message impose une copie sur l’émetteur : sortir cette copie du chemin critique (diminution de latence)
• L’enregistrement de message suppose une livraison atomique : faux en réalité, impose une copie inutile changer le modèle
Séparation de la correspondance et de la livraison du message
La correspondance peut-être non déterministe (source non spécifiée)
58
Réseaux rapidesDéterminisme de la livraison
• Contrairement au modèle général, certaines livraisons sont déterministes dans MPI (enregistrement inutile)
• Fonctions d’accès au message livré : • Recv, Wait, WaitAll : livraison déterministe
• WaitAny : un des messages parmi un ensemble est terminé, lequel ?
• WaitSome : un ou plusieurs messages sont terminés, lesquels, combien ?
• Probe : un message est-il prêt à une date donnée ? Combien de fois n’est-il pas prêt ?
On enregistre deux évènements distincts pour un message : • La correspondance au début du message si il est sans source spécifiée
• Le résultat de l’opération de livraison
59
Réseaux rapidesArchitecture OpenMPI-V
• PML-V parasite le vrai PML et charge un « Vprotocol »
• Vprotocol remplace les fonctions d’interface
• Des BTL spéciaux communiquent avec l’enregistreur d’évènements, et enregistrent les messages sur l’émetteur
• Lors de la récupération, les messages sans source ont leur source spécifiée par l’enregistrement des évènements
• Le résultat des livraisons non déterministes est rejoué à l’identique
60
Réseaux rapidesPerformance ping-pong Myrinet
61
Réseaux rapides Performances OpenMPI-Vpessimist
• Aucune dégradation de performance pour les messages à source spécifiée
• Latence multipliée par 3 uniquement pour les messages sans source
• Pas de coût de copies mémoires
62
ConclusionsAlgorithmes adaptés pour le contexte du calcul numérique hautes performances
• Protocole par vue globale coordonnée (Chandy&Lamport)– Algorithme non bloquant pour les points de reprise– Enregistrement local et distant des points de reprise
• Enregistrement de messages pessimiste– Enregistrement de message distant décentralisé : protocole original– Enregistrement de message basé sur l’émetteur : traitement optimisé des messages en-transit
• Enregistrement de messages Causal– Première implémentation de l’algorithme LogOn– Nouvel algorithme paresseux
Environnement MPICH-V• Implémentation de 6 protocoles différents (Chandy&Lamport, 3 stratégies causal, 2 pessimistes)• L’environnement est validé expérimentalement
Comparaison de trois stratégies causales• Introduction d’un enregistreur d’évènements dans le protocole causal• La présence d’un support stable impacte plus les performances que le choix de l’algorithme causal
Comparaison de performances entre les protocoles• Avantage pour CL pour la performance hors faute• Avantage pour Pessimiste en terme de résistance aux fautes• Causal est un bon compromis
Réseaux rapides• Environnement « zéro copie » OpenMPI-V• Modification des hypothèses d’enregistrement de message pour traiter l’absence de copies• Détection des évènements déterministes : diminution du coût général de l’enregistrement pessimiste
63
Travaux futurs
• Collaboration avec les couches hautes de OpenMPI (opérations collectives) pour détecter les évènements non déterministes sémantiquement déterministes
• Enregistreur d’évènements décentralisé pour protocole causal
• Décentralisation de l’enregistrement des points de reprise (Reed-Solomon + incremental ckpt)
• Investigation : problème de passage à l’échelle structurel de la vague de synchro CL ? (Grid5000)
• Évaluation à grande échelle avec Grid5000, et comparaison dans OpenMPI-V de toutes les familles de protocoles (en particulier pour C&L)
64
Tolérance aux défaillancesdans les systèmes hautes performances
Grand Large
QUESTIONS ?