Projet QUID gk/QUID/ Présentation rapide de MPI : Message Passing Interface Géraud Krawezik LRI – Université de Paris Sud EADS CCR – Blagnac

Projet QUID

www.lri.fr/~gk/QUID/

Présentation rapide de MPI :

Message Passing Interface

Géraud KrawezikLRI – Université de Paris Sud

EADS CCR – Blagnac

[email protected]

DEA ID - Calcul Haute Performance 228 octobre 2003

Sommaire

MPI, une bibliothèque de passage de messages Le passage de messages MPI

MPI en pratique Fonctions de communication point-à-point Fonctions de communication collective

MPI : notions avancées Modes de communication Types utilisateur Extensions MPI-2


Introduction à MPI

Introduction au modèle à passage de messages

MPI

Structure d’un programme MPI

Fonctions de base

HelloWorld_MPI.c


Passage de messages (1)

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


Passage de messages (2)

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’


Deux types de communications

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()


MPI (Message Passing Interface)

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


Structure d’un programme MPI 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


Fonctions de base

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)

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)


HelloWorld_MPI.c

#include <stdio.h>

#include <mpi.h>

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

int rang, nprocs;

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &rang);

MPI_Comm_size(MPI_COMM_WORLD, &nprocs);

printf(“Bonjour, je suis %d (parmi %d process)\n”, rang, nprocs);

MPI_Finalize();

}


MPI : notions et fonctions de base

Notions élémentaires : groupes, contextes, domaines de communication

Types de données

Tags de communication

Fonctions de communication point à point

Fonctions de communication collectives

Exemple concret : calcul de la trace d’une matrice carrée


Groupes et contextes

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


Domaines de communication

Plusieurs nœuds peuvent être regroupés en un domaine de communication, ou communicator

Dans tous les exemples précédents, 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


Domaines de communication (2)

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, )


Types de données MPI

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


Communications point à point

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


Tags de communication

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


Fonctions de comm. de base

Envoi de données synchrone de base : 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 de base : 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 MPI_ANY_SOURCE peut être précisé si l’émetteur n’est pas

nécessairement connu


Jeton.c

#include <stdio.h>

#include <mpi.h>


int me, prec, suiv, np;

int jeton = 0;

MPI_Status * status;


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


Synchronisme et asynchronisme (1)

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 (bloquante ou pas) est lancée sur l’autre nœud … opérations diverses (typiquement : calcul) Terminaison de la communication (opération qui bloque jusqu’à ce que

la communication ait été effectuée)


Synchronisme et asynchronisme (2)

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) ;


Opérations collectives

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 réductions

Des échanges de données entre processeurs : Broadcast Scatter Gather All-to-All

Des synchronisations explicites


Réductions (1)

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


Réductions (2)

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


Broadcast 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


Scatter

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


Gather

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


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


All-to-All

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


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


Synchronisation explicite

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

A noter que sur les machines disposant de barrières matérielles (comme les SGI et le Cray T3E), la barrière MPI est beaucoup plus lente que celles-ci

Prototype de la fonction C : int MPI_Barrier (MPI_Comm communicator); Fortran : MPI_Barrier(Communicator, IERROR)


Trace d’une matrice (1)

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

n

k

kkAATrace1

,)(


Trace d’une matrice (2.1)

#include <stdio.h>

#include <mpi.h>


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_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);


Trace d’une matrice (2.2)

/* 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();

}


MPI : notions avancées

Modes de communication

Types de données utilisateur

Extensions MPI-2


Modes de communication

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


Types de données utilisateur

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) ;


Extensions MPI-2

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


Remarques en conclusion

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


Quelques pointeurs

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

Documents

Projet QUID gk/QUID/ Présentation rapide de MPI : Message Passing Interface Géraud Krawezik LRI – Université de Paris Sud EADS CCR – Blagnac