Dernière mise à jour : 2026-06-29

La loi de Gustafson

La loi de Gustafson estime l’accélération d’un programme parallèle lorsque la taille du problème croît en même temps que le nombre de processeurs. Elle reformule la question de mise à l’échelle posée par la loi d’Amdahl : au lieu de fixer la charge de travail et de raccourcir l’exécution, elle fixe le budget de temps et demande quelle quantité de travail supplémentaire une machine plus grande peut accomplir. Le calculateur prend la fraction parallélisable de l’exécution et un nombre de processeurs, puis renvoie l’accélération à l’échelle et l’efficacité parallèle.

Temps fixe plutôt que travail fixe

Lorsqu’on acquiert une grappe plus grande, on n’exécute souvent pas le même travail plus vite — on exécute un travail plus grand dans le même temps. Un modèle météorologique passe à une grille plus fine, un moteur de rendu produit davantage d’images, un entraînement ingère plus de données. Dans ce contexte, la portion parallèle du travail s’étend pour occuper les processeurs ajoutés, tandis que la surcharge série (démarrage, coordination, agrégation finale) reste à peu près constante.

La loi de Gustafson rend compte de ce phénomène. Soit $p$ la fraction du temps d’exécution correspondant au travail parallèle telle qu’elle est mesurée sur le système parallèle, et $1 - p$ la fraction série partagée par chaque processeur. L’accélération à l’échelle sur $N$ processeurs vaut :

$S = (1 - p) + p \cdot N$

Comme le terme parallèle croît linéairement avec $N$, l’accélération prévue continue d’augmenter à mesure que des processeurs sont ajoutés, au lieu de s’aplatir contre un plafond.

Exemple résolu

Supposons que 95 % de l’exécution sur un système à 16 processeurs corresponde à du travail parallèle. L’accélération à l’échelle vaut :

Ainsi, le système à 16 processeurs accomplit environ 15,25× le travail d’un seul processeur dans le même temps réel, pour une efficacité parallèle de $15{,}25 / 16 \approx 95\%$. À comparer avec la vision à taille fixe, où la même fraction parallèle de 95 % limite l’accélération à environ 9,1× sur 16 processeurs et à 20× à la limite.

Passage à l’échelle fort et passage à l’échelle faible

La différence entre les deux lois est celle qui sépare le passage à l’échelle fort du passage à l’échelle faible. Le passage à l’échelle fort — le régime de la Calculateur de la loi d’Amdahl — maintient le problème fixe et se trouve borné par la fraction série. Le passage à l’échelle faible — le régime de la loi de Gustafson — fait croître le problème avec le matériel et évolue presque linéairement. Aucune des deux lois n’est universellement correcte ; le bon choix dépend de la nature de la charge de travail, fixe ou amenée à occuper les ressources qu’on lui attribue.

Comme la fraction parallélisable est mesurée sur le système à l’échelle et dépend de la taille du problème, le résultat doit être traité comme une estimation du comportement attendu plutôt que comme une garantie précise. Estimer l’accélération selon les hypothèses de Gustafson et d’Amdahl encadre la plage probable.