Loi selon laquelle, lorsqu'on ne parallélise qu'une partie d'un programme, l'accélération globale est limitée par la partie non parallélisable. Par exemple, même en parallélisant 90 %, le gain ne dépasse pas 10 fois.
Nom japonais: アムダールの法則
« Loi d'Amdahl » apparaît dans 5 questions d'entraînement réparties sur 2 thèmes, dont Analyse des performances, CPU et architecture.
Domaine: CPU et architecture
La loi d'Amdahl donne l'accélération d'un programme dont une fraction p peut être parallélisée sur N processeurs : S = 1 / ((1 − p) + p/N). Lorsque N croît sans limite, le terme p/N s'annule et l'accélération tend vers 1 / (1 − p). Avec p = 0,9, ce plafond vaut 10×, et avec dix processeurs le résultat n'est que d'environ 5,3× : la moitié du matériel est en pratique gaspillée. La fraction séquentielle, aussi petite qu'elle paraisse, finit par dominer le temps d'exécution dès que la partie parallèle a été suffisamment découpée.
La loi s'applique à toute amélioration partielle, pas seulement à l'ajout de cœurs. Si une section occupant 50 % du temps d'exécution devient 4× plus rapide, le nouveau temps vaut 0,5 + 0,5/4 = 0,625 du temps initial, soit une accélération globale de 1,6×, et aucune optimisation supplémentaire de cette section ne peut dépasser 2×. Rendre infiniment rapide une partie qui occupe 1 % du temps ne fait gagner qu'environ 1 %. C'est le fondement quantitatif du principe « accélérer le cas courant » (make the common case fast) et la raison pour laquelle il faut profiler un programme avant de l'optimiser.
La loi d'Amdahl suppose une taille de problème fixe, ce qui correspond à la scalabilité forte (strong scaling) : le même travail est réparti sur davantage de processeurs. La loi de Gustafson suppose l'inverse : avec plus de processeurs, on résout un problème plus grand dans le même temps, par exemple une grille de simulation plus fine. Le travail parallèle croît avec le problème tandis que la partie séquentielle reste à peu près constante : la fraction séquentielle diminue et l'accélération croît presque proportionnellement au nombre de processeurs. C'est la scalabilité faible (weak scaling). Aucune des deux lois n'est fausse ; elles répondent à des questions différentes sur l'usage d'une charge de travail.
La loi d'Amdahl suppose déjà que la partie parallèle passe parfaitement à l'échelle : les accélérations mesurées sont donc généralement encore plus faibles. Les threads attendent sur des verrous et des barrières, les données partagées et le faux partage (false sharing) font rebondir les lignes de cache entre cœurs, une répartition inégale du travail laisse certains cœurs inactifs, et de nombreux threads peuvent saturer la bande passante mémoire. Le surcoût de communication et de synchronisation peut même croître avec N, si bien qu'ajouter des cœurs finit parfois par ralentir un programme. La meilleure scalabilité s'obtient lorsque chaque thread travaille surtout sur des données privées, avec peu de communication et d'attente.
Réponse : B. 1,6
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.
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.
On divise 1 par le nouveau temps d'exécution relatif : S = 1 / ((1 − p) + p/s), où p est la fraction du temps concernée et s le facteur d'accélération de cette partie (s = N pour N processeurs). Pour p = 0,5 et s = 4, on obtient 1 / 0,625 = 1,6×.
La limite est 1 / (1 − 0,95) = 20×, quel que soit le nombre de processeurs utilisés. Même s'approcher de cette limite exige un très grand nombre de processeurs et une efficacité parallèle quasi parfaite.
La loi d'Amdahl fixe la taille du problème et montre que la partie séquentielle plafonne l'accélération. La loi de Gustafson laisse le problème grandir avec le nombre de processeurs : la fraction séquentielle diminue et une accélération à l'échelle quasi linéaire devient possible.
Selon la loi d'Amdahl, avec p la fraction parallélisable et N le nombre de processeurs, l'accélération vaut 1/((1 − p) + p/N).
Pour un programme dont 90 % du traitement est parallélisabl…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.
Quelle idée la loi de Gustafson exprime-t-elle correctement…Conformément à la loi d'Amdahl, il est efficace d'améliorer les parties les plus consommatrices : mesurer est la première étape de l'amélioration des performances.
Quel est l'objectif correct de l'utilisation d'un profileur…Profileur Loi de Gustafson Architecture de von Neumann Architecture du jeu d'instructions (ISA) Cohérence de cache DMA (accès direct à la mémoire) DVFS (ajustement dynamique de la tension et de la fréquence) Exécution dans le désordre (out-of-order) GPU Interruption