Maîtrise d'informatique
Module de Programmation parallèle

Examen

Philippe Marquet

Juin 2001

Tous documents autorisés
Durée : 3h

Ce document est disponible sous forme d'un fichier PostScript compressé.

Important
Plusieurs questions vous demandent d'expliquer/décrire/motiver l'énoncé d'un algorithme, la parallélisation d'un problème... Ne les négligez pas ; ces questions sont notées ! Bien entendu, des réponses concises et précises sont appréciées.

1   Résolution de systèmes triangulaires supérieurs en MPI

Nous allons proposer une parallélisation à l'aide de la bibliothèque de passage de messages MPI de la phase de remontée, dernière étape de la résolution d'un système linéaire, après une triangularisation de Gauss ou une décomposition de Cholesky.

Nous allons résoudre le système triangulaire supérieur (sts)
U x = b
avec
U =
æ
ç
ç
ç
è
U1,1 U1,2 ... U1,N
0 U2,2 ... U2,N
0 ... ... ...
0 0 ... UN,N
ö
÷
÷
÷
ø
    et     Ui,i ¹ 0   pour tout   1 £ i £ N.

On a
bi =
N
å
j=i
Ui,j . xj      pour   i = N, N-1, N-2, ..., 1.

On procède donc par remontée en calculant successivement
xN =
bN
UN,N
     puis      xi =
bi -
N
å
j=i+1
Ui,j . xj
Ui,i
     pour   i = N-1, N-2, ..., 1.

Un code séquentiel pour ce calcul est le suivant : 
x[N] = b[N] / U[N,N];
for (i=N-1 ; i >= 1 ; i--) {
   acc = 0;
   for (j=i+1 ; j <= N ; j++) {
      acc += U[i,j] * x[j];
   }
   x[i] = (b[i] - acc) / U[i,i] ;
}
Nous travaillons avec N processus : P0 à PN-1. Les tableaux sont distribués par lignes sur ces processus selon le schéma de la figure 1.



Figure 1 : Distribution des tableaux pour la résolution du système linéaire triangulaire supérieur

Initialement,le processus P0 détient U et b (qu'il initialise par un appel à sts_lire (U,b)) ; il les distribue aux autres processus. À l'issue du calcul, P0 centralisera les résultats (qu'il sauvegardera par un appel à sts_ecrire (x)).

Exercice 1  [Initialisation et terminaison]   Donner les codes C/MPI ou Fortran/MPI des phases de diffusion des valeurs initiales aux processus et de collecte du résultat par le processus P0.

Il sera nécessaire de préciser les tableaux devant être alloués localement par chacun des processus.

Exercice 2  [Schéma de communications]   Identifier ce que doit recevoir le processus Pp pour mener à bien son calcul local à l'étape t ; de quel(s) processus il doit recevoir ces données. En conséquence, identifier ce que doit envoyer le processus Pp, et à quel(s) processus.

Exercice 3  [Résolution de sts]   Donner le code C/MPI ou Fortran/MPI de la résolution d'un STS.

Exercice 4  [Nouvelle(s) distribution(s) des données]   De part la distribution des données proposée, il appert un déséquilibre de travail entre les processus. Proposer des alternatives pour palier à ce déséquilibre. Identifier, si cela est possible, un recouvrement des communications par des calculs.

2   Différences finies en mémoire partagée

Nous allons implanter le problème dit des différences finies sur une machine multiprocesseurs à mémoire partagée à l'aide de processus légers. Nous travaillons au choix avec la bibliothèque pthread ou avec OpenMP.

On considère un domaine à deux dimensions de taille N × N. La valeur au point i,j au temps t+1 est calculée de la manière suivante :
Xi,j(t+1) =
4 Xi,j(t) + Xi-1,j(t) + Xi,j-1(t) + Xi+1,j(t) + Xi,j+1(t)
8

La résolution du problème se termine quand en tout point la différence entre la valeur de X(t) et la valeur de X(t-1) au temps précédent est inférieure, en valeur absolue, à une valeur e donnée.

Exercice 5  [Organisation pour les différences finies parallèles]   Donner une organisation de processus légers qui peut être mis en oeuvre pour la résolution du problème des différences finies 2-D sur une machine à mémoire partagée.

Exercice 6  [Programme des différences finies parallèles]   Donner le code d'un programme implantant votre proposition énoncée à l'exercice précédent.

3   Annexe

Pourvu que vous en définissiez précisément le comportement, vous pouvez introduire nombre de fonctions utiles qui ne sont pas en rapport direct avec les aspects centraux des développements à réaliser ici. Par exemple :

lire_X0(double **X)
initialise la valeur du domaine 2-D X.
double max_erreur(double **d1, double **d2)
retourne la valeur maximale de la différence élément à élément entre les domaines 2-D d1 et d2.


Ce document a été traduit de LATEX par HEVEA.