Communicateurs et produit matriciel en MPI
Résumé:
Dans ce TD, nous allons mettre en
uvre un produit de matrice
en
MPIbasé l'algorithme de double diffusion. Les diffusions se
faisant sur certain processeurs uniquement, nous allons créer de
nouveaux groupes de processus pour pouvoir utiliser la fonction
MPI_Bcast.
Nous avons déjà utilisé le communicateur MPI_COMM_WORLD qui
regroupe l'intégralité des processus lancés. Il est possible de créer
d'autres communicateurs, c'est à dire d'autres groupes de processus,
notamment en utilisant la fonction MPI_Comm_split.
int MPI_Comm_split ( MPI_Comm comm, int color, int key, MPI_Comm *newcomm )
- comm est le communicateur que l'on souhaite scinder
- color est un entier positif qui détermine à quel ensemble
on appartiendra, le nouveau communicateur regroupant les processus
de même couleur.
- key est un entier qui permet de déterminer le rang du
processus au sein du nouveau communicateur. Deux processeurs de même
couleur seront donc dans le même communicateur et leur rang sera
déterminé en fonction de leur valeur respectives de key
- newcomm est le nouveau communicateur.
On souhaite effectuer le calcul
pour tout dans
.
L'Algorithme 1 décrit une façon naturelle d'effectuer ce
calcul mais pas forcément adaptée à une parallélisation directe.
Les boucles 1 et 2 de cet
algorithme sont parallèles. La boucle de la ligne 3
correspond à une opération de réduction (qui peut s'effectuer par
exemple à l'aide d'un arbre) et réduit le parallélisme. On
séquentialise généralement une partie de ces boucles afin d'ordonner
et de régulariser les calculs (éviter des migrations de données
excessives et désordonnées), de simplifier le contrôle et surtout
d'adapter la granularité de la machine cible.
Il est donc préférable de permuter les boucles pour arriver à
l'Algorithme 2 et d'effectuer alors la boucle externe
(ligne 1) séquentiellement et les boucles internes
(lignes 2 et 3) en parallèle. Si
chaque est alloué à une unité de calcul fixe, alors les
et les doivent circuler entre chaque étape de
calcul, mais cela ne nuit pas au parallélisme et permet un
recouvrement potentiel du calcul et des communications (même si le
premier TD a démontré la difficulté de ce recouvrement avec MPI).
Figure:
Distribution homogène contiguë pour une grille
|
Dans le cas où l'on dispose de processeurs identiques
interconnectés en grille (voir Figure 1) : chaque
processeur est responsable de sous-matrices de taille
de , et .
L'Algorithme 2 se déroule donc en étapes et à
l'étape , la
colonne de et la
ligne de sont diffusées horizontalement (pour la
colonne) et verticalement (pour la ligne). Chaque processeur reçoit
donc un fragment de colonne de et un fragment de ligne de de
tailles respectivement et et met à jour la partie de
dont il est responsable (voir Figure 1).
Vous trouverez dans http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud/algopar/MPI/src/ un
canevas pour le programme de produit matriciel
(matmult_template.c). Comme d'habitude, le programme est
commenté et il n'y a qu'à remplir les trous. Une fois que le programme
fonctionne, augmentez la granularité des communications. Comment faire
pour évitez des copies inutiles lors des envois des fragment de lignes
et de colonnes ?
Une solution est disponible à la même adresse dans matmult.c.
Arnaud Legrand
2005-11-03