Cours : ``Parallélisme'' Travaux dirigés E. Goubault & M. Martel
TD 6
25 février 2003
1 Callback et RMI
On souhaite améliorer la façon dont pi est calculé par la méthode vue au TD 5, en
rendant la méthode compute non bloquante. Pour cela, la nouvelle méthode compute
créera un nouveau thread pour effectuer réellement le calcul et rendra immédiatement la main.
Le principe du callback intervient lorsque le calcul local est terminé, afin de communiquer le résultat
au client. Modifier le programme de calcul de pi du TD 5 comme indiqué précédemment.
2 Diffusion sur un anneau
Tester la simulation d'anneau de processeurs vue au TD 5 en programmant la diffusion simple pipelinée vue en cours.
3 Rotations de Givens
Pour triangulariser une matrice A d'ordre n de façon numériquement stable, on peut utiliser les
rotations de Givens. L'opération de base Rot(i,j,k) consiste à combiner les deux lignes
i et j, qui doivent toutes deux commencer par k-1 zéros pour annuler l'élément
en position (j,k) (avec le bon q):
æ è
0
...
0
a'i,k
a'i,k+1
...
a'i,n
0
...
0
0
a'j,k+1
...
a'j,n
ö ø
¬
æ è
cos q
-sin q
sin q
cos q
ö ø
æ è
0
...
0
ai,k
ai,k+1
...
ai,n
0
...
0
aj,k
aj,k+1
...
aj,n
ö ø
L'algorithme séquentiel peut s'écrire:
Givens(A)
1: for (k=1;k<n;k++)
2: for (i=n;i>k;i--)
3: Rot(i-1,i,k);
On considère qu'une rotation Rot(i,j,k) s'exécute en temps unité, indépendamment
de k.
Question 1
:
Mettre en oeuvre cet algorithme sur un réseau linéaire de n processeurs.
Question 2
:
Mettre en oeuvre cet algorithme sur un réseau linéaire comportant seulement ë n/ 2 û
processeurs
4 Allocation homogène/inhomogène
On considère un calcul sur une matrice M de taille n × n avec p processeurs.
Ce calcul, que l'on ne précise pas, a la propriété suivante: le
calcul de Mi,j ne peut se faire que si Mi-1,j et Mi,j-1
ont été calculés.
Question 1
: Comment faire une allocation statique optimale dans le cas homogène?
Question 2
: Comment faire une allocation statique par blocs de B=10 colonnes dans le
cas où p=3 et les temps de cycle sont t1=3, t2=5 et t3=8?
Question 3
: Utiliser l'idée de l'algorithme d'allocation incrémental du cours
pour essayer de faire mieux.