Communications, Tolérance aux pannes, programmation

Communications, Tolérance aux pannes, programmationparallèle, communications, lanceurs

Grégory Mounié

2020

Grégory Mounié Communications, Tolérance aux pannes, programmation parallèle, communications, lanceurs2020 1 / 114

Outline

1 Couches de communications

2 Intergiciels par passage de message: MPI

3 Minimiser la latence et maximiser le débit

4 Modélisation des réseaux

5 Tolérance aux pannes

6 Exascale

7 Programmation parallèle

8 Programmation parallèle par tâches

9 Lanceurs


Couches de communications

Les couches de communications dans les middlewares

Trois grandes familles de middleware1 Ceux déclenchant une exécution de code à distance: RPC, RMI,

DCOM, DO, etc.2 Ceux utilisant des primitives de communications explicites (une

fonction SEND et une fonction RECV): Socket, MPI (cf plus en détailplus tard), ZeroMQ, etc.

3 Ceux, asynchrone, �abilisant chaque message (un peu comme lesEmail): les MOM (RabbitMQ, AMQP)



Utiliser des nouveaux protocoles ?

2 idées de base d'internet1 Datagramme (réseau stupide) (Merci Louis Pouzin)2 Modèle en couche (OSI)

IPv4 legacy

Il est di�cile de mettre en place de nouveau protocole à cause des NAT quise sont généralisés pour palier au manque d'adresses IPv4, et les pare-feuparanoïaques

Nouveaux protocoles (depuis les environs de 2010)

SCTP, TCP avec la notion de messages et de multi-chemins

DCCP, UDP avec controle de congestion

QUICK, (over UDP), réduire la latence en https: échange de clef àl'ouverture, crypto par paquet, multi-chemin.



Propriétés des protocoles des intergiciels

2 grandes propriétés des protocoles haut niveaux

1 persistant ou transitoire2 asynchrone ou synchrone



RPC: remote procedure call (synchrone, transitoire)

programmation similaire à un appel séquentiel

emballage/déballage

gestion des erreurs

génération de talons à partir d'un IDL

support interne à certains langages (eg. Java)



Exemple de code RPC, coté client

public class Client {

private Client() {}

public static void main(String[] args) {

String host = (args.length < 1) ? null : args[0];

try {

Registry registry = LocateRegistry

.getRegistry(host);

Echo stub = (Echo) registry.lookup("Echo");

String response = stub.sayEcho("Hi, Echo !");

System.out.println("Response: " + response);

} catch (Exception e) {

System.err.println("Client exception: "

+ e.toString());

e.printStackTrace();

}}}



Extension de RPC

RPC asynchrone

Réponse immédiate: il faudra donc prévenir de la �n plus tard !

Mécanisme de callback utilisant RPC !

Multicast RPC

Cela peut être fait à l'insu du client, mais il faut faire attention auxréponses.



Message-oriented communication

Il existe de nombreuses abstactions. Nous allons discuter brievement des:

les sockets (coté OS)

ZMQ

MPI (plus tard dans ce cours)

MOM

Multicast



L'abstraction de base: les Sockets (synchrone, transitoire)

L'abstraction universelle de base dans les réseaux de communications. Trèsbas niveau (Endianness). Souple: multi-protocole, multi-réseaux. API assezproche des API �chiers (open/read/write/close).

Opérations de base (TCP):

préparation socket, bind, listen,

connection accept, connect

échange send, recv

fermeture close, shutdown



Messaging Pattern: ZeroMQ (asynchrone connecté,transitoire)

Implantation de patrons (patterns) de communications de haut niveau(TCP, comme les sockets) (one-to-many et many-to-one):Connexion asynchrone mais orienté connexion (au sens TCP):

l'emmetteur peut envoyer un message avant que le récepteur n'aitdémarré !

On peut démarrer le client avant le serveur !

le principe est de faire un appariement de socket. Les types des socketsappariés dé�nit l'opération



