Introduction à la programmation parallèle avec MPI

D’après des diapositives de Pierre Kestener

[Link]@[Link]
1 /52
MPI - types de systèmes parallèles

2 /52
MPI - types de systèmes parallèles

Systèmes à mémoire partagée

• Les cœurs d’un CPU partagent l’accès à la mémoire
• Programme dit multi-threadé, les threads partagent des variables
localisées dans le même espace mémoire
• Coordination des threads par lecture/écriture des variables partagés

Systèmes à mémoire distribuée

• Programme constitués de plusieurs tâches (au sens Unixdu terme,
donc espace mémoire propre pas directement accessibleaux autres
tâches)
• Communication inter-tâches (coordination) via l’échange explicit de
messages (via une interface réseau)
• Les ressources (données en mémoire) sont locales(ou privées) à une
tâche
• le modèle par échange de message (messagepassing) est aussi valable
sur architecture à mémoire partagée

3 /52
MPI - un standard /une norme

Historique: 1992-94: a groupe constitué de vendeurs et d’utilsateurs

décident de créer un document décrivant les concepts /les
abstractions de la norme MPI (quels types de communications,
point-à-point, collectives, ..., quels modes de synchronisations)
servant de base pour les implémentations logicielles
MPI forum [Link] ⇒ defines a standard set
of library calls, but does not define how to implement them
iterface C et Fortran
But (évident): fournir un outil commun pour la programmation des
systèmes à mémoire distribuée; assurer la portabilité d’un
programme d’un système à un autre
lien recommendé: le blog de Jeff Squyres sur MPI et ses slides

4 /52
MPI - un standard /une norme

5 /52
MPI - un standard /une norme

MPI : Message Passing Interface

Plusieurs tâches (au sens Unix du terme) envoient et/ou recoivent
des données d’autres tâches.
modèle SPMD (Single Program Multiple Data)
Toutes les tâches MPI exécutent le même programme mais utilisent
un sous-ensemble des données
MPMD (Multi Program Multiple Data) est permis par les ajouts dans
version MPI-2 de la norme (en dehors du cours)

6 /52
MPI - un standard /une norme

MPI est une librairie (pas un language)

Permettre le développement d’applications parallèles, de librairies
parallèles (ex: FFTW-mpi, scalapack, Petsc, ...), démocratiser l’accès
aux super-calculateurs
Quelque soit la technologie réseau (ethernet Gigabit, infiniband, ...), Les
différentes implémentations de MPI
• OpenMPI
• MPICH
• MVAPICH
• IntelMPI
• DeinoMPI

7 /52
MPI - un standard /une norme

Les évolutions du standard:

MPI-2
• New datatype constructors, language interoperability
• new functionalities: One-side communication, MPI-IO, dynamics
processes
• Fortran90 /C++ bindings

8 /52
Le programme MPI le plus simple ...
1 # inc lud e < s t d l i b . h>
# inc lud e < s t d i o . h>
3
# inc lud e <mpi . h>
5
i n t main ( i n t a rgc , char * a r gv [ ] )
7 {

9 i n t nbTask ;
i n t myRank ;
11
M PI_Init (& a rgc , &ar gv ) ;
13
MPI_Comm_size (MPI_COMM_WORLD, &nbTask ) ;
15
MPI_Comm_rank (MPI_COMM_WORLD, &myRank ) ;

17
p r i n t f ( " I am t a s k %d out o f %d\n" ,myRank , nbTask ) ;

19
M PI_Fina lize ( ) ;

21
r e tu r n 0 ;

23 }

../code/c/helloworld_mpi.c
9 /52
Le programme MPI le plus simple ...

1 program helloworld_mpi

3 use mpi

5 i m p l i c i t none

7 inte ge r : : nbTask , myRank , i e r r

9 c a l l M PI_Init ( i e r r )

11 c a l l MPI_COMM_SIZE(MPI_COMM_WORLD, nbTask , i e r r )
c a l l MPI_COMM_RANK(MPI_COMM_WORLD, myRank , i e r r )
13
w r ite ( * , * ) ’ I am t a s k ’ , myRank , ’ out o f ’ , nbTask
15
c a l l M PI_Fina lize ( i e r r )
17
end program helloworld_mpi

