Saisissez la fraction d’un programme exécutable en parallèle et le nombre de processeurs (cœurs) pour voir de combien l’ensemble du programme est accéléré selon la loi d’Amdahl. Un graphique log-log compare cette limite à taille de problème fixe avec l’approche de Gustafson, dans laquelle le problème grandit avec le nombre de processeurs.
Résultats
Accélération (loi d’Amdahl)
–
Efficacité parallèle
–
Accélération limite 1/(1−p)
–
Accélération mise à l’échelle (loi de Gustafson)
–
La fine ligne pointillée représente l’accélération linéaire idéale (N fois), la ligne bleue la loi d’Amdahl et la ligne verte la loi de Gustafson. Les deux axes sont logarithmiques. Les surcoûts liés à la communication, à la synchronisation et au déséquilibre de charge ne sont pas pris en compte ; les accélérations réelles sont donc généralement plus faibles.
Voir sous forme de graphique
Les autres entrées gardent leur valeur actuelle tandis que l'entrée choisie varie de 1/4 à 4 fois sa valeur actuelle. Le point rouge est la valeur actuelle.
La formule de la loi d’Amdahl
Prenons le temps d’exécution sur un seul processeur égal à 1 et notons p la fraction parallélisable. Avec N processeurs, la partie parallèle se réduit à p/N, mais la partie séquentielle (1 − p) reste inchangée ; l’accélération vaut donc S = 1/((1 − p) + p/N). Aussi grand que devienne N, la partie séquentielle ne disparaît jamais : l’accélération est plafonnée à 1/(1 − p). Avec les valeurs par défaut p = 95 % et N = 16, S ≈ 9,14 et la limite vaut 20. Seulement 5 % de travail séquentiel suffisent à fixer la vitesse maximale que le programme pourra jamais atteindre.
Lire l’efficacité et le graphique
L’efficacité parallèle, E = S/N, indique la part de travail utile fournie par chaque processeur. Avec les valeurs par défaut, elle vaut 9,14 ÷ 16 ≈ 57,1 % : plus de 40 % de la capacité de traitement reste en pratique inutilisée. Sur le graphique, la ligne bleue suit la ligne idéale pointillée pour les petites valeurs de N, puis s’en écarte et s’aplatit vers la limite. En gardant p = 95 % et en portant N à 64, on obtient S ≈ 15,4 et une efficacité d’environ 24 % seulement. Le point où l’efficacité commence à chuter rapidement donne une indication pratique du nombre de processeurs qui valent leur coût.
En quoi la loi de Gustafson diffère
La loi d’Amdahl suppose une taille de problème fixe pendant que l’on ajoute des processeurs : c’est la mise à l’échelle forte (strong scaling). La loi de Gustafson fait au contraire croître le problème avec le nombre de processeurs et le résout dans le même temps : c’est la mise à l’échelle faible (weak scaling), qui donne S = (1 − p) + p·N. Lorsqu’on affine le maillage d’une simulation, par exemple, seul le travail parallèle augmente, si bien que l’accélération croît presque proportionnellement à N. Notez que p désigne ici la fraction du temps mesurée sur l’exécution à N processeurs, ce qui n’est pas la même définition que le p de la loi d’Amdahl.
Utilisation en conception réelle
Les programmes réels ajoutent le lancement des threads, les communications de données, les attentes aux verrous et aux barrières ainsi que le déséquilibre de charge ; les accélérations effectives restent donc inférieures à la prédiction d’Amdahl. Réduire la partie séquentielle est souvent plus efficace qu’ajouter des cœurs : la pratique habituelle consiste à profiler d’abord, puis à paralléliser les points chauds. Sur les GPU, les transferts de données vers et depuis l’hôte ainsi que les lancements de noyaux se comportent eux aussi comme des parties séquentielles. En conception de puces, associer quelques cœurs hautes performances à de nombreux petits cœurs permet d’accélérer à la fois les parties séquentielles et parallèles d’une charge de travail.
Le temps après amélioration est la somme des 50 % non accélérés (0,5) et des 50 % accélérés 4 fois (0,5 ÷ 4 = 0,125), soit 0,625. L'accélération vaut 1 ÷ 0,625 = 1,6. Quelle que soit l'accélération de la partie améliorée, les 50 % restants subsistent, si bien que le gain global ne peut dépasser 2. Pour accélérer fortement l'ensemble, il faut identifier et améliorer les parties qui occupent le plus de temps.
AAccélérer en priorité les parties qui consomment beaucoup de temps (le cas fréquent)
BAccélérer d'abord les parties rarement exécutées
CQuelle que soit la partie accélérée, l'effet global est le même
Afficher la réponse et l'explication
Réponse : A. Accélérer en priorité les parties qui consomment beaucoup de temps (le cas fréquent)
Accélérer infiniment une partie qui n'occupe que 1 % du temps n'accélère l'ensemble que d'environ 1 %. À l'inverse, doubler la vitesse d'une partie occupant 80 % du temps rend l'ensemble environ 1,7 fois plus rapide. La démarche de base consiste donc à repérer, par exemple avec un profileur, les parties les plus consommatrices de temps et à commencer par elles. « Rendre le cas fréquent rapide » est un principe récurrent de la conception des ordinateurs.
ASi l'on augmente la taille du problème en même temps que le nombre de processeurs, la part parallélisable augmente et l'on obtient une forte accélération
BQuel que soit le nombre de processeurs ajoutés, l'accélération est toujours plafonnée à 2
CLa part parallélisable est toujours constante, quelle que soit la taille du problème
Afficher la réponse et l'explication
Réponse : A. Si l'on augmente la taille du problème en même temps que le nombre de processeurs, la part parallélisable augmente et l'on obtient une forte accélération
La loi d'Amdahl considère l'ajout de processeurs à taille de problème constante : la part non parallélisable fixe alors la limite de l'accélération. La loi de Gustafson considère qu'avec plus de processeurs, on résout un problème plus grand dans le même temps. Agrandir le problème, par exemple en affinant le maillage d'une simulation, accroît la part parallèle et réduit la proportion séquentielle, d'où un gain presque proportionnel au nombre de processeurs.
L'efficacité parallèle est l'accélération divisée par le nombre de cœurs ; elle indique dans quelle mesure les cœurs sont utilisés efficacement. 6 ÷ 8 = 75 % : on obtient les trois quarts de l'effet idéal (8 fois). Les 25 % restants sont perdus en attentes de synchronisation, déséquilibre de charge, communications, concurrence pour la bande passante mémoire, etc. L'efficacité parallèle tendant à baisser avec le nombre de cœurs, on choisit le nombre de cœurs en observant jusqu'où elle se maintient.
Questions fréquentes
De combien un programme parallèle à 90 % peut-il être accéléré ?
Selon la loi d’Amdahl, la limite est de 1/(1 − 0,9) = 10 fois. Même avec 16 processeurs, l’accélération n’est que de 1/(0,1 + 0,9/16) = 6,4, soit une efficacité de 40 %. Tant que les 10 % de travail séquentiel restants ne sont pas réduits, l’accélération ne peut jamais dépasser 10.
La loi d’Amdahl et la loi de Gustafson se contredisent-elles ?
Non. La loi d’Amdahl traite de la mise à l’échelle forte, à taille de problème fixe, tandis que la loi de Gustafson traite de la mise à l’échelle faible, où le problème grandit avec le nombre de processeurs. Le point de vue qui s’applique dépend de l’objectif : résoudre le même problème plus vite, ou un problème plus grand dans le même temps.
L’efficacité parallèle peut-elle dépasser 100 % ?
Oui. Lorsque l’ajout de processeurs réduit suffisamment la part de données de chaque processeur pour qu’elle tienne dans son cache, les accès mémoire deviennent plus rapides et une accélération superlinéaire peut apparaître. La loi d’Amdahl ne modélise pas ce type d’effet.