CS228 - Exercices corriges
Loi d'Amdhal ... La mémoire locale MLi n'est accessible que par le processeur Pi.
... d) En tenant compte de la loi d'Amdahl, quelles sont les propriétés qu'un ...
part of the document
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 quil 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 darbre binaire
8 personnes dans une configuration darbre 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 lexécution dune 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 laddition 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 dexécution dune suite de N paires (ai, bi) i=1,2,3
N sur un PIPELINE.
Calculer laccélération et lefficacité de la solution PIPELINE.
Exercice 3
Soit lexpression E = (a + (b c)/d)*(e (((f g)/h) * i ))
a) Dessiner larbre dévaluation de cette expression et son graphe de dépendances. Paralléliser au maximum le calcul de lexpression.
b) Calculer laccélération, lefficacité 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é dassociativité, peut on modifier lexpression E pour en accélérer le calcul ? Quels sont alors laccélération, lefficacité et le travail résultant ?
Exercice 4
Loi dAmdhal
Soit T1 le temps dexécution dun programme A sur une machine séquentiel (à 1 processeur) et le temps Tp le temps dune solution parallèle du programme A sur une machine parallèle comprenant p processeurs. Laccé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 dexécution de la partie séquentielle de A et T// est égal au temps dexé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 dAmdahl, quelles sont les propriétés quun 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