../code/fortran/helloworld_mpi.f90

10 /52
Le programme MPI le plus simple ...

Compiler une application MPI

• (optionnel) module load openmpi
• en C: mpicc -o helloworld_mpi_c helloworld_mpi.c
• en F90: mpif90 -o helloworld_mpi_f helloworld_mpi.f90
• Note: mpicc et mpif90 ne sont que des wrapper; pour savoir ce qui se
cache derrière, tapper mpicc -showme; en particulier mpicc appelle un
compilateur C qui peut être gcc, icc, pgcc, ...
Exécuter:
• ./helloworld_mpi_c
• mpirun -np 2 ./helloworld_mpi_c
• tapper man mpirun
• sur un processeurà x cœur, on peut lancer le programme avec plus de
tâches que de cœurs, elles vont être multiplexée (toute fois en HPC, cela
n’est pas recommandé)

11 /52
Le programme MPI le plus simple ...
mpirun peut lancer un programme MPI sur un ensemble de
machines simplement connectées sur le réseau
Mais comment lancer le programme sur plusieurs machines en même
temps ? 1
utiliser l’option -hostfile,
Comment spécifier le nombre de tâches par processeur (socket ), etc
...
man mpirun (cf TP sur poincare)
• manuel 2 : avoir le même système de fichier sur tous les nœuds (e.g. avoir les
répertoires home montés par le réseau en NFS); avoir des clefs ssh
accessiblesdepuis tous les nœuds
• automatique: les super-calculateursutilisent un gestionnairede travaux (ou
planificateurs de tâches) 3 qui s’occupent de gérer/allouer
les ressources matérielles dans un environnement multi-utilisateurs et
décident quand l’application sera exécutée; exemple: LoadLeveler (cf
TP sur cluster poincare), SLURM, TORQUE, ...
1 [Link]

2 [Link]
3 Job scheduler /batch system /distribute resource manager

12 /52
Le programme MPI le plus simple ...

connaître les caractéristiques de la version d’OpenMPI disponible:

ompi_info
Exemple: découvrir les paramêtres (qui peuvent être changés au
runtime) concernant la couche d’interconnection:
ompi_info - -param btl all
Rendre verbeux l’exécution:
mpirun - -mca mtl_base_verbose30 ./helloworld_mpi.exe

13 /52
Communicateurs MPI

Communicateur par défaut: MPI_COMM_WORLD ⇒ constante définie

dans mpi.h; désigne l’ensemble de toutes les tâches du programme
MPI; communicateur global
Chaque tâche MPI est identifiée de manière unique par son rang
dans le communicateur.
Une tâche peut appartenir à plusieurs communicateurs (et avoir un
identifiant dans chacun)
Comment créer un communicateur ? e.g. MPI_Comm_split

14 /52
Programmation parallèle avec MPI

Start processes
Send messages:
• point-to-point: MPI_Send, MPI_Bsend, MPI_Isend, MPI_Issend,
MPI_Ibsend
• collective: MPI_Reduce, MPI_Scatter, ...
Receive messages:
• point-to-point: MPI_Recv, MPI_Brecv, MPI_Irecv, MPI_Isrecv,
MPI_Ibrecv
• collective: MPI_Reduce, MPI_Scatter, ...
Synchronize: MPI_Barrier

15 /52
MPI : Point-à-Point

Ce qu’il faut connaître:

Les 4 modes de communications: standard, buffered, synchronous,
ready
Communications bloquantes vs non-bloquantes
Qu’est une deadlock; comment les éviter ?
Les fonctions: MPI_Wait, MPI_Test
[avancé]: les communications persistantes

Références:
[Link]
[Link]

16 /52
MPI : Point-à-Point

Ce qu’il faut connaître:

les modes de communications régissent comment le système gère
l’envoi et la réception d’un message
exemple: lorsque l’appel de fonction MPI_Send se termine, que peut-on
dire sur la réception du message ?
• Peut-on savoirsi la réception a déjà terminée, ou à peine commencé ?
• Peut-on ré-utiliser les ressources (tableau mémoire) du message de
manière sure ?