Exemple de code (origine: https://zeromq.org)

#include <zmq.h>

int main (void)

{

void *context = zmq_ctx_new ();

void *requester = zmq_socket (context, ZMQ_REQ);

zmq_connect (requester, "tcp://localhost:5555");

int request_nbr;

for (request_nbr = 0; request_nbr != 10; request_nbr++) {

char buffer [10];

zmq_send (requester, "Hello", 5, 0);

zmq_recv (requester, buffer, 10, 0);

}

zmq_close (requester);

zmq_ctx_destroy (context);

return 0;

}Grégory Mounié Communications, Tolérance aux pannes, programmation parallèle, communications, lanceurs2020 12 / 114

https://zeromq.org


ZMQ: trois principaux patrons

request-reply (socket REQ (client) et socket REP (serveur)) (similaire auxsockets classiques)

publish-subscribe publication d'évènement auprès d'abonnées (multi-castsocket PUB (serveur), socket SUB (client)

pipeline (sockets PUSH et PULL)



Message-oriented persistent communication (AMQP,RabbitMQ) (asynchrone, persistant)

Message oriented Middleware ou message queuing systems

(Image: https://rabbitmq.com)


https://rabbitmq.com


Construction du graphe de l'application

Des �les d'attente de messages persistants

Avec des messages persistants dans les �les d'attente, client et serveurpeuvent être très asynchrones.

Des queues manager s'occupe du routage

et de la réécriture des messages entre les queues locals.

Les queues managers sont connectés par des channels

dont les extrémités sont gérées par des MCA (Message channel agent)

La topologie est un overlay

du réseau liant les queues managers est un overlay network consistant.



Multicast communications (transitoire, synchrone)

Trois grandes familles de communications par multicast, en fonction de laméthode

1 Routage par un arbre couvrant sur un réseau overlay2 routage par inondation

I Possibilité de réglage en limitant la probabilité d'émission à chaque

voisin.

3 Gossip base (bavardage): tirer un voisin au hasard et échanger avec luiles informations dans les deux sens. (tirer, quand l'information est peurépandue, ne sert à rien; pousser quand l'information est trèsrépandue, ne sert à rien)


Intergiciels par passage de message: MPI

Programmation distribuée par passage de message

Le point di�cile lors de la programmation distribuée, est la gestion de ladistribution et des communications. Des bibliothèques/API comme MPIpermettent de programmer les applications avec le paradigme simple àcomprendre du passage de message.L'utilisation conjointe d'autres abstractions est courante (OpenMP, Cudaou OpenCL): multi-threading ou gestion des accélérateurs.



Le passage de message

Le paradigme consiste à écrire dans le code séquentiel exécuté par chaquenoeud, et explicitement les communications (envoi ou réception) qu'il doitréaliser pour faire correctement le calcul.

Exemple simpli�é

Sur le noeud 0

int tableau[3] = {1,2,3};

int destinataire=3;

Calcul(tableau, 3);

Envoyer(tableau, 3, INT, destinataire);



Le passage de message (suite)

Sur le noeud 3

int tableauCalcule[3] = {};

int emetteur=0;

Recevoir(tableauCalcule, 3, INT, emetteur);

ContinuerCalcul(tableauCalcule, 3);



MPI, Message Passing Interface

MPI est un standard dé�nissant l'API de fonctions permettant d'implanterdes applications parallèles avec passage de message.Le standard ne dé�nit pas les opérations de gestion (lancement del'application parallèle). Elles peuvent varier d'une implantation à l'autre.Implantations couramment utilisées: http://www.open-mpi.org (exLAM-mpi) et MPICH http://mpich.org.


http://www.open-mpi.org

http://mpich.org


Un peu d'histoire Histoire

L'API est dé�nie pour C (et donc C++ et al.) et Fortran.Elle est la somme de l'expertise des concepteurs autour de l'écriture debibliothèques d'échange de message (1980-1994, 1996 pour MPI-2, 2014pour MPI-3.0, MPI-4 en cours).MPI permet:

la portabilité (standard),

l'exploitation des performances des communications au plus près dumatériel,

Elle fournit de nombreuses fonctionnalités et est disponible presquepartout.



Mémoire distribuée vs mémoire partagée

MPI a été conçu pour des architectures à mémoire distribuée, tout enétant compatible avec une utilisation en mémoire partagée.

Elle a évolué pour faciliter l'exploitation de multi-c÷ursinter-connectés.

Elle supporte aussi l'hétérogénéité des processeurs (verbeux) et ladynamicité (dépend de l'implantation)



Exemple: Hello world en MPI

#include <mpi.h>

int main(int argc, char **argv) {

MPI_Init(& argc, &argv);

printf("Hello world !\n");

MPI_Finalize();

}



Compilation

1 mpicc -o hello hello.c

2 mpirun -np 1000 ./hello # et hop ! 1000 Hello !

3 mpirun -np 1000 --hostfile listedemachines ./hello



Nommage des processus

Pour pouvoir di�érencier les calculs fait par chaque n÷ud, il faut pouvoirles nommer.Tous les processus lancés ensemble appartiennent à un même groupe(Communicateur). Le communicateur par défaut est MPI_COMM_WORLDDeux fonctions permettent d'obtenir la taille et le rang dans lecommunicateur.



Hello world et nommage

#include <mpi.h>

#include <stdio.h>


int taille, rang, len;

char hostname[MPI_MAX_PROCESSOR_NAME]={};


MPI_Comm_size(MPI_COMM_WORLD, &taille);

MPI_Comm_rank(MPI_COMM_WORLD, &rang);

MPI_Get_processor_name(hostname, &len);

printf("Hello world %d parmi %d sur %s!\n", rang, taille, hostname);

MPI_Finalize();

}

L'a�chage est dans le désordre. Il dépend de l'ordonnancement desprocessus lancés.



Mesure du temps écoulé

double MPI_Wtime();

double debut = MPI_Wtime();

...

double fin = MPI_Wtime();

printf("Temps ecoule %g\n", fin - debut);

double MPI_Wtick(); (tick)

La précision de la mesure est disponible en utilisant la fonction de la lignetick.



Nombreuses formes de communications

MPI propose de nombreuses variantes pour les communicationspoint-à-point (un processus émetteur et un processus récepteur) oucollectives.Pour une communication point-à-point, l'algorithme utilisé sera: dépendantde l'implémentation (défaut); avec tampon; réception déjà prête;synchrone; mono-directionel.Toutes les variantes (point-à-point et collectives) existent en versionincomplète (commencer la communication de suite, mais attendre sa �nplus tard).



MPI_Send / MPI_Recv

// envoi de 10 float

float tableau[10];

int recepteur; int TAG=123456;

...

MPI_Send(tableau, 10, MPI_FLOAT,

recepteur, TAG,

MPI_COMM_WORLD);

// réception de 10 float

float tableauR[10];

MPI_Status status; int emetteur;

...

MPI_Recv( tableauR, 10, MPI_FLOAT,

emetteur, TAG,

MPI_COMM_WORLD, &status);



Sémantique

MPI_Send() et MPI_Recv() sont bloquants jusqu'à ce que les

données puissent être réutilisée,

MPI_Recv() est donc bloquant jusqu'à la réception du message,

MPI_Send() est bloquant jusqu'à ce que l'envoi ou la copie desdonnées (dépend de l'implémentation).



Exemple/début du TP MPI

Anneau à jeton

Les processus font une ronde. Chaque processus envoie un entier (le jeton)au processus suivant, sauf le 0, qui initie et termine le tour.

l'initialisation#include <mpi.h>

#include <stdio.h>


int taille, rang, hostlen;

char hostname[MPI_MAX_PROCESSOR_NAME]={};

double message=42.0;

int TAG = 123456;

MPI_Status status;




Exemple

La boucle: le n÷ud 0, qui démarre la boucle et la termine

MPI_Comm_size(MPI_COMM_WORLD, &taille);

MPI_Comm_rank(MPI_COMM_WORLD, &rang);

MPI_Get_processor_name(hostname, &hostlen);

if (rang == 0) {

MPI_Send(& message, 1 , MPI_DOUBLE,

(rang + 1)%taille, TAG, MPI_COMM_WORLD);

MPI_Recv(& message, 1, MPI_DOUBLE,

(taille - 1), TAG, MPI_COMM_WORLD, & status);

printf("Message %g reçu ! %d parmi %d sur %s!\n",

message, rang, taille, hostname);

}



Exemple

La boucle: le n÷ud 0, qui démarre la boucle et la termine

else {

MPI_Recv(& message, 1, MPI_DOUBLE,

(rang - 1), TAG, MPI_COMM_WORLD, & status);

printf("Message %g reçu ! %d parmi %d sur %s!\n",

message, rang, taille, hostname);

MPI_Send(& message, 1 , MPI_DOUBLE,

(rang + 1)%taille, TAG, MPI_COMM_WORLD);

}

MPI_Finalize();

}



Variation utile: Joker en réception

MPI_Recv( tableauR, 10, MPI_FLOAT,

MPI_ANY_SOURCE, MPI_ANY_TAG, // jokers

MPI_COMM_WORLD, &status);

status.MPI_SOURCE; // rang de la source

status.MPI_TAG; // TAG du message reçu



Pourquoi avoir plusieurs types de communications 1/2

Exemple: tous les processus échangent avec le processus 0

if (rang != 0) {

MPI_Send(donnees, nb, MPI_DOUBLE, 0, TAG, MPI_COMM_WORLD);

MPI_Recv(donnees, nbR, MPI_DOUBLE, 0, TAG, MPI_COMM_WORLD, & status);

} else {

for(int dest =1; dest < taille; dest++, donnees += nbR) {

MPI_Send(donnees, nb, MPI_DOUBLE, dest, TAG,

MPI_COMM_WORLD);

MPI_Recv(donnees, nb, MPI_DOUBLE, dest, TAG,

MPI_COMM_WORLD,

& status);

}

}



Pourquoi avoir plusieurs types de communications ? (2/2)

Seul le programmeur, connaissant le contexte global, peut prendre lesdécisions en liens avec la performance et l'utilisation de la mémoire.

Si Send envoie les données lorsque la réception est prête

Il faut attendre un aller-retour du réseau ⇒ Perte de performance

Si Send envoie les données dès qu'il commence

Le récepteur devra stocker les données et peut donc saturer sa mémoire.



Envoi et Réception Asynchrone

MPI permet de démarrer des communications puis d'attendre plus tard leur�n (y compris envoi et collective)

Exemple de réception asynchrone

MPI_Request req;

MPI_Status status;

MPI_IRecv(donnees, nb, MPI_INT,

emetteur, TGA, MPI_COMM_WORLD, &req);

...

MPI_Wait(&req, &status);

Autres fonctions de tests

MPI_Test(), MPI_Testall(), MPI_Testany(), MPI_Testsome(),MPI_Waitall(), MPI_Waitany(), MPI_Waitsome(), MPI_Probe()



Envoi synchrone

L'envoi terminera après le début de la réception

Exemple d'envoi synchrone

MPI_Ssend(donnees, nb, MPI_INT,

destinataire, TAG, MPI_COMM_WORLD);



Envoi tamponné

Les données seront copiées dans un tampon intermédiaire. Très utile pouremballer des structures complexes.

Exemple d'envoi tamponné (similaire à printf)

Cela à un coût non négligeable par rapport à une transmission avec 0 copie,mais permet de réutiliser les données en mémoire rapidement.

MPI_Buffer_attach(& buffer, taille);

for(int i=0; i< nb_accumulation; i++) {

MPI_Bsend(donnees, nb, MPI_INT,


}

// forcer l'attente de la fin des envois

MPI_Buffer_detach(& buffer, taille);



Envoi et réception simultanée

Le code d'échange précédent mais avec deux tampons di�érents.

Exemple d'échanges simultanée

if (rang != 0) {

MPI_Sendrecv(donnees, nb, MPI_DOUBLE, 0, STAG

donnees2, nb2, MPI_DOUBLE, 0, RTAG,

MPI_COMM_WORLD, & status);

} else {

for(int dest =1; dest < taille; dest++, donnees += nbR) {

MPI_Sendrecv(donnees, nb, MPI_DOUBLE, dest, STAG,

donnees2, nb2, MPI_DOUBLE, dest, RTAG,

MPI_COMM_WORLD, & status);

}

}



Envoi prêt (ready) à être reçu

Le programmeur indique que la réception est déjà place. MPI peut doncenvoyer le message sans délai, sans crainte de saturer la mémoire durécepteur.

Exemple d'envoi indiquant que la réception est déjà prête

MPI_Rsend(donnees, nb, MPI_INT,




Communications collective

Exemple de communications collectives

MPI_Barrier(MPI_COMM_WORLD);

MPI_Bcast(donnees, 20, MPI_INT, root, MPI_COMM_WORLD );

MPI_Scatter(donnees, 20, MPI_INT,

donneesR, 20, MPI_INT,

root, MPI_COMM_WORLD);

MPI_Gather(donnees, 20, MPI_INT,



MPI_Allgather(donnees, 20, MPI_INT,



MPI_Reduce(donnees, donneesR, 20, MPI_INT,

MPI_MAX, root, MPI_COMM_WORLD);

// OP: MPI_MAX, MPI_SUM, MPI_PROD, etc.



Collectives asynchrones

Elles existent aussi en version asynchrone depuis MPI-3.

Exemple de deux communications collective asynchrones et attentesimultanée

// [exemple tiré des slides du MPI BOF 2019-06]

for (i= 0; i< MAXITER; i++) {

compute(bufA);

MPI_Ibcast(bufA, ..., rowcomm, &req[0]);

compute(bufB);

MPI_Ireduce(bufB, ..., colcomm, &req[1]);

MPI_Waitall(2, req, ...);

}



Construction de type dérivé

les types de bases

MPI_CHAR, MPI_WCHAR, MPI_SHORT, MPI_INT, MPI_LONG,

MPI_FLOAT, MPI_DOUBLE, MPI_BYTE; // etc.

Pour une structure

struct T { int a; float b; };

T tmp;

int nb=2;

int len[2] = {1, 1};

MPI_Aint indices[2] = { (&tmp.a) - (&tmp), (&tmp.b)-(&tmp) };

MPI_Datatype old[2] = { MPI_INT, MPI_FLOAT };

MPI_Datatype new;

MPI_Type_struct( nb, len, indices, old, & new );



Performance: scrutation, interruption et réseaux rapide(1/3)

Les communications sur les réseaux rapides sont délicates à utilisere�cacement.Faire un appel système, ou une interruption, coûte des dizaines de milliersde cycle (∼ la latence des réseaux rapide (µ secondes)).




Scrutation (Polling)

Interroger régulièrement la carte réseau est

d'un coût unitaire faible (aller-retour sur le bus, quelques dizaines decycles)

un travail inutile si rien ne s'est passé

Interruption

La carte réseau arrête le travail d'un c÷ur en cours lors de l'arrivée d'unmessage

coût unitaire important (dizaines de milliers de cycle)

pas de travail inutile




En pratique, on fait souvent les deux

Les pilotes scrutent un moment le périphérique, puis s'endorment s'il n'y arien à faire pendant trop longtemps.

Scrutation/Interruption

Problème récurrent non-résolu dans de nombreux contextes: pilote de carteréseaux, environnement de programmation multi-threadés, pilote desaccélérateurs.



One core to rule them all

Réserver un c÷ur pour la communication avec un périphériqueparticulier

Réserver un c÷ur pour discuter la carte de communication avec le GPU oua�n de maximiser le débit, et la réactivité.



One Linux kernel to rule them all: FUGAKU

158,976n÷uds.

Fugaku, comme tous les supercomputer du top500 tourneLinux. Le noyau s'occupe de la gestion du matériel et desentrées-sorties.Mais, l'idée originale est que le noyau Linux n'utilise qu'unnombre restreint des c÷urs d'un noeud. Les autres c÷ursexécutent un noyau ultra-léger (McKernel)), mono-thread,sans préemption, ni appel système (donc pas de surcoût, nide perturbations, interruptions, pollution ou vidanges descaches, lors des calculs.).Le McKernel renvoie les requêtes systèmes au noyau Linux.Comme la mémoire d'un n÷ud est partagé, il n'a pas dedi�culté à lire ou écrire les données dans les variablesmanipulées par un thread quelconque s'exécutant sur unMcKernel.


Minimiser la latence et maximiser le débit

Performance des communications

Puisque les communications entre les hôtes passent par un réseau, laqualité du réseau a un impact direct sur les performances.

Impact direct sur la facilité de programmation

grain de calcul

Deux critères dominants

la bande passante (débit)

la latence (le temps d'acheminer le premier octet)

Mais d'autres critères existent: full-duplex, 1-port, bande passante du fondde panier dans les routeurs, �abilité du partage, �abilité du routage,optimisation diverses.



Comment se passe un transfert entre deux processusdistants (Unix classique)

1 appel système (write): interruption2 copie des données dans les tampons du système3 emballage dans la pile IP4 copie dans la mémoire de la carte5 envoi6 réception sur la carte7 copie dans un tampon système8 interruption9 copie dans la mémoire du processus (read)10 retour d'interruption



Transfert en zéro copie

1 ordre et envoi de la mémoire vers la carte2 envoi3 copie dans la mémoire du processus qui boucle en attendant cette

écriture



Problèmes à résoudre

Un processus travaille avec ses adresses virtuelles, la carte travailleavec les adresses physiques.

C'est le système qui contrôle la position physique d'une page. Il peutla déplacer ! (ex. Huge Page)

On vérrouille (pin) donc la mémoire (mais la taille de la mémoireverouillable est limitée)



Parfois on a besoin de copies

Il est plus e�cace de copier un bloc contigu de données que des donnéeséparpillées dans la mémoire (iovec)



Certaines optimisations du matériel

Elles ne sont pas toujours évidentes à détecter et à interpréter.

Transfert de gros �chiers sur le même réseau Ethernet

Comment di�user un �chier vers un ensemble de machines sur le mêmeréseau Ethernet ? Ré�échissez à une stratégie.



Transfert de gros �chiers sur le même réseau Ethernet

Les switches (et la pile TCP) sont optimisés pour les transferts réguliers.Ils possèdent parfois des optimisations dédiées aux gros transferts.En pratique, souvent, il vaut mieux discuter toujours avec le mêmeinterlocuteur dans un sens donné. La meilleure topologie est donc la chaîne(pipeline).


Modélisation des réseaux

le modèle Délai

Le modèle Délai

T = β + Lτ : le temps d'arrivée du message entier

β le délai

τ le débit

L la longueur du message

Il n'y a pas de limite dans le modèle sur l'envoi, ou la réception, simultanéede plusieurs messages.

Mesure des constantes

Comment mesurer les paramètre ? Indiquez les mesures à faire et commenten déduire les paramètres du modèle.Grégory Mounié Communications, Tolérance aux pannes, programmation parallèle, communications, lanceurs2020 57 / 114


Mesure du modèle délai

Pour mesurer β, c'est la moitié du RTT d'un message de taille nulle.Pour τ , il faut envoyer un deuxième message de taille su�sante pour endéduire le débit.



LogP 1/2

Inonvénient du modèle délai

Le modèle délai précédent ne tient aucun compte du coût de calcul associéà l'envoi ou la réception d'un message. Il ne tient pas compte non plus dela capacité limitée en sortie des émmetteurs.Pour les réseaux rapides, le débit est di�cile à saturer et comme leslatences sont petites, les coûts de calculs associés aux communications nesont pas négligeables.



LogP (2/2)

le modèle LogP

Modèle pour des messages de taille uniforme.

L temps de transfert d'un message entre deux hôtes

o temps de calcul de la préparation et réception d'un message

g temps entre deux émissions des messages (bande passente desortie de l'émetteur sur les réseaux rapides)



Mesure des paramètres de LogP

Mesure

Temps de transfert d'un message

Comment mesurer o ? directement dans le programme

Comment mesurer L ? En mesurant le RTT et en soustrayant o

Comment mesurer g ? En envoyant plusieurs messages à la suite, poursaturer le réseau, et en mesurer le gap.



Exemple de la mesure du débit d'un réseau TCP

L'importance des mécanismes de crédit à la TCP

Example (1 paquet de 64Ko)

On envoie un paquet de 1o et l'on reçoit en retour un paquet de 1o. Onmesure le temps d'aller-retour RTT1. On envoie un paquet de 64ko et l'onreçoit en retour un paquet vide. On mesure le temps d'aller-retour RTT64k .Quelle est la latence et la bande passante du réseau ?



De l'importance des mécanismes de crédit à la TCP

Le problème du min-max (chaîne coupée par plusieurscommunications)

On pénalise toutes les communications pour en faire passer une seule. Pourmaximiser la bande passante, on devrait laisser une bande passante de 0 àla communication transverse. En fait on cherche plutôt de l'équitéproportionnelle (on maximise le produit des débits).( x*(1-x)n )' = (1-x)n - (1-x)(n-1)



Ré�exions avec un réseau In�niband (crédit dans les réseauxrapides)

Les réseaux rapides ont un besoin vital de mécanismes de contrôle de �ux.Du coup, les interférences entre communications deviennent complexes.

Un modèle simple, et �uide (continu), d'un réseau In�niband.

Dans les réseaux locaux à très haut débit, comme In�niband, il faut régulerles �ux au niveau de la couche {Liaison} par des mécanismes de crédits(comme TCP). Sinon, à cause des vitesses de transferts, les tamponsmémoires des cartes réseaux déborderaient très rapidement.



Deux grandes di�érences avec les crédits de TCP

1 Les échelles de temps sont beaucoup plus petites. Le contrôle de �uxpeut alors être modélisé comme celui d'un �uide continu.

2 Les communications de données sont unidirectionnelles, mais il fautpouvoir faire passer un grand nombre de messages de crédits dansl'autre sens pour pouvoir maintenir le débit.

I Le partage du débit est en fait réalisé comme si les communications

étaient bidirectionnelles: il faut demander des crédits en même temps

que le transfert e�ectif.



Modélisation d'un réseau In�niband

Nous allons donc modéliser le réseau par un modèle obéissant aux règlessuivantes:

La somme des débits entrants et sortants d'un noeud est plus petiteou égale à 1.

L'allocation des crédits est partagée proportionnellement auxdemandes. Les demandes sont partagées uniformément. Suivant lagéométrie des demandes entre les noeuds, il va y avoir des variationsillustrées sur les exemples suivants:



Exemples I

Le noeud B obtient une bande passante de 1 vers le noeud A.

A 1 B

Le noeud B utilise la moitié de sa bande passante pour aller vers A etl'autre moitié pour aller vers C.

A12 B

12 C



Exemples II

Le noeud C ne demande des crédits à B que la moitié du temps. Ademande des crédits à B tout le temps. B alloue donc ses crédits avec unerépartition de 3/4 (1 pendant la moitié du temps + 1/2 pendant la moitiédu temps) versus 1/4 (1/2 pendant la moitié du temps).

A34 B

14 C

12 D

NB: La bande passante de C n'est pas saturée. La bande passante estlimitée par le minimum entre la bande passante d'émission et la bandepassante de réception.



Exercice I

Quelles vont être les bandes passantes des liens pour les géométriessuivantes ?

A B C

Solution

1/2; 1/2



Exercice I


A B C

Solution

1/2; 1/2



Exercice II

AB

C

D

Solution

1/3; 1/3; 1/3



Exercice II

AB

C

D

Solution

1/3; 1/3; 1/3



Exercice III


A B C

DE

Solution

B vers D et C: 1/3; B vers A: 1/6; E vers A: 2/3+ 1/6 = 5/6;



Exercice III


A B C

DE

Solution

B vers D et C: 1/3; B vers A: 1/6; E vers A: 2/3+ 1/6 = 5/6;



Exercice IV

A B C

DE

Solution

B vers A et C: 1/4; E vers A et D vers C: 1/2+ 1/4 = 3/4



Exercice IV

A B C

DE

Solution

B vers A et C: 1/4; E vers A et D vers C: 1/2+ 1/4 = 3/4



Exercice V


A B C

DE



Exercice V (solution)

B se découpe en 2 demi: il demande donc à A pendant 1/2 du tempstandis que E demande à A pendant 1/2.

E vers A: 1/2 ∗ 1/2 ∗ 1/2+ 1 ∗ 1/2 ∗ 1/2 = 3/8;

B vers A: 1 ∗ 1/8 ∗ 1/2+ 1/2 ∗ 1/2 ∗ 1/2+ 1/3 ∗ 1/4 ∗ 1/2 = 11/48;

E vers B:1∗1/8∗1/2+1/3∗3/8∗1/2+1/2∗3/8∗1/2+1/4∗1/8∗1/2 = 15/64



Exercice VI

A B C

D



Exercice VI (solution)

B se découpe en 3 tiers: il demande donc à A pendant 1/3 du temps tandisque D demande à A pendant 1/2, mais il reçoit des messages de B pendant1/3 du temps.B vers A: 1 ∗ 1/2 ∗ 1/3+ 1/2 ∗ 1/2 ∗ 1/3 = 1/4 B vers D:1 ∗ 1/4 ∗ 1/3+ 1/2 ∗ 1/2 ∗ 1/3+ 1/3 ∗ 1/4 ∗ 1/3 = 7/36 D vers A:1/2 ∗ (2/3− 1/9) ∗ 1/2+ 1 ∗ (1/3+ 1/9) ∗ 1/2 = 13/36


Tolérance aux pannes


Motivation

Lorsque l'on fait un calcul sur un PC pendant quelques secondes, laprobabilité de panne est faible, et souvent négligée.

Lorsque le calcul est long (plusieurs mois) et/ou lorsqu'il utilise ungrand nombre de machine, l'occurence d'une panne devient quasicertain.




Problème du nombre

Un objet avec un temps moyen avant panne de 10 ans.

1000 objets une panne tous les 3 jours;

10000 objets 3 pannes par jour;

1000000 objets 1 panne toutes les 5 minutes.

Et il y a plusieurs objets dans chaque ordinateur: processeurs, disques durs,alimentation, chaque cellule de chaque barrette mémoire ou disque SSD.



But de la tolérance aux pannes

Vivre avec les pannes

Le but n'est pas d'empêcher les pannes. Le but est de réussir à vivre avec.



Stratégies généralistes

Duplication répliquer les éléments pour obtenir des résultats avec une plusgrande probabilité

Détection et contournement savoir que l'on a une panne et prendre desmesures pour la contourner (poursuite ou compensation)

Points de reprises enregistrer les états intermédiaires sur un support stableet être capable de repartir de ces états



Détection par senseur

Heartbeat

Émettre régulièrement un message pour informer ses voisins que l'on estvivant.Variation : envoyer régulièrement une requête et en attendre une réponse.

Suspect

En cas de non réception des messages attendus, le processus est suspecté.



Senseurs Implicites

Example (Détection)

Il existe de nombreux cas où des tests de fonctionnement font partie duprocessus

Le nettoyage des processus sur une machine à distance teste:l'alimentation électrique, le réseau, le noyau, le système de �chier(clefs ssh)

Les protocoles réseaux à di�usion régulière d'information (exemple enroutage: RIP, BGP, OSPF) mettent un délai de garde sur les données.



Types et propriétés des détecteurs

♦S , ♦PLes détecteurs les plus courant visent deux propriétés

Complétude la défaillance �nie un jour par être détectée par tous lesprocessus corrects

Justesse/Accuracy il existe un instant à partir duquel tous les processuscorrects (♦P) ne seront pas suspectés, ou au moins 1processus correct (♦S) ne sera pas suspecté.



Points de reprise

Deux di�cultés intrinsèques à la méthode :1 où faire l'enregistrement de l'état ?2 que faut-il enregistrer pour pouvoir reprendre ?

Hypothèse du support stable

Les mécanismes utilisent un support dit stable

Algorithme de snapshot

L'enregistrement des calculs est souvent laissé à l'application quiconnait les données nécessaires et su�santes.

NB: Il faut aussi enregistrer les messages en transit !



Critique et coûts des points de reprise

Écrire les données sur un disque prend beaucoup de temps (un disquec'est lent)

le support stable n'est pas toujours stable, surtout si on le stresse avecdes écritures simultanées

L'écriture à distance va utiliser le réseau pendant des bursts

Un compromis est à trouver entre le nombre de points de reprises et laquantité de travail perdu un cas de panne.



Recursive doubling

Si l'on ne connaît pas le temps de calcul, on peut faire croître l'écarttemporel entre les points de reprises de manière géométrique.

Recursive doubling

Avec un multiplicateur ×2, on ne peut pas perdre plus de la moitié deson travail.

le nombre d'enregistrement est proportionnel au logarithme du tempsde calcul



Duplication

On peut faire les mêmes calculs sur plusieurs machines

Il faut être capable d'agglomérer les résultats.

Cela diminue la puissance de calcul

Cela augmente la consommation énergétique


Exascale

Vers l'Exascale

Pour passer à plusieurs millions ou dizaines de millions de machines onaugmente encore la di�culté.La tolérance aux pannes est l'un des véritables challenges à résoudre pouratteindre une puissance de calcul de 1 Exa�ops


Exascale

Energie

L'autre challenge de l'exascale est l'e�cacité énergétique.Quand on est riche, on peut éventuellement construire une tranche decentrale nucléaire et mettre 10\calculateur, mais plus c'est compliqué.

Passage à des technologies moins énergivores

montée en puissance des puces ARM

calculateurs vectoriels programmables: les GPGPU des cartes ou despuces graphiques.

SSD

Réseaux ???


Programmation parallèle

Lancer de rayons (Ray tracing)



L'exemple d'un ray-traceur décortiqué (similaire à l'exemplesur la page du cours)

un �chier avec une scène à lire

Un nid de deux boucles indépendantes

l'écriture des pixels dans un �chier d'image



Implantation en MPI

1 réplication de la lecture du �chier2 Parallélisation des calculs indépendants3 écriture séquentielle dans un �chier



Variante statique

Répartir, les lignes ou les pixels en fonction du numéro de la machine

relativement simple, aux erreurs d'arrondis près

performance sensible à la charge des machines



Variante dynamique

Répartir les lignes, bloc ou pixel avec un maître-esclave

Schéma générique de l'esclave

esclave () {

demander_travail();

while(1) {

recevoir_message();

if (message_fini) break;

faire_boulot();

envoyer_result_demander_travail();

}

}



Variante dynamique

Répartir les lignes, bloc ou pixel avec un maître-esclave

Schéma générique du maître

void maitre () {

while( nbfini < M ) {

recevoir_message();

if ( message_avec_resultat() ) {

sauver_ecrire_resultat();

}

if ( reste_du_boulot() )

envoyer_boulot();

else {

envoyer_message_fini();

nbfini ++;

}

}

} Grégory Mounié Communications, Tolérance aux pannes, programmation parallèle, communications, lanceurs2020 95 / 114


Recouvrement calcul communication

Si la latence n'est pas négligeable face au calcul mais que la bandepassante est importante, alors on peut recouvrir le temps decommunication par du travail:

en donnant (ou en a�ectant statiquement) du travail aux esclaves audébut: risqué en cas de panne, il faut être capable de détecter que dutravail n'est pas fait, par exemple en le dupliquant dans la �le. Il fautalors tracer ce qui est fait.

Un esclave peut demander du travail avant d'avoir �ni (idéalement 1RTT+transfert avant la �n). cela peut demander de gérer une �lelocale de travail à faire.



MPI + threads

Avec des communications réseaux ou même entre processus sur la meemachine, il y a un coup important de calcul. On peut éviter lescommunications sur un même noeud en utilisant en parallèle des threads



Multi-coeur avec OpenMP

gcc -std=gnu11 -fopenmp loop_openmp.c

#include <omp.h>

#include <stdio.h>

int main(int argc, char ** argv) {

int tid, i, j;

#pragma omp parallel private(tid)

{

tid = omp_get_thread_num();

printf("coucou de %d\n", tid);

}



nid de boucle (suite)

#pragma omp parallel private(tid, i, j)

{

#pragma omp for schedule(dynamic, 2) nowait

for(int i=0; i < 10; i++)

for(int j=0; j < 10; j++)

{

int tid = omp_get_thread_num();

printf("coucou de %d (%d, %d)\n", tid, i, j);

}

}

}


Programmation parallèle par tâches

Les tâches

Pour obtenir des performances il faut être capable de décrire les calculs, lesdonnées et leurs liaisons.L'outil généraliste pour cela est le graphe de tâche.Pour aller encore plus loin, il faut séparer les données et les calculs pourobtenir un graphe data-�ow.



Fibonnacci

Exemple récurrent simple (pour être plus réaliste il faudrait une versionavec cuto�)

#include <stdio.h>

fibo(int n) {

if (n < 2) return 1;

return fibo(n-1) + fibo(n-2);

}

int main() {

print("fibo : %d\n", fibo(10) );

}



Les tâches dans les languages courant

On trouve des tâches parallèle dans les langages courants: Ada (je mens unpeu), Ruby (ici aussi), C++-11 + Boost-threads, Gopackage main

import fmt "fmt"

func fibo(n int, r chan int) {

if n < 2 {

r <- 1;

return;

}

var res1 chan int = make(chan int)

var res2 chan int = make(chan int, 1)

go fibo(n - 1, res1)

fibo(n - 2, res2)

r <- ( <- res1 + <- res2 )

} Grégory Mounié Communications, Tolérance aux pannes, programmation parallèle, communications, lanceurs2020 102 / 114


Fibo go (suite)

func main() {

var r chan int = make(chan int)

go fibo(15, r)

fmt.Printf("%d en %d call \n", <- r, nbc)

}



Multi-coeur: OpenMP

#include <stdio.h>

long comp_fib_numbers(int n)

{

long res1, res2, fn;

if ( n < 2 ) return 1;

#pragma omp task shared(res1)

res1 = comp_fib_numbers(n-1);

#pragma omp task shared(res2)

res2 = comp_fib_numbers(n-2);

#pragma omp taskwait

return fnm1 + fnm2;

}



Fibo OpenMP (suite)

int main(int argc, char **argv)

{

int result

#pragma omp parallel

{

#pragma omp single nowait

{

result = comp_fib_numbers(10);

} // end of single region

} // end of parallel region

printf("finonacci(%d) = %ld\n", n, result);

return 0;

}



Distribuée: Chapel

Langage développé par CrayPermet un parallélisme implicite (tableau parallèle), explicite (forall à laopenMP) ou par tâche.Il fonctionne en distribuée ! (compilation vers une cible C + MPI)



Fibonnacci en Chapel

def FiboParallel(n : uint) : long {

if(n<=1) then return n;

var a,b :long;

cobegin {

a = FiboParallel(n-1);

b = FiboParallel(n-2);

}

return a + b;

}


Lanceurs

Exemple de Taktuk

Qu'est ce qu'un lanceur parallèle

Le but est de démarrer le plus rapidement possible un ensemble d'activité(processus) sur un ensemble de machines.

Problème: comment recouvrir calcul et communication

Le coût de calcul de l'authenti�cation (crypto ssh) n'est pas négligeable, etles nombreuses communications (réseaux, TCP) non plus.


Lanceurs

Mesure du temps d'exécution

On peut mesurer le temps d'exécution et le temps de communication d'uneconnexion ssh. Cela donne une première approximation du nombre deconnexion simultanée que l'on peut lancer depuis le noeud d'origine.

Inconvénients

Di�cile de dépasser quelques centaines de connexions


Lanceurs

Contention sur les ressources

La contention sur les ressources à tendance pipeliner naturellement lesexécutions.Taktuk force cette exécution en pipeline en introduisant un délai entre ledébut de chaque connexion.les connections ssh sont composée au début d'une partie qui ne peut pas serecouvrir puis d'une autre qui peut.


Lanceurs

Le modèle postal

Il y a un temps de préparation de l'envoi, non recouvrable

Puis la latence du réseau, pour atteindre le noeud destinataire.

On peut préparer un autre envoi pendant le transfert sur le réseau.

Machines et réseau homogène

La solution optimal pour une di�usion consiste à démarrer les envois auplus tôt.


Lanceurs

Hétérogénéité

Comment répartir les connections si les machines et le réseaux sonthétérogènes ?

vol de travail

distribution amortie limitée à la moitié de ce qui reste


Lanceurs

Auto-propagation

Taktuk est implanté en Perl. Il peut donc facilement s'auto-déployerpendant le démarrage des connections.

1 lancer perl à distance et lui faire renvoyer une noti�cation2 lui envoyer ensuite le code de taktuk3 après le démarrage de taktuk il envoie une requête demandant du

travail


Lanceurs

Noeuds en panne

Les noeuds en panne vont �nir par être détecté par TCP ou ssh mais celava prendre le temps d'un timeout. Il est possible d'accélérer lesdéploiement en �xant dans taktuk un timeout plus petit.


Documents

Communications, Tolérance aux pannes, programmation