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

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






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


P0 P1 P2

P0

P1

P2C3 C1

m1m2

m5

C2

m4

m3

Ckpt

P0

19


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


P0

P1

P2

23


P0

P1

P2

24


P0

P1

P2

25


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






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






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






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






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






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 ?

Documents

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