Références:
[Link]
i/
[Link]

17 /52
MPI : Point-à-Point

Ce qu’il faut connaître:

Communications bloquantes vs non-bloquantes
• Un appel à une routine de communication bloquante (MPI_Send,
MPI_Recv) suspend l’éxécution de la tâche MPI appellante jusqu’à ce
que le buffer/tableau (contenant le message) peut être ré-utilisé en
toute sécurité.
• Un appel à une routine de communication non-bloquante
(MPI_Isend, MPI_Irecv) initialise le processus de communication; le
développeur doit vérifierplus tard que la communication s’est bien
déroulée (appel à MPI_Wait, MPI_Test), avant de pouvoir ré-utiliser le
buffer.

Références:
[Link]
[Link]

18 /52
Point-à-Point: MPI_Send / MPI_Recv

Les 3 paramêtres qui décrivent les donnés /le message

Les 3 paramêtres qui décrivent le routage
src, tag peuvent prendre des valeurs génériques; noter les différences
C/Fortran (passage par références et retour d’erreur)

19 /52
Point-à-Point: MPI_Send / MPI_Recv

Les 3 paramêtres qui décrivent les donnés /le message

Les 3 paramêtres qui décrivent le routage
src, tag peuvent prendre des valeurs génériques; noter les différences
C/Fortran (passage par références et retour d’erreur)

20 /52
Point-à-Point: MPI_Send / MPI_Recv

Communication point-à-point; nécessite un envoyeur et un

récepteur
Communication bufferisée: MPI_Bsend, MPI_Buffer_attach

21 /52
Point-à-Point: MPI_Send / MPI_Recv

Communication point-à-point; nécessite un envoyeur et un

récepteur
Communication bufferisée: MPI_Bsend, MPI_Buffer_attach

22 /52
Point-à-Point: MPI_Send / MPI_Recv

Communication point-à-point; nécessite un envoyeur et un

récepteur
Communication bufferisée: MPI_Bsend, MPI_Buffer_attach

23 /52
Exercice: MPI_Send / MPI_Recv

1 Helloworld_mpi
• Compiler avec mpicc sur le poste local et sur poincare
• Changer le nombre de tâches MPI par nœud, nombre de nœuds, ..
• Modifier le code en ajoutant un appel à MPI_Get_processor_name, et
vérifier le mapping des tâches sur les nœuds (exécution sur poincare)
2 Helloworld_mpi2 avec MPI_Send / MPI_Recv
• Compiler et exécuter l’exemple.
• Visualiser les traces avec l’outil jumpshot 1 .
• Que se passe-t-il si le paramêtre source de MPI_Recv est hors des
possibilités (négatif ou supérieur à la taille du communicateur) ?

1 Re-compiler l’exemple avec mpecc /mpefc et avec l’option -mpilog

24 /52
Exercice: MPI_Send / MPI_Recv

1 Helloworld_mpi
3 • modifier Helloworld_mpi2 pour que la tâche 0 envoie un message à la
tâche 1 et réciproquement
• Que se passe-t-il si l’ordre des opérations send/receive est inversé dans
la tâche 1 ?
• Modifier le code pour les messages envoyés contiennent un tableau; et
reprendre la question précédente en faisant varier la taille du tableau.
• Que se passe-t-il si le tableau de réception n’est pas assez grand pour
contenir le message ?
• Que se passe-t-il si les paramêtres count de MPI_Send / MPI_Recv ne
correspondent pas (trop grand ou trop petit) ?
• Ré-écrire le code de cet exemple en utilisant MPI_ISend puis
MPI_Sendrecv
• Visualiser les traces avec jumpshot des différents programmes (avec
communications bloquantes et non-bloquantes).

25 /52
Helloworld revisité

Peut-on forcer l’ordre dans lequel les messages sont affichés ?

MPI_Barrier

26 /52
MPI : Point-à-Point

System overhead
Cost of transferring data from the sender’s message buffer onto the
network, then from the network into the receiver’s message buffer.
Good network connections improve system overhead.
• Buffered send has more system overhead due to the extra buffer copy.

