Cours : ``Parallélisme'' Travaux dirigés - Révisions E. Goubault & M. Martel
TD 9
25 mars 2003
1 Enveloppe convexe
A finir...
2 PRAM
Soit L une liste contenant n objets coloriés soit en bleu, soit en rouge. Concevoir un algorithme
EREW efficace qui sépare les éléments bleus des éléments rouges (c'est-à-dire qui construit
une nouvelle liste ne contenant que les éléments bleus).
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.