View
127
Download
5
Category
Preview:
Citation preview
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.
Recommended