Synchronization overhead
Time spent waiting for an event to occur on another task.
• In certain modes, the sender must wait for the receiveto be executed
and for the handshake to arrive before the message can be transferred.
• Synchronoussend has no extra copying but requires more waiting; a
receivemust be executedand a handshake must arrivebefore sending.
MPI_Sen
d
Standard mode
• Large tries use
messages to trade off between
the "rendezvous the types
protocol" of overhead.
to avoid extra copying: a
handshake procedure establishes direct communication.
• Small messages use the "eager protocol" to avoidsynchronization cost:
the message is quicklycopied to a small system buffer on the receiver.

27 /52
MPI : modes de communications

mode bufferisé
• le message est d’abord copié dans un buffer intermédiaire fourni par
l’utilisateur (MPI_Buffer_attach / MPI_Buffer_detach)
• les données (zone mémoire / tableau) en argument de MPI_Bsend peut
être ré-utilisé
• system overheadajouté (coût en mémoire)
• bonne synchro(les appels MPI_Bsend sont potentiellement courts)

28 /52
MPI : modes de communications
mode synchrone
• c’est le mode le plus sûr
• l’envoi effectif du message sur le réseau ne commence que lorsque la
procédure de hand-shake est terminée
• l’envoyeur est bloqué jusqu’à ce que le récepteur soit prêt.
• synchronisation overhead potentiellement important (appelà
MPI_Ssend sont potentiellement longs)
• pas d’overhead system (pas de tableau temporaire à allouer)

29 /52
MPI : modes de communications
mode ready
• Réduire à la fois les délais systèmes et de synchronisation (beurre et
l’argent du beurre)
• Hypothèse forte le récepteur est déjà prêt à recevoir; si ce n’est pas le
cas une erreur est générée coté récepteur (mais pas envoyeur) ⇒
difficile à gérer
• coté envoyeur c’est le cas optimal; coté récepteur, il y a un coût
potentiel à la synchro (MPI_Recv peut avoir démarré bien avant)
• Mode peu fréquent à l’utilisation; l’algorithme doit garantir que les
récepteurs sont toujours prêts pour éviter les erreurs.

30 /52
MPI : modes de communications
mode standard / normal (compromis entre buffered et synchrone)
• plus difficileà définir: 2 stratégies
• les messages courts sont bufferisés sur le récepteur (low synchro
overhead), aussi appelé eager protocol
• les messages longs on utilise le mode synchone (avec rendez-vous),
mais pas de bufferisation
• le seuil message court/long dépend de l’implémentation (voir l’exercise
helloworld); parfois configurable au runtime par une variable
d’environnement

31 /52
MPI - Communications non-bloquantes

The letter I (think of initiate) appears in the name

of the call, immediately following the first underscore:
1

e.g., MPI_Irecv.
2

The final argument is a handle to an opaque (or hidden)

request object that holds detailed information about the
transaction. The request handle can be used for subsequent
Wait and Test calls.

32 /52
MPI - Communications non-bloquantes

33 /52
MPI - Deadlock

deadlock (ou inter-blocage): en programmation

concurrente, désigne une situation où 2 processus
concurrent s’attendent mutuellement, et restent dans cet état
d’attente définitivement ! /
Programme MPI: situation typique où au moins 2 tâches
MPI veulent échanger des messages, mais toutes les 2
veulent envoyer leur message respectif et ne sont pas prêtes
à recevoir.

34 /52
MPI - Deadlock - exemples

reference: Steve Lantz, CAC, Cornell University,

Workshop on Parallel Computing

35 /52
MPI - Deadlock - exemples

reference: Steve Lantz, CAC, Cornell University,

Workshop on Parallel Computing

36 /52
MPI - Deadlock - exemples

reference: Steve Lantz, CAC, Cornell University,

Workshop on Parallel Computing

37 /52
MPI - Deadlock - exemples

reference: Steve Lantz, CAC, Cornell University,

Workshop on Parallel Computing

38 /52
MPI Deadlock

Expliquer pourquoi le programme suivant n’est par sûr:

