Loi de Gustafson

Évolution selon la loi de Gustafson de l'accélération théorique en latence de l'exécution d'un programme en fonction du nombre de processeurs l'exécutant, pour différentes valeurs de p.

En architecture informatique, la loi de Gustafson donne l'accélération théorique en latence de l'exécution d'une tâche à temps d'exécution constant que l'on peut attendre d'un système dont on améliore les ressources. Elle est énoncée par l'informaticien John L. Gustafson et son collègue Edwin H. Barsis dans l'article Reevaluating Amdahl's Law en 1988^[1].

La loi de Gustafson peut être formulée de la façon suivante :

${\displaystyle S_{\text{latence}}(s)=1-p+sp,}$

où

• S_latence est l'accélération théorique en latence de l'exécution de toute la tâche ;
• s est l'accélération en latence de l'exécution de la partie de la tâche bénéficiant de l'amélioration des ressources du système ;
• p est le pourcentage de la charge d'exécution de toute la tâche concerné par la partie bénéficiant de l'amélioration des ressources du système avant l'amélioration.

La loi de Gustafson est souvent utilisée en calcul parallèle pour prédire l'accélération théorique lors de l'utilisation de plusieurs processeurs dans le cas où il est possible d'augmenter la quantité de données traitées, contrairement à la loi d'Amdahl, qui suppose une quantité de données constante. Elle traduit le fait que l'on peut traiter plus de données dans le même temps en augmentant le nombre de processeurs.

Démonstration

Une tâche exécutée par un système dont les ressources sont améliorées par rapport à un système similaire initial peut être séparée en deux parties :

• une partie ne bénéficiant pas de l'amélioration des ressources du système ;
• une partie bénéficiant de l'amélioration des ressources du système.

Exemple. — Un programme informatique qui traite les fichiers d'un disque. Une partie du programme commence par lire le répertoire du disque et créer une liste de fichiers en mémoire. Puis une autre partie du programme passe chaque fichier à un fil d'exécution pour traitement. La partie qui lit le répertoire et crée la liste de fichiers ne peut pas être accélérée sur un ordinateur parallèle, mais la partie qui traite les fichiers peut l'être.

La charge d'exécution de toute la tâche avant l'amélioration des ressources est notée C. Elle inclut la charge d'exécution de la partie ne bénéficiant pas de l'amélioration des ressources et la charge d'exécution de celle en bénéficiant. Le pourcentage de la charge d'exécution de toute la tâche correspondant à la partie bénéficiant de l'amélioration des ressources avant l'amélioration des ressources est noté p. Celui correspondant à la partie n'en bénéficiant pas est donc 1 − p. Il vient

${\displaystyle C=(1-p)C+pC.}$

C'est l'exécution de la partie bénéficiant de l'amélioration des ressources qui est accélérée d'un facteur s après l'amélioration des ressources. Par conséquent, la charge d'exécution de la partie n'en bénéficiant pas reste identique, tandis que celle de la partie en bénéficiant devient

${\displaystyle spC.}$

La charge d'exécution théorique C(s) de toute la tâche après l'amélioration des ressources est ainsi

${\displaystyle C(s)=(1-p)C+spC.}$

La loi de Gustafson exprime l'accélération théorique en latence de l'exécution de toute la tâche à temps d'exécution constant T, ce qui donne

${\displaystyle S_{\text{latence}}(s)={\frac {TC(s)}{TC}}={\frac {C(s)}{C}}=1-p+sp.}$

Conséquences

Plus le nombre de données traitées en parallèle est grand, plus l’utilisation d'un grand nombre de processeurs est efficace. Mais surtout, il n'y a pas de limite théorique à l'accélération : on peut mettre autant de données que l'on veut, celles-ci sont toutes traitées par un processeur simultanément et le temps mis pour traiter s données sur s processeurs sera identique au temps mis pour traiter une donnée sur un seul processeur. Aucune limite n'existe concernant la quantité de données traitables simultanément, et donc au gain que l'on peut obtenir.

Bien sûr, il faut se rappeler que la loi de Gustafson s'applique sur une durée déterminée : elle ne rend pas les calculs plus rapides.

Mais dans la réalité, la loi de Gustafson n'est pas utilisable directement. Dans des situations réelles, de nombreux autres paramètres interviennent, qui dépendent de l'architecture des processeurs utilisés, du langage de programmation utilisé et de la manière dont a été programmé le programme en question.

Références

1. Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM 31(5), 1988. pp. 532-533. Aussi au format web ici

Voir aussi

Articles connexes

• Loi d'Amdahl

• Portail de l’informatique