Introduction to Parallel Programming with MPI

Master Modélisation et Simulation - ENSTA cours A1-2

Pierre Kestener
[Link]@[Link]

CEA-Saclay, DSM, France

Maison de la Simulation

MDLS, September, 2013

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 Unix du terme,
donc espace mémoire propre pas directement accessible aux 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 (message passing) 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 #include < s t d l i b . h>
#include < s t d i o . h>
3

#include <mpi . h>

5

i n t main( i n t argc , char * argv [ ] )

7 {

9 i n t nbTask ;
i n t myRank ;
11

MPI_Init(&argc , &argv ) ;
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 task %d out of %d\n" ,myRank, nbTask ) ;

19 MPI_Finalize ( ) ;

21 return 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 integer : : nbTask , myRank, i e r r

9 c a l l MPI_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

write ( * , * ) ’ I am task ’ , myRank, ’ out of ’ , nbTask

15

c a l l MPI_Finalize ( 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 accessibles depuis tous les nœuds
• automatique: les super-calculateurs utilisent un gestionnaire de
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_verbose 30 ./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 savoir si 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]
[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érifier plus 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_mpi3
• 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 receive to be executed
and for the handshake to arrive before the message can be transferred.
• Synchronous send has no extra copying but requires more waiting; a
receive must be executed and a handshake must arrive before sending.
MPI_Send
Standard mode tries to trade off between the types of overhead.
• Large messages use the "rendezvous protocol" to avoid extra copying: a
handshake procedure establishes direct communication.
• Small messages use the "eager protocol" to avoid synchronization cost:
the message is quickly copied 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 overhead ajouté (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

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

immediately following the first underscore: 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 to demonstrate the order of receive operations * /
2 MPI_Comm_rank (comm, &myRank) ;
i f (myRank == 0) {
4 MPI_Send ( sendbuf1 , count , MPI_INT , 2 , tag , comm) ;
MPI_Send ( sendbuf2 , count , MPI_INT , 1 , tag , comm) ;
6 } e l s e i f (myRank == 1) {
MPI_Recv ( recvbuf1 , count , MPI_INT , 0 , tag , comm, &s t a t u s ) ;
8 MPI_Send ( recvbuf1 , count , MPI_INT , 2 , tag , comm) ;
} e l s e i f (myRank == 2) {
10 MPI_Recv ( recvbuf1 , count , MPI_INT , MPI_ANY_SOURCE, tag , comm, &s t a t u s )
;
MPI_Recv ( recvbuf2 , count , MPI_INT , MPI_ANY_SOURCE, tag , 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

void gather_ring ( f l o a t * x , i n t blocksize , f l o a t * y )

2 {
i n t i , p , my_rank , succ , pred ;
4 i n t send_offset , 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) ;

8 MPI_Comm_rank (MPI_COMM_WORLD, &my_rank ) ;
f o r ( i =0; i <blocksize ; i ++)
10 y [ i +my_rank * blocksize ] = x [ i ] ;
succ = ( my_rank+1) % p;
12 pred = ( my_rank−1+p) % p ;
f o r ( i =0; i <p−1; i ++) {
14 send_offset = ( ( my_rank−i +p) %p ) * blocksize ;
r e c v _ o f f s e t = ( ( my_rank−i −1+p) %p ) * blocksize ;
16 MPI_Send ( y+send_offset , blocksize , MPI_FLOAT, succ , 0 ,
MPI_COMM_WORLD) ;
MPI_Recv ( y+ r e c v _ o f f s e t , blocksize , 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 #@ class = clallmds
#@ job_name = TEST
5 #@ total_tasks = 4
#@ node = 2
7 #@ wall_clock_limit = 0:05:00
#@ output = $ ( job_name ) . $ ( jobid )
9 #@ error = $ ( job_name ) . $ ( jobid )
#@ environment = COPY_ALL
11 #@ job_type = mpich
#@ queue
13

module load gnu−env openmpi

15

mpirun −bycore −bind−to−core −report−bindings . / 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 .bashrc contient 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 broadcast * /
i f ( my_rank == 0) {
3 f o r ( rank =1; rank<nranks ; rank ++) {
MPI_Send ( ( void * ) a , / * t a r g e t = * / rank , . . . ) ;
5 }
} else {
7 MPI_Recv ( ( void * ) a , 0 , . . . ) ;
}

../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 broadcast * /
2 i f ( my_rank == 0) {
f o r ( rank =1; rank<nranks ; rank ++) {
4 MPI_Send ( ( void * ) a , / * t a r g e t = * / rank , . . . ) ;
}
6 } else {
MPI_Recv ( ( void * ) 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
• Replace un 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