Parallel Programmingwith MPI and OpenMP

Michael J. Quinn

Chapitre 6L’algorithme de Floyd

Sujets couvertsChemin le plus court entre toutes les paires de

noeuds

Tableau 2-D dynamique

Communication entre deux noeuds

Le problème du chemin le plus court entre toutes les paires de noeuds d’un graphe

A

E

B

C

D

4

6

1 35

3

1

2

0 6 3 6

4 0 7 10

12 6 0 3

7 3 10 0

9 5 12 2

A

B

C

D

E

A B C D

4

8

1

11

0

E

Matrice d’adjacence

Algorithme de Floyd

for k 0 to n-1for i 0 to n-1

for j 0 to n-1a[i,j] min (a[i,j], a[i,k] + a[k,j])

endforendfor

endfor

Création dynamique d’un tableau 1-D

A

Heap

Run-time Stack

Création dynamique d’un tableau 2-D

Heap

Run-time StackBstorage B

Création dynamique d’un tableau 2-D

int **B, i;

Bstorage = (int*) malloc (M*n*sizeof(int));

B=(int**) malloc (m*sizeof(int*));

for (i=0; i<m; i++) B[i] = &Bstorage[i*n];

Conception d’un algorithme parallèle

Partition

Communication

Répartition du travail

PartitionDoit-on décomposer les données ou le code?

On peut facilement extraire du parallélisme de données

La même instruction doit être exécutée n3 fois

Pas de parallélisme de tâche

On peut voir le problème comme n2 applications de la même tâche à effectuer en parallèle sur des données différentes.

Communication

Tâches primitives

Mise-à-jour dea[3,4] lorsquek = 1

Iteration k:Chaque tâche de la ligne kdiffuse sa valeur aux tâches de la même colonne

Iteration k:chaque tâche de la colonne kdiffuse sa valeur aux tâches de la même ligne

Répartition du travailp processeurs

n2 valeurs de sortie

On associe environ n2/2 valeurs à chaque processeur

2 méthodes possibles

On regroupe par lignes On regroupe par colonnes

ComnparaisonRegroupement par colonne

On élimine la diffusion entre les lignes On élimine la diffusion entres les colonnes d’un même

groupe

Regroupement par ligne On élimine la diffusion entre les colonnes On élimine la diffusion entres les lignes d’un même

groupe

On choisi le regroupement par ligne puisque sur la plupart des systèmes les matrices sont représentées ligne par ligne.

Fichier d’entrée

Fichier

Un processus est chargé de lire le fichier d’entrée et de distribuer son contenu aux autres

Communicationentre deux noeuds

Deux processus veulent communiquer

Un processus envoie un message

L’autre processus reçoit le message

En opposition avec une diffusion ou un processus envoie un message à tous les autres.

Send/Receive

Function MPI_Send

int MPI_Send (

void *message,

int count,

MPI_Datatype datatype,

int dest,

int tag,

MPI_Comm comm

)

MPI_Datatype

MPI_CHAR

MPI_DOUBLE

MPI_FLOAT

MPI_INT

MPI_LONG

MPI_LONG_DOUBLE

MPI_SHORT

MPI_UNSIGNED_CHAR

MPI_UNSIGNED

MPI_UNSIGNED_LONG

MPI_UNSIGNED_SHORT

Function MPI_Recvint MPI_Recv (

void *message,

int count,

MPI_Datatype datatype,

int source,

int tag,

MPI_Comm comm,

MPI_Status *status

)

MPI_status3 champs:

MPI_SOURCE: id du processus envoyant le message

MPI_TAG: le tag du message

MPI_ERROR: code d’erreur

Utilisation de Send/Receive

…if (ID == j) { … Receive from I …}…if (ID == i) { … Send to j …}…

Implémentation de MPI_Send et MPI_Recv

Processus expéditeur Processus récepteur

Tampon duprogramme

Tampon du système

Tampon du système

Tampon de la mémoire

MPI_Send MPI_Recv

Retour deMPI_SendLe processus expéditeur est bloqué tant que la

mémoire n’est pas libéré

La mémoire est libéré lorsqueLe message est copié dans le tampon, ouLe message est transmis

Scénario typique:Le message est copié dans le tamponLa transmission s’effectue pendant que

l’expéditeur poursuit son exécution

Retour de MPI_RecvLe processus récepteur jusqu’à ce que le

message soit copié dans le tampon

Si le message n’arrive jamais alors le processus ne débloquera jamais

InterblocageLorsqu’un processus attend un événement qui

ne se produira jamais

Les appels send/receive sont une cause importante d’interblocageDeux processus: Les deux reçoivent avant

d’envoyerAucun send ne correspond à un receiveUn processus envoie un message à un mauvais

destinataire.