/ * example t o demonstrate the o rd e r o f r e c e i v e o pe r a t io ns * /
2 MPI_Comm_rank (comm, &myRank ) ;
i f (myRank == 0) {
4 MPI_Send ( sendbuf1 , count , MPI_INT , 2 , ta g , comm) ;
MPI_Send ( sendbuf2 , count , MPI_INT , 1 , ta g , comm) ;
6 } e l s e i f (myRank == 1 ) {
MPI_Recv ( re cvb uf1 , count , MPI_INT , 0 , ta g , comm, &s t a t u s ) ;
8 MPI_Send ( re cvb uf1 , count , MPI_INT , 2 , ta g , comm) ;
} e l s e i f (myRank == 2 ) {
10
MPI_Recv ( re cvb uf1 , count , MPI_INT , MPI_ANY_SOURCE, ta g , comm, &s t a t u s )
;
MPI_Recv ( re cvb uf2 , count , MPI_INT , MPI_ANY_SOURCE, ta g , comm, &s t a t u s )
;
}
12

../code/c/deadlock.c

39 /52
MPI Exercice - anneau logique

anneau: écrire le code d’un programme MPI, où

on considère que les tâches MPI constitue un
anneau et on souhaite que les données de la
tâche i soit envoyée à la tâche (i + 1)%p
assurez-vous que le code est fonctionnel
quelque soit le nombre de tâches, et qu’il n’y a
pas de blocage.

40 /52
MPI Exercice - anneau logique

vo id g a t he r _ r i n g ( f l o a t * x , i n t b l o c ks i z e , f l o a t * y )
2 {
i n t i , p , my_rank , succ , pred ;
4
i n t s e nd _ o f fs e t , r e c v _ o f f s e t ;
MPI_Status s t a t u s ;
6
MPI_Comm_size (MPI_COMM_WORLD, &p ) ;
MPI_Comm_rank (MPI_COMM_WORLD, &my_rank ) ;
8
f o r ( i =0 ; i < b l o c k s i z e ; i ++)
y [ i +my_rank * b l o c k s i z e ] = x [ i ] ;
10
succ = ( my_rank +1) % p;
pred = ( my_rank−1+p ) % p ;
12

f o r ( i =0 ; i <p−1; i ++) {
14
s e n d _ o f f s e t = ( ( my_rank− i +p ) %p ) * b l o c k s i z e ;
r e c v _ o f f s( ey+t s =
MPI_Send e n d( (_o ff s e t , −1+p
my_rank−i b l o c) ks%p * b l o c k ,s i zsucc
i z e) , MPI_FLOAT e ; , 0,
16
MPI_COMM_WORLD) ;
MPI_Recv ( y+ r e c v _ o f f s e t , b l o c k s i z e , MPI_FLOAT , pred , 0 ,
MPI_COMM_WORLD, &s t a t u s ) ;
}
18
}

../code/c/gather_ring.c

41 /52
MPI Exercice - anneau logique

• Le code de la page précédente permet de

rassembler des blocs de données
distribués; faire un schéma pour illustrer
les accès mémoire
• Comment modifier le code si chaque
tâche à un blocksize différent ?

42 /52
MPI Performance
[Link]
MPE (MPI Parallel Environment): Outil de logging/tracing pour MPI
Visualisation de fichier trace (format CLOG2) avec jumpshot
(distribué avec MPE)
(septembre 2013): seule la version git de MPE est compatible avec
MPICH, la version release suffit pour OpenMPI

Figure: Capture d’écran de jumpshot montrant un exemple de trace d’éxecution

d’un programme MPI.
43 /52
Implementation d’OpenMPI

OpenMPI internal’s:
[Link]
En savoir plus sur l’implémentation bas-niveau:
slides de Brian Barret

44 /52
Gestion des resources sur poincare

Exemple de script de soumission de travail, demandant 2 nœuds, avec 2

tâches MPI par nœud.
1 # ! /bin / bash

3 #@ c la s s = c la llm d s
#@ job_name = TEST
5 #@ to ta l_ta s k s = 4
#@ node = 2
7
#@ w a ll_c lo c k _lim it = 0 :0 5 :0 0
#@ output = $ ( job_name ) . $ ( j o b i d )
#@ error = $ ( job_name ) . $ ( j o b i d )
9
#@ environment = COPY_ALL
#@ jo b _type = mpich
11
#@ queue

