Loi de Gustafson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La loi de Gustafson est une loi théorique qui permet d'obtenir une borne maximale au gain que l'on peut avoir en utilisant plusieurs processeurs pour paralléliser du code via parallélisme de données.

Cette loi donne le gain que l'on peut avoir avec N processeurs en exécutant un programme parallélisé dans le cas où il est possible d'augmenter la quantité de données traitées, contrairement à la loi d'Amdahl, qui s'applique à quantité de données fixe. Elle traduit le fait qu'on peut traiter plus de données en augmentant le nombre de processeurs.

Elle dit que le gain de vitesse est égal à S + ( N \times P ), avec :

  • S le pourcentage de code non-parallélisable ;
  • P le pourcentage de code parallélisable ;
  • et N le nombre de processeurs.

Démonstration[modifier | modifier le code]

Prenons un programme s’exécutant sur un seul processeur. Ce programme contient une certaine quantité de code qui ne peut être parallélisé : on appelle ce code le code série. Inversement, une partie du programme pourra être exécutée : c'est le code parallèle. Tout programme prend un temps Ts à exécuter son code série et un temps Tp pour exécuter son code parallèle. Dans tous les cas, le temps d’exécution total du programme, noté T, vaut Ts + Tp.

Hypothéses de départ[modifier | modifier le code]

Dans la démonstration de la loi de Gustafson, ce code parallèle s’exécute soit sur une donnée (image, fichier son, pixel ou autre) soit sur plusieurs données : ainsi, pour N données, on pourra prendre N processeurs et exécuter sur chacun d'eux le code parallèle sur une des N données.

En prenant 1 ou N processeurs, la partie série restera la même et sera exécutée sur un seul processeur durant un temps Ts. Avec une seule donnée, le temps d’exécution T est égal à Ts + Tp, avec Ts le temps d’exécution du code série et Tp celui du code parallèle. Par contre, durant le temps Tp, on pourra demander à chacun des N processeurs de traiter une donnée en un temps Tp. Ce qui fait qu'en un temps T, on peut demander à notre processeur d’exécuter un programme sur N données.

Si ce calcul fait sur ces N données avait été fait sur un seul processeur, on aurait dû calculer ces N données unes par une, ce qui aurait pris un temps égal à T = Ts + ( N \times Tp )

Gain[modifier | modifier le code]

Pour connaitre les gains dus à l'utilisation de N processeurs comparé à un seul, il nous faut calculer un paramètre nommé le speed-up. Ce speed-up a une signification simple : si le speed-up vaut X, alors l'application est X fois plus rapide que si on l’exécutait sur un seul processeur. On verra ainsi si le programme s’exécute 2, 3, voir 50 fois rapidement. Bien évidemment, plus ce speed-up est élevé, plus notre programme aura gagné en performance comparé à la version avec un seul processeur.

Dans notre cas, le speed-up vaut : \frac {T} {T(N)}.

Cette équation se simplifie en : \frac {Ts + ( N \times Tp )} {Ts + Tp}.


Cette équation se factorise en : \frac {Ts} {Ts + Tp} + \frac { N \times ( Tp )} {Ts + Tp}.


En remarquant que {Ts + Tp} est égal au temps d’exécution total du programme, on trouve la loi de Gustafson.


En remarquant que S = 1 - P, on peut aussi écrire cette loi comme ceci : Gain = 1 - P + ( N \times P )

Conséquences[modifier | modifier le code]

Plus le nombre de données traitées en parallèles est grand, plus l’utilisation d'un grand nombre de processeurs est efficace. En effet, sur un seul processeur, si on augmente le nombre N de données, et que ces N données doivent être traitées par la partie parallélisée du programme, cela prendrait un temps égal à Ts + ( Tp \times N )

Mais surtout, il n'y a pas de limites théoriques à N : on peut mettre autant de données que l'on veut, avec N processeurs, celles-ci sont toutes traitées par un processeur simultanément et le temps mis pour traiter N données sur N processeurs sera identique au temps mit 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 : si une donnée N met un temps T à être traitée, alors on ne gagne rien en termes de temps de calcul.

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.