Français
Menu

Loi d'Amdahl vs loi de Gustafson : hypothèses et scalabilité

Les deux lois estiment de combien un calcul s'accélère lorsqu'on ajoute des processeurs, mais elles reposent sur des hypothèses différentes. La loi d'Amdahl fixe la taille du problème et considère comment terminer plus vite le même travail : la partie non parallélisable fixe alors la limite de l'accélération. La loi de Gustafson fixe le temps d'exécution et considère comment résoudre un problème d'autant plus grand qu'on ajoute des processeurs : l'accélération croît alors presque proportionnellement au nombre de processeurs. Les deux ne se contredisent pas : elles répondent à des questions différentes.

CritèreLoi d'AmdahlLoi de Gustafson
Ce qui est fixéLa taille du problème (quantité totale de travail)Le temps d'exécution (quantité de travail par processeur)
QuestionÀ quel point peut-on résoudre plus vite le même problème ?Quelle taille de problème peut-on résoudre dans le même temps ?
Formule (N : nombre de processeurs)S = 1 / ((1 − p) + p / N)S = s + (1 − s) × N = N − s × (N − 1)
Mesure de la fractionp est la part du temps occupée par la partie parallélisable lors d'une exécution sur 1 processeurs est la part du temps occupée par la partie séquentielle lors d'une exécution parallèle sur N processeurs
Quand N augmentePlafonne à 1 / (1 − p)Continue de croître presque proportionnellement à N
Exemple de calculAvec p = 0,95 : environ 17 fois pour N = 100 ; même avec N infini, la limite est de 20 foisAvec s = 0,05 : environ 95 fois pour N = 100
Mise à l'échelle correspondanteScalabilité forteScalabilité faible
Point de vuePessimiste. Une petite partie séquentielle fixe la limiteOptimiste. Agrandir le problème rend la parallélisation rentable
Exemples adaptésLorsqu'on veut traiter rapidement une entrée de taille fixe : traitement d'une image, réponse interactive, etc.Simulations avec un maillage plus fin, ou lorsqu'on veut traiter des données ou des modèles plus grands dans le même temps
Ce que les deux ignorentSurcoût de communication et de synchronisation, déséquilibre de charge, bande passante mémoire insuffisanteSurcoût de communication et de synchronisation, déséquilibre de charge, bande passante mémoire insuffisante

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

Loi d'Amdahl
Lorsque la taille du problème est fixée et qu'on veut réduire le temps de réponse. Elle sert à estimer la limite de la parallélisation et à juger s'il faut réduire la partie séquentielle.
Loi de Gustafson
Lorsque le problème peut grandir avec le nombre de processeurs. Elle sert à estimer l'intérêt de calculer plus finement et plus grand dans les simulations et traitements de données à grande échelle.
Présentation des résultats
Lorsqu'on rapporte des performances parallèles, on précise si elles ont été mesurées en scalabilité forte ou faible. Si les conditions diffèrent, l'accélération d'un même programme peut varier fortement.

Questions fréquentes

Les deux lois ne se contredisent-elles pas ?

Non. La loi d'Amdahl fixe la taille du problème et la loi de Gustafson le temps d'exécution : elles répondent à des questions différentes. De plus, la part de la partie séquentielle se mesure, pour Amdahl, sur le temps d'exécution sur 1 processeur et, pour Gustafson, sur le temps d'exécution sur N processeurs ; on ne peut donc pas les comparer en y injectant la même valeur.

Pourquoi, avec 90 % de code parallélisable, n'obtient-on au mieux que 10 fois plus vite ?

Parce que les 10 % restants ne raccourcissent pas, quel que soit le nombre de processeurs ajoutés. Même si le temps de la partie parallèle tend vers zéro, le temps total ne descend pas sous 10 % du temps initial, et l'accélération plafonne donc à 1 / 0,1 = 10 fois.

Pourquoi l'accélération réelle est-elle inférieure aux prévisions de ces lois ?

Parce qu'aucune des deux lois ne tient compte de la communication et de la synchronisation entre processeurs, du déséquilibre de charge ni de l'insuffisance de la bande passante mémoire partagée. Plus il y a de processeurs, plus ces effets sont importants et plus l'efficacité parallèle baisse.

Quelle loi appliquer à mon programme ?

Si la taille d'entrée est fixée et que vous voulez obtenir le résultat plus vite, c'est la loi d'Amdahl. Si vous voulez traiter un maillage plus fin ou des données plus grandes à mesure que les processeurs augmentent, c'est la loi de Gustafson. Pour un même programme, la loi applicable dépend de l'usage qu'on en fait.

Vérifier vos connaissances

Pour un programme dont 90 % du traitement est parallélisable, quelle est l'accélération théorique maximale lorsque le nombre de processeurs tend vers l'infini ?

  1. A10 fois
  2. B90 fois
  3. CInfinie
Afficher la réponse et l'explication

Réponse : A. 10 fois

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 p = 0,9, même avec N infini, la limite est 1/0,1 = 10 fois, et avec N = 10 on n'obtient qu'environ 5,3 fois. La moindre partie non parallélisable fixant la limite, il est essentiel de réduire la partie séquentielle. L'approche consistant à augmenter la taille du problème pour accroître la partie parallèle est la loi de Gustafson.

Une partie représentant 50 % du traitement total est rendue 4 fois plus rapide. Quelle est l'accélération globale (loi d'Amdahl) ?

  1. A2
  2. B1,6
  3. C4
Afficher la réponse et l'explication

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.

Quel est l'enseignement le plus approprié de la loi d'Amdahl concernant la démarche d'amélioration des performances ?

  1. AAccélérer en priorité les parties qui consomment beaucoup de temps (le cas fréquent)
  2. BAccélérer d'abord les parties rarement exécutées
  3. 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.

  1. Quelle idée la loi de Gustafson exprime-t-elle correctement ?
  2. Quelle est la différence correcte entre « scalabilité forte » et « scalabilité faible » dans l'évaluation du calcul parallèle ?
  3. Comment calcule-t-on correctement l'« accélération » (speedup) exprimant une amélioration des performances ?

Questions d'entraînement sur Analyse des performances

Termes clés expliqués

Loi d'Amdahl
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.
Loi de Gustafson
Idée selon laquelle, si l'on agrandit le problème en même temps qu'on augmente le nombre de processeurs, la part parallélisable croît et le gain devient presque proportionnel au nombre de processeurs.
Mise à l'échelle forte (strong scaling)
Évaluation des performances parallèles qui mesure la réduction du temps lorsqu'on augmente le nombre de processeurs à taille de problème fixe.
Mise à l'échelle faible (weak scaling)
Évaluation des performances parallèles qui fixe la taille du problème par processeur, augmente la taille totale et vérifie si le temps reste constant.
Efficacité parallèle
Accélération obtenue par parallélisation divisée par le nombre de processeurs. Elle indique dans quelle mesure les cœurs sont utilisés efficacement.

Comparatifs associés