Université Sultan Moulay Slimane — Faculté Polydisciplinaire Beni Mellal
Master IOTR — Module : SoC et Programmation Parallèle
Série TD — Corrigé Détaillé
Notation utilisée (conforme au cours) : alpha = fraction parallélisable, (1-alpha) = fraction séquentielle. Loi
d'Amdahl : S(n) = 1 / (alpha/n + (1-alpha))
Exercice 01 : Graphe de dépendances — Somme parallèle (n=16)
Le graphe représente une réduction par arbre binaire (addition par paires successives). Avec n=16
éléments, les additions se font en log2(16) = 4 niveaux.
1. Temps d'exécution parallèle T(inf) — chemin critique :
Le chemin le plus long dans le graphe traverse log2(n) additions successives :
T(inf) = log2(16) = 4 unités de temps
2. Travail total T(1) :
Nombre total d'additions (toutes les opérations du graphe) :
T(1) = n - 1 = 16 - 1 = 15 additions
3. Nombre maximal de processeurs requis :
Au premier niveau, n/2 = 8 additions peuvent se faire simultanément. C'est le niveau le plus large :
P_max = n/2 = 16/2 = 8 processeurs
4. Coût :
Cout = P_max x T(inf) = 8 x 4 = 32
Conclusion : Le coût (32) est supérieur au travail (15). Tous les processeurs ne sont pas actifs à
chaque étage, ce qui induit une perte d'efficacité.
Exercice 02 : Speedup et efficacité
Données : T_seq = 100 s, T_par(4) = 30 s, p = 4 processeurs
1. Speedup :
S = T_seq / T_par = 100 / 30 = 3,33
2. Efficacite :
E = S / p = 3,33 / 4 = 0,833 (83,3 %)
3. Cause de la perte d'efficacite :
• Partie séquentielle incompressible du programme (loi d'Amdahl).
• Surcoûts de communication et synchronisation entre processeurs.
• Déséquilibre de charge (certains processeurs attendent).
4. Avec 8 processeurs, T_par(8) = 22 s :
S(8) = 100 / 22 = 4,55
E(8) = 4,55 / 8 = 0,569 (56,9 %)
Conclusion : En doublant le nombre de processeurs (4->8), le speedup n'a augmenté que de 3,33
a 4,55. L'efficacite chute de 83 % a 57 %. La partie séquentielle limite fortement le gain (loi
d'Amdahl).
Exercice 03 : Loi d'Amdahl — alpha = 75 %
Données : alpha = 0,75 => (1-alpha) = 0,25
Accélération maximale (n -> inf) :
S(inf) = 1 / (alpha/inf + (1-alpha)) = 1 / (0 + 0,25) = 1 / 0,25 = 4
Conclusion : Meme avec un nombre infini de processeurs, le speedup maximal est 4. La partie
séquentielle (25 %) est le goulot d'étranglement.
Exercice 04 : Loi d'Amdahl — alpha = 95 %, n = 8
Données : alpha = 0,95 => (1-alpha) = 0,05 ; n = 8 processeurs
Application de la loi d'Amdahl :
S(8) = 1 / (alpha/n + (1-alpha)) = 1 / (0,95/8 + 0,05)
S(8) = 1 / (0,11875 + 0,05) = 1 / 0,16875 = 5,93
Conclusion : Avec 8 processeurs et alpha=95 %, on obtient un speedup de 5,93. La limite
théorique (n->inf) serait 1/0,05 = 20, mais 8 processeurs n'y suffisent pas.
Exercice 05 : Speedup mesuré — 71 processeurs, partie séquentielle 11 %
Données : n = 71 processeurs, (1-alpha) = 0,11 => alpha = 0,89
Application de la loi d'Amdahl :
S(71) = 1 / (alpha/n + (1-alpha)) = 1 / (0,89/71 + 0,11)
S(71) = 1 / (0,01254 + 0,11) = 1 / 0,12254 = 8,16
Conclusion : Malgré 71 processeurs, la partie séquentielle (11 %) limite l'accélération a environ
8,16.
Exercice 06 : Nombre minimal de processeurs pour S = 10, (1-alpha) = 6 %
Données : (1-alpha) = 0,06 => alpha = 0,94 ; S souhaité = 10
On résout la loi d'Amdahl en n :
S(n) = 1 / (alpha/n + (1-alpha)) => 10 = 1 / (0,94/n + 0,06)
0,94/n + 0,06 = 1/10 = 0,1 => 0,94/n = 0,04 => n = 0,94 / 0,04 = 23,5
=> n_min = 24 processeurs
Verification : S(24) = 1/(0,94/24 + 0,06) = 1/(0,03917 + 0,06) = 1/0,09917 = 10,08 > 10 OK
Exercice 07 : Fraction séquentielle maximale — S = 8 sur 12 processeurs
Données : S = 8, n = 12. On cherche (1-alpha).
Inversion de la loi d'Amdahl :
1/S = alpha/n + (1-alpha) => 1/8 = alpha/12 + (1-alpha)
0,125 = alpha/12 + 1 - alpha
0,125 - 1 = alpha/12 - alpha => -0,875 = alpha(1/12 - 1) = alpha(-11/12)
alpha = 0,875 x 12/11 = 10,5/11 = 0,9545
(1-alpha) = 1 - 0,9545 = 0,0455 (≈ 4,55 %)
Conclusion : La fraction séquentielle maximale compatible avec S=8 sur 12 processeurs est
d'environ 4,55 %.
Exercice 08 : Loi d'Amdahl — (1-alpha) = 15 %
Données : (1-alpha) = 0,15 => alpha = 0,85
1. Speedup théorique avec 4, 8 et 32 processeurs :
S(n) = 1 / (0,85/n + 0,15)
n (processeurs) Calcul détaillé Speedup S(n)
4 1 / (0,85/4 + 0,15) = 1 / (0,2125 + 0,15) = 1/0,3625 ≈ 2,76
8 1 / (0,85/8 + 0,15) = 1 / (0,10625 + 0,15) = 1/0,25625 ≈ 3,90
32 1 / (0,85/32 + 0,15) = 1 / (0,02656 + 0,15) = 1/0,17656 ≈ 5,66
2. Limite quand n -> inf :
S(inf) = 1 / (0 + 0,15) = 1 / 0,15 = 6,67
3. Conclusion :
Le speedup plafonne a 6,67 quelle que soit la quantité de processeurs. Au-dela de 32, le gain
marginal devient négligeable. Réduire la partie séquentielle (15 %) est plus efficace
qu'augmenter le nombre de processeurs.
Exercice 09 : Calcul du speedup maximal selon Amdahl
Rappel : S(n) = 1 / (alpha/n + (1-alpha)) ; S(inf) = 1/(1-alpha)
1. (1-alpha) = 1/10 = 0,1 => alpha = 0,9
S(n) = 1 / (0,9/n + 0,1)
Exemple : S(10) = 1/(0,09+0,1) = 1/0,19 ≈ 5,26 | S(100) = 1/(0,009+0,1) ≈ 9,17
S_max = S(inf) = 1/(1-alpha) = 1/0,1 = 10
2. (1-alpha) = 1/100 = 0,01 => alpha = 0,99
S_max = S(inf) = 1/0,01 = 100
Conclusion : Réduire la fraction séquentielle de 10 % a 1 % multiplie par 10 le speedup maximal
atteignable (de 10 a 100).
Exercice 10 : Processeur 4 coeurs — Deux applications
Données : n = 4 coeurs. App1 : 60 % des ressources, alpha1 = 0,80 => (1-alpha1) = 0,20. App2 : 40 %
des ressources, alpha2 = 0,90 => (1-alpha2) = 0,10.
1. Gain de l'App1 seule sur 4 processeurs :
S1 = 1 / (alpha1/n + (1-alpha1)) = 1 / (0,80/4 + 0,20) = 1 / (0,20 + 0,20) = 1/0,40 = 2,5
2. Gain de l'App2 seule sur 4 processeurs :
S2 = 1 / (alpha2/n + (1-alpha2)) = 1 / (0,90/4 + 0,10) = 1 / (0,225 + 0,10) = 1/0,325 = 3,08
3. Gain global si seule App1 est parallélisée (App2 non améliorée => S_App2 = 1) :
Loi d'Amdahl généralisée : S_global = 1 / (fraction_App1/S1 + fraction_App2/S_App2)
S_global = 1 / (0,60/2,5 + 0,40/1) = 1 / (0,24 + 0,40) = 1/0,64 = 1,5625
4. Gain global si les deux applications sont parallélisées :
S1 = 2,5 (Q1), S2 = 3,08 (Q2)
S_global = 1 / (0,60/2,5 + 0,40/3,08) = 1 / (0,240 + 0,130) = 1/0,370 = 2,70
Conclusion : Paralléliser les deux applications donne un gain global de 2,70 contre 1,56 si on ne
parallélise que App1. Meme App2 (40 % des ressources) contribue significativement au gain
global.
— Fin du corrigé —