13
module lo a d gnu−env openmpi

15
mpirun −bycore −bind−to−c o re −re po r t −bind ings . /helloworld_mpi_c

../code/submit_job_poincare.sh

45 /52
Installer MPI /Executer un programme MPI

Quelques conseils pratiques pour utiliser MPI sur des postes de travail
usuels (pas un super-calculateur, pas de gestionnaires de ressources/job):
Installer MPI (e.g. OpenMPI)localement sur toutes les machines (ou
sur un système de fichier partagé, par exemple montage NFS)
Configuration SSH: il faut mettre en place des clés ssh (sans
passphrase)
• Créer la paire clé privée / clef publique: ssh-keygen -t rsa
• Copier la clé publique sur les machines distantes: ssh-copy-id -i
/.ssh/id_rsa.pub monlogin@machine_distante
• (optionnel) S’assurer que .bashrccontient tout se qui nécessaire pour exécution

en mode non-interactif 1 .
On pourra ensuite faire un petit test avec 1 seul processeur MPI, pour
vérifier que l’exécution distante fonctionne:
ssh monlogin@machine_distante mpirun -np 1
$HOME/helloworld_mpi

1 Le fichier .bashrc par defaut d’Ubuntu par ex, ne fait rien en mode non-interactif. Au besoin,
commenter la ligne qui teste si la variable PS1 n’existe pas.
46 /52
Installer MPI /Executer un programme MPI

Quelques conseils pratiques pour utiliser MPI sur des postes de travail
usuels (pas un super-calculateur, pas de gestionnaires de ressources/job):
On peut ensuite faire un teste d’un programme MPI sur plusieurs nœuds:

• Créer un fichier [Link] contenant la liste des noms de

machines sur le réseau local sur lesquelles on vient d’installer MPI et
configurer ssh.
• mpirun -np 4 -machinefile [Link]
$HOME/helloworld_mpi

47 /52
MPI - Communications collectives

1 / * Naive b ro a d ca st * /
i f ( my_rank == 0 ) {
3
f o r ( rank = 1 ; rank <nranks ; rank ++) {
MPI_Send ( ( vo id * ) a , / * t a r g e t = * / rank , ... );
5
}
} e ls e {
MPI_Recv ( ( vo id * ) a , 0 , . . . ) ;
7
}

../code/c/naive_bcast.c

broadcast: une tâche envoie un message à toutes les autres

implémentation naïve est très (trop) lente; messages sérialisés dans
la tâche émettrice
optimisation en implementant de meilleurs algorithmes

48 /52
MPI - Communications collectives
/ * Naive b ro a d ca st * /
2 i f ( my_rank == 0 ) {
f o r ( rank = 1 ; rank <nranks ; rank ++) {
4
MPI_Send ( ( vo id * ) a , / * t a r g e t = * / rank , ... );
}
} e ls e {
6
MPI_Recv ( ( vo id * ) a , 0 , . . . ) ;
}
8

../code/c/naive_bcast.c

OpenMPI par exemple utilise 6 algorithmes différents pour implanter

l’opération broadcast (MPI_Bcast) (le choix est fait en fonction de la
taille des données à diffuser et le nombre de récepteurs):
• binary tree
• binomial tree
• splitted binary tree
• pipeline
• ...
Qu’est ce qu’une communication collective ?
• toutes les tâches d’un communicateur sont impliquées
• Replaceun séquence complexe d’opérations P2P
49 /52
MPI - Communications collectives

MPI collective communication can be divided into three

subsets:
Synchronization
• Barrier synchronization

Data Movement
• Broadcast from one member to all other members
• Gather data from an array spread across processes into one array
• Scatter data from one member to all members
• All-to-all exchange of data

Global Computation
• Global reduction (e.g., sum, min of distributed data elements)
• Scan across all members of a communicator

50 /52
MPI - Communications collectives

51 /52
MPI - Communications collectives

52 /52