11
Présentation rapide de
22
• MPI et la programmation (message pasing) en mémoire distribuée– La programmation par échanges de message – MPI
• MPI en pratique– Groupes de communications– Communication points à points– Communication collectives
• MPI plus précisément…– Les types utilisateur– MPI2
Plan
33
• Le problème :– On dispose de n machines– Ces machines sont connectées en réseau
Comment utiliser la machine globale à n processeurs constituée par l’ensemble de ces n machines?
RAM
CPU
RAM
CPU
RAM
CPU
RAM
CPU
RAM
CPU
RAM
CPU
RAM
CPU
Réseau
Message passing en mémoire distribuée
44
• Une réponse : le passage de messages (message passing)– Faire exécuter un processus sur chaque processeur disponible– Effectuer des transferts de données explicites entre les processeurs– Synchroniser les processus explicitement
• Immédiatement on peut distinguer deux types de communications pour le transfert de données :– Les communications à l’initiative d’un seul des processus : ‘one
sided’ – Les communications se font en commun : ‘cooperative’
Message passing en mémoire distribuée
55
• Communications ‘one sided’– Pas de protocole de
rendez-vous (tout est fait à distance)
– On n’indique pas aux processus une lecture ou écriture dans leur mémoire locale
– Synchronisation difficile ou coûteuses
• Prototypes de fonctions :– put(remote_process, data)– get(remote_process, data)
• Communications coopératives– La communication est
effectuée explicitement par les deux processus
– La synchronisation est implicite dans les cas simples
• Prototypes de fonctions :– send(destination, data)
– recv(source, data)
CPU CPU
put()
CPU CPU
get()
CPU CPU
send() recv()
Deux types de communications
66
• Standard développe et utilisé par des industriels, des académiques, et des fabricants de machines parallèles
• But : spécifier une bibliothèque de fonctions de passage de messages portable
• La base est un environnement d’exécution qui lance les processus et les connecte entre eux
• Supporte :– Des modes de communication synchrones et asynchrones– Des communications collectives
• Offre des domaines de communication séparés
MPI
77
• Correspond au schéma général de programmation SPMD– Tous les processus sont lancés en même temps– Le même programme est lancé sur tous les processus
Section séquentielle
Initialisation de MPI
Initialisation de
la section parallèle
Calcul
Communications
Synchronisation
Fin section parallèle
Section séquentielle
(Parties non-parallélisables)
Remarque : la plupart des implémentations
‘conseillent’ de limiter cette dernière partie
à la sortie du programme
Section multinode (MPI)
Initialisation de la section parallèle
Terminaison de la section parallèle
Structure d’un programme MPI
88
• Tout unité de programme appelant des sous-programmes MPI doit inclure un fichier d’en-têtes mpi.h en C/C++ (mpif.h en Fortran)
• Les fonctions de la bibliothèque MPI sont sensiblement les même entre la version Fortran et C/C++ – généralement une variable de sortie supplémentaire « ierror »
en Fortran qui remplace le type de retour des fonctions C/C++
• Initialisation de l’environnement MPI– C : MPI_Init(&argc, char &argv);– Fortran : call MPI_Init(ierror)
• Terminaison de l’environnement MPI (il est en général recommandé de terminer immédiatement après cette instruction)– C : MPI_Finalize();– Fortran : call MPI_Finalize(ierror)
Fonctionnement d’un programme MPI
99
• Toutes les opérations effectuées par MPI portent sur des communicateurs. Le communicateur par défaut est MPI_COMM_WORLD qui comprend tous les processus actifs.
• Obtention du rang du processus
– C : MPI_Comm_rank(MPI_COMM_WORLD, &rank);
– Fortran : call MPI_Comm_rank(MPI_COMM_WORLD, rank, ierror)
• Obtention du nombre de processus
– C : MPI_Comm_size(MPI_COMM_WORLD, &size);
– Fortran : call MPI_comm_size(MPI_COMM_WORLD, size, ierror)
Fonctionnement d’un programme MPI
1010
#include <stdio.h>
#include <???>
void main(int argc, char ** argv)
{
int rang, nprocs;
????? ;
????? ;
????? ;
printf(“Bonjour, je suis le processus %d (parmi %d process)\n”, rang, nprocs);
????? ;
}
Le programme HelloWorld
1111
• Notions élémentaires : groupes, contextes, domaines de communication
• Fonctions de communication point à point
• Types de données
• Tags de communication
• Fonctions de communication collectives
• Exemple concret : calcul de la trace d’une matrice carrée
Partie 1 : MPI ?
1212
• Les processus d’un programme MPI peuvent être regroupés en groupes ‘group’
• Tout message est envoyé dans un contexte ‘context’, et doit impérativement être reçu dans le même contexte
Groupe de communication
1313
• Plusieurs nœuds peuvent être regroupés en un domaine de communication, ou communicator
• Un est définie par défaut, MPI_COMM_WORLD a été utilisé pour les communications, il s’agit du domaine par défaut, comprenant tous les processeurs
• De façon plus générale, toute opération peut être effectuée seulement sur un ensemble de processeurs par l’indication de son domaine
• Chaque processus possède un rang dans chaque domaine de communication dont il fait partie
Groupe de communication
1414
• Avant de créer un domaine, il faut créer un groupe de processeurs :– int MPI_Comm_group(MPI_Comm comm, MPI_Group *group);
• Création d’un domaine :– int MPI_Comm_create(MPI_Comm comm, MPI_Group group,
MPI_Comm *newcomm) ;– int MPI_Comm_split(MPI_Comm comm, int color, int key,
MPI_Comm *newcomm) ;
• Exemple d’utilisation :– MPI_Send(newcomm, )
Groupe de communication
1515
• Une communication dite point à point a lieu entre deux processus, l’un appelé processus émetteur et l’autre processus récepteur (ou destinataire).
• Elles permettent d’envoyer et recevoir des données entre deux processus
• Les deux processus initient la communication, l’un qui envoie la donnée, le second qui la reçoit
• Les communications sont identifiés par des tags
• Il faut préciser d’avance la taille des éléments envoyés, ainsi que leur type
Communication point à point
1616
• L’émetteur et le récepteur sont identifiés par leur rang dans le communicateur.
• Ce que l’on appelle l’enveloppe d’un message est constituée :
– du rang du processus émetteur – du rang du processus récepteur – de l’étiquette (tag) du message – du nom du communicateur qui définira le contexte de
communication de l’opération
• Les données échangées sont typées (entiers, réels, etc. ou types d´erivés personnels)
• Il existe dans chaque cas plusieurs modes de transfert, faisant appel à des protocoles différents
Communication point à point
1717
• Envoi de données synchrone :
– int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm) ;
– Le tag permet d’identifier le message de facon unique
• Réception de données synchrone :
– int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status) ;
– Le tag doit être identique que le tag du Send
Communication point à point: synchrone
1818
• Les tags de communication permettent d’identifier une communication particulière dans un ensemble
• Elles permettent ainsi, dans le cas ou les communications ne sont pas synchrones, de ‘trier’ les messages
• Il est possible dans le cas des opérations de réception, de recevoir depuis n’importe quel tag en utilisant le mot-clef : MPI_ANY_TAG (à eviter)
• On peut egalement utilisé le mot-clef : MPI_ANY_SOURCE si l’émetteur n’est pas nécessairement connu (à eviter)
• Il existe des variantes syntaxiques, MPI_Sendrecv(…) et MPI_Sendrecv_replace(…), qui enchaînent un envoi et une réception.
Les tags de communication
1919
Type MPI Type C
MPI_CHAR signed char
MPI_SHORT signed short int
MPI_INT signed int
MPI_LONG signed long int
MPI_UNSIGNED_CHAR unsigned char
MPI_UNSIGNED_SHORT unsigned short int
MPI_UNSIGNED unsigned int
MPI_UNSIGNED_LONG unsigned long int
MPI_FLOAT float
MPI_DOUBLE double
MPI_LONG_DOUBLE long double
MPI_BYTE
MPI_PACKED
Type MPI Type FORTRAN
MPI_INTEGER INTEGER
MPI_REAL REAL
MPI_DOUBLE_PRECISION DOUBLE PRECISION
MPI_COMPLEX COMPLEX
MPI_LOGICAL LOGICAL
MPI_CHARACTER CHARACTER(1)
MPI_BYTE
MPI_PACKED
Les types prédéfinies dans MPI
2020
#include <stdio.h>
#include <mpi.h>
void main(int argc, char ** argv) {
int me, prec, suiv, np;
int jeton = 0;
MPI_Status * status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &me);
MPI_Comm_size(MPI_COMM_WORLD, &np);
if (me == 0)
prec = np – 1;
else
prec = me – 1;
if (me == np - 1)
suiv = 0;
else
suiv = me + 1;
if (me == 0) MPI_Send(&jeton, 1,
MPI_INT, suiv, 0, MPI_COMM_WORLD,);
while (1) {
MPI_Recv(&jeton, 1, MPI_INT, prec, 0, MPI_COMM_WORLD, status);
MPI_Send(&jeton, 1, MPI_INT, suiv, 0, MPI_COMM_WORLD);
}
MPI_Finalize();
}
3
4
5
21
0
np -1
Un exemple : tour de table
2121
• Afin de résoudre les problèmes de deadlocks, et pour permettre le recouvrement des communications par le calcul, on peut utiliser des fonctions de communications asynchrones
• Dans ce cas, le schéma de communication est le suivant :
– Initiation d’une communication non-bloquante (soit par l’envoyeur, soit par le récepteur, soit les deux)
– La communication est lancée sur l’autre nœud– … opérations diverses (typiquement : du calcul)– Terminaison de la communication (opération qui bloque jusqu’à ce
que la communication ait été effectuée)
Communication point à point: asynchrone
2222
• Les fonctions non-bloquantes :
– int MPI_Isend(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request);
– int MPI_Irecv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request) ;
• Le champ request sert à connaître l’état de la communication non-bloquante afin de savoir quand elle se termine, par un appel à la fonction :
– int MPI_Wait(MPI_Request *request, MPI_Status *status) ;
Communication point à point: synchrone
2323
• Il existe non seulement la possibilité d’envoyer les données de façon synchrone ou asynchrone dans le cas des échanges point-à-point
• Ainsi, on peut contrôler plus finalement le mode de communication par l’utilisation de préfixes (MPI_[*]Send):– Envoi synchrone ([S]) :se termine lorsque la réception
correspondante est postée– Envoi bufferisé ([B]): un buffer est créé, et l’envoi ne se termine que
lorsque ce buffer utilisateur est copié dans le buffer système– Envoi standard () : l’envoi se termine quand le buffer d’émission est
vide– Envoi ready ([R]) : l’utilisateur affirme que la réception a été postée
avec l’émission
Communication point à point: indicatif
2424
• Afin de simplifier certaines opérations récurrentes, on peut utiliser des opérations qui sont effectuées sur un ensemble de processeurs (sur leur domaine de communication)
• Ces opérations sont typiquement :
– Des synchronisations explicites
– Des échanges de données entre processeurs :• Broadcast• Scatter• Gather• All-to-All
– Des réductions
Communication collective
2525
• Barrière de synchronisation : tous les processus d’un domaine de communication attendent que le dernier processus soit arrivé à la barrière de synchronisation avant de continuer l’exécution
• Prototype de la fonction
– C : int MPI_Barrier (MPI_Comm communicator);
– Fortran : MPI_Barrier(Communicator, IERROR)
Barrière
Communication collective : synchronisation
2626
• Une opération de broadcast permet de distribuer à tous les processeurs une même donnée
• Communication de type un-vers-tous, depuis un processus ‘root’ spécifie par tous les processus (identique pour tous) du domaine
• Prototypes :– C : int MPI_Bcast(void *buffer, int count, MPI_Datatype
datatype, int root, MPI_Comm comm);– Fortran : MPI_Bcast(buffer, count, datatype, root,
communicator, ierror)
0 1 2 3 np-1
root = 1
0 1 2 3 np-1
buffer
Communication collective :broadcast
2727
• Opération de type un-vers-tous, où des données différentes sont envoyées sur chaque processus receveur, suivant leur rang
• Prototypes :– C : int MPI_Scatter(void * sendbuf, int sendcount, MPI_Datatype
sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm communicator);
– Fortran : MPI_Scatter(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, root, communicator, ierror)
• Les paramètres ‘send’ ne sont utilises que par le processus qui envoie les données
sendbuf
recvbuf
0 1 2 3 np-1
root = 2
0 1 2 3 np-1
Communication collective : sscatter
2828
• Opération de type tous-vers-un, où des données différentes sont reçues par le processeur receveur, suivant leur rang
• Prototypes :– C : int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype
sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm communicator);
– Fortran : MPI_Gather(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, root, communicator, ierror)
• Les paramètres ‘receive’ ne sont utilises que par le processus qui reçoit les données
sendbuf
recvbuf
0 1 2 3 np-1
root = 3
0 1 2 3 np-1
Communication collective : gather
2929
• Opération de type tous-vers-un, où des données différentes sont reçues par le processeur receveur, suivant leur rang
• Prototypes :– C : int MPI_AllGather(void* sendbuf, int sendcount, MPI_Datatype
sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, MPI_Comm communicator);
– Fortran : MPI_AllGather(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, communicator, ierror)
• Les paramètres ‘receive’ ne sont utilises que par le processus qui reçoit les données
sendbuf
recvbuf
0 1 2 3 np-1 0 1 2 3 np-1
Communication collective : allgather
3030
• Opération de type tous-vers-tous, où des données différentes sont envoyées sur chaque processus, suivant son rang, et réarrangées suivant le rang de l’expéditeur
• Prototypes :– C : int MPI_AlltoAll(void * sendbuf, int sendcount, MPI_Datatype
sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm communicator);
– Fortran : MPI_Alltoall(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, root, communicator, ierror)
• Les paramètres ‘send’ ne sont utilises que par le processus qui envoie les données
sendbuf
recvbuf
0 1 2 3 np-1 0 1 2 3 np-1
Communication collective : alltoall
3131
• Les sous-programmes MPI SCATTERV(), MPI GATHERV(), MPI ALLGATHERV() et MPI ALLTOALLV() étendent MPI SCATTER(), MPI GATHER(), MPI ALLGATHER() et MPI ALLTOALL() au cas où le nombre d’éléments à diffuser ou collecter est différent suivant les processus.
• Ils prennent alors un ou des arguments suplémentaires qui representent les nombres de données ainsi que les positions de stockage des données
• Exemple : prototypes de Scatterv :– C : int MPI_Scatterv(void * sendbuf, int *sendcounts, int
*senddispls, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm communicator);
– Fortran : MPI_Scatterv(sendbuf, sendcounts, senddispls, sendtype, recvbuf, recvcount, recvtype, root, communicator, ierror)
Communication collective : extension
3232
sendbuf
recvbuf
0 1 2 3 np-1
root = 2
0 1 2 3 np-1
• Exemple sur le processeur root on doit avoir :
– sendcounts 1, 2, 1, 3, 1, 2
– senddispls 0, 1, 3, 4, 7, 8
Communication collective : extension
3333
• Une réduction permet d’effectuer sur un des données distribuées dans un ensemble de processeurs une opération arithmétique de type addition, minima/maxima, …
• Prototype :– C : int MPI_Reduce(void * sendbuf, void* recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm communicator);
– Fortran : MPI_Reduce(sendbuf, recvbuf, count, datatype, op, root, communicator, ierror)
• Dans la forme MPI_Reduce() seul le processeur root reçoit le résultat
• Il existe la forme MPI_AllReduce(), ou tous les processus reçoivent le résultat
Les réductions
3434
• Opérations disponibles
MPI_Op Operation
MPI_MIN Minimum
MPI_MAX Maximum
MPI_SUM Somme
MPI_PROD Produit élément à élément
MPI_LAND ET logique
MPI_BAND ET bit par bit
MPI_LOR OU logique
MPI_BOR OU bit par bit
MPI_LXOR OU exclusif logique
MPI_BXOR OU exclusif bit par bit
MPI_MINLOC Minimum et emplacement
MPI_MAXLOC Maximum et emplacement
Les réductions
3535
• Calcul de la trace d’une matrice An
• Rappel : la trace d’une matrice est la somme des éléments de sa diagonale (matrice nécessairement carrée)
• Mathématiquement, on sait que :
• Immédiatement, on voit facilement que le problème peut être parallélisé en calculant la somme des éléments diagonaux sur plusieurs processeurs puis en utilisant une réduction pour calculer la trace globale
Exemple : calcul de la trace d’une matrice
3636
#include <stdio.h>
#include <mpi.h>
void main(int argc, char ** argv) {
int me, np, root=0;
int N; /* On suppose que N = m*np */
double A[N][N];
double buffer[N], diag[N];
double traceA, trace_loc;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &me);
MPI_Comm_size(MPI_COMM_WORLD, &np);
tranche = N/np;
/* Initialisation de A faite sur 0 */
/* … */
/* On bufferise les éléments diagonaux depuis le processus maître */
if (me == 0) {
for (i=root; i<N; i++)
buffer[i] = A[i][i];
}
/* L’opération de scatter permet de distribuer la diagonale bufférisée entre les processus */
MPI_Scatter(
buffer, tranche, MPI_DOUBLE,
diag, tranche, MPI_DOUBLE, MPI_COMM_WORLD);
Exemple : calcul de la trace d’une matrice
3737
/* On calcule la trace locale sur chaque processeur */
trace_loc = 0;
for (i = 0; i < tranche; i++)
trace_loc += diag[i];
/* On peut alors effectuer la somme globale */
MPI_Reduce(&trace_loc, &traceA, 1, MPI_DOUBLE, MPI_SUM, root, MPI_COMM_WORLD);
if (me == root)
printf("La trace de A est : %f \n", traceA);
MPI_Finalize();
}
Exemple : calcul de la trace d’une matrice
3838
• Types de données utilisateur
• Extensions MPI-2
Partie 2 : notions avancées
3939
• Par défaut, les données qui peuvent être échangées (au sens large) par MPI sont les types présentés précédemment, sous forme de vecteurs
• Il est possible de créer de nouveaux types afin de simplifier les opérations de communication (notamment les procédures de ‘bufferisation’)
• Un type se présente sous la forme d’une séquence de types de base et d’une séquence d’offsets entier (placement mémoire)– Creation : MPI_Type_commit(type) ;– Destruction : MPI_Type_free(type) ;
Types de données utilisateur
4040
• Le standard MPI-2 présente certaines nouveautés afin de combler certains vides constatés, que d’autres outils peuvent combler
• Changement dynamique du nombre de processeurs– Il devient possible de ‘spawner’ de nouveaux processus lors de
l’exécution du programme. Des inter-domaines sont alors crées
• Fonctions de communications ‘one-sided’– MPI_Put () et MPI_Get () sont présents dans MPI-2
L’évolution MPI-2
4141
• MPI est devenu, grâce au travail en commun de la communauté du calcul parallèle, une bibliothèque standard de passage de messages
• De nombreuses implémentations existent, sur la plupart des plate-formes
• L’apprentissage de MPI est très simple, sans devoir entrer dans les notions les plus obscures de la bibliothèque
• La documentation et les publications disponibles sont conséquentes
Conclusions sur MPI
4242
• Le site officiel du standard MPI (en Anglais)– http://www-unix.mcs.anl.gov/mpi/
• Le forum MPI (en Anglais)– http://www.mpi-forum.org/
• Livre : MPI, The Complete Reference (Marc Snir et al.)– http://www.netlib.org/utk/papers/mpi-book/mpi-book.html
• Les cours de l’IDRIS (en Français)– http://www.idris.fr/data/cours/parallel/mpi/choix_doc.html
Plus d’information =>