CS228 - Le2i

2004-2005
Systèmes (distribués et parallèles)
Exercices
Exercice 1
On veut calculer la somme de n nombres. Il faut Tc unités de temps à une
personne pour additionner deux nombres. a) Calculer le temps nécessaire à une personne pour calculer la somme de n
nombres
b) Les n nombres sont répartis en 8 groupes. On demande à 8 personnes de
calculer la somme des n nombres, sachant qu'il faut Tw unités de temps à
une personne pour transmettre son résultat à une autre personne
Calculer le temps nécessaire aux 8 personnes pour faire la somme n nombres
dans les cas suivants :
- 8 personnes assises en cercle
- 8 personnes formant deux rangées de 4 personnes chacune
- 8 personnes dans une configuration d'arbre binaire
- 8 personnes dans une configuration d'arbre ternaire
Exercice 2
On considère une tâche T décomposable en m sous tâches { Ti } i= 1,2,
...,m.
a) En supposant que l'exécution d'une tâche Ti prend une unité de temps,
calculer le temps nécessaire à un PIPELINE de m étapes pour exécuter N
tâches T.
b) La tâche T représente l'addition de deux nombres réels. Les réels sont
représentés en format scientifique (par exemple, 35.63 ---> .3563E+2). Une
addition est décomposée en quatre sous tâches ou opérations nécessitant
une unité de temps chacune :
T1 : Comparaison des exposants
T2 : Décalage de la virgule
T3 : Addition des mantisses
T4 : Normalisation du résultat Calculer le temps d'exécution d'une suite de N paires (ai, bi) i=1,2,3 ...N
sur un PIPELINE.
Calculer l'accélération et l'efficacité de la solution PIPELINE. Exercice 3
Soit l'expression E = (a + (b - c)/d)*(e - (((f - g)/h) * i ))
a) Dessiner l'arbre d'évaluation de cette expression et son graphe de
dépendances. Paralléliser au maximum le calcul de l'expression.
b) Calculer l'accélération, l'efficacité et le travail de la solution
parallèle en supposant que chaque opération arithmétique prend une unité de
temps.
c) En utilisant la propriété d'associativité, peut on modifier l'expression
E pour en accélérer le calcul ? Quels sont alors l'accélération,
l'efficacité et le travail résultant ? Exercice 4 Loi d'Amdhal
Soit T1 le temps d'exécution d'un programme A sur une machine séquentiel (à
1 processeur) et le temps Tp le temps d'une solution parallèle du programme
A sur une machine parallèle comprenant p processeurs. L'accélération de la
solution parallèle, notée S(p), est égale à
S(p) = T1 / Tp
a) S(p) peut - il être supérieur à P, c'est-à-dire peut on obtenir une
accélération surlinéaire ? Commentez et justifiez votre réponse.
b) Déterminer une borne supérieure de S(p) et montrer que S(p) ---> 1/f
lorsque p ---> ( .
(f = Ts/T1, T1 = Ts + T// où Ts est égal au temps d'exécution de la partie
séquentielle de A et T// est égal au temps d'exécution de la partie
parallélisable de A). Exercice 5
Une machine PRAM EREW est constituée d'une mémoire globale partagée MG, p
processeurs et p mémoire locales MLm (m=1,2,..p). La mémoire locale MLi
n'est accessible que par le processeur Pi. a) Proposer une méthode pour recopier un élément X en mémoire global
partagée MG dans les mémoires locales des processeurs Pi X en O(logp) unité
de temps.
b) Ecrire en pseudo code la méthode de a). Utiliser les primitives de
lectures et d'écritures globales étudiées en cours.
c) Ecrire en pseudo code une méthode pour recopier X de la mémoire globale
vers les mémoires locales d'une machine PRAM CREW. Donner le temps
d'exécution de la méthode.
d) En tenant compte de la loi d'Amdahl, quelles sont les propriétés qu'un
algorithme parallèle doit avoir pour que son efficacité soit bonne lorsque
le nombre de processeurs utilisés devient grand. Exercice 6 Soit X1, .... Xn n valeurs. Le calcul des préfixes des Xi consiste à
calculer les valeurs
Si = X1 + ....Xi-1.
a) Décrire une méthode pour calculer les préfixes des nombres Xi sur une
architecture hypercube composée de n processeurs.
b) Décrire une méthode pour calculer les préfixes de Xi sur une grille pxp
( n=p2) Exercice 7 Décrire un algorithme pour déterminer la valeur maximale de n nombres X1,
X2, ...Xn sur une grille pxp où n = p2. Exercice 8 Ecrire en pseudo code un algorithme pour une diffusion One-to-All d'une
valeur X0 d'un processeur vers les autres processeurs dans :
- réseau linéaire de n processeurs
- un anneau de n processeurs
- dans une grille pxp où n=p2