Bref – lois

Quelques raccourcis :

Proportion parallélisable d'un traitement
- Fraction sérielle
- Accélération relative
Loi d'Amdahl
- Transgresser la loi d'Amdahl
Loi de Gustafson
- Fraction sérielle échelonnable
- Illustration de la loi de Gustafson

Le nom le dit : ceci n'est qu'un bref, pas une description exhaustive du sujet.

Ce qui suit décrit très brièvement les principales lois associées au parallélisme et aux gains en termes de « performances » (au sens large) que cette approche peut apporter.

Mise en contexte

Le parallélisme est typiquement une question de débit de traitement. Transformer un algorithme séquentiel en un « équivalent » parallèle a typiquement pour impact, présumant que les conditions s'y prêtent et que la parallélisation soit bien réalisée, d'accélérer l'exécution du programme résultant.

Il est toutefois généralement admis que, dans un algorithme, il y ait une partie parallélisable et une partie qui ne l'est pas. La partie d'un programme qui n'est pas parallélisable est ce qui doit être fait de manière séquentielle, et comprend souvent en particulier la phase d'initialisation d'un algorithme et celle de sa finalisation.

Lorsque des efforts sont investis dans la parallélisation d'un algorithme, la question du retour sur l'investissement se pose. Le jeu en vaut-il la chandelle? Jusqu'où est-il pertinent d'investir des efforts en ce sens? Pour répondre à ces questions, un effort analytique est pertinent. Les sections qui suivent présentent des résultats théoriques importants, à tout le moins d'un point de vue historique, à propos de la parallélisation des programmes et de ce que cela peut rapporter.

Proportion parallélisable d'un traitement

Le temps total d'exécution d'un programme sur une seule unité d'exécution peut se représenter par l'équation à droite.

On y voit une conceptualisation légitime, à l'effet que le temps total de traitement $T_{total}(1)$ sur une unité d'exécution est la somme :

Du temps d'initialisation $T_{init}$
Du temps d'exécution $T_{trait}(1)$ sur une seule unité d'exécution, et
Du temps de finalisation $T_{final}$

\[ T_{total}(1)=T_{init} + T_{trait}(1) + T_{final} \]

Présumant que le traitement soit parallélisable sur $P$ unités d'exécution, sans changer la complexité de l'algorithme en le faisant passer de séquentiel à parallèle, et si l'initialisation et la finalisation doivent demeurer séquentiels, nous avons ce que vous voyez à droite.

Cette équation décrit un idéal essentiellement inatteignable en pratique, mais vers lequel on cherchera à tendre.

\[ T_{total}(P)=T_{init} + \frac{T_{trait}(1)}{P} + T_{final} \]

Pour comprendre les enjeux, examinons le cas d'un algorithme hypothétique ayant une partie séquentielle initiale de $5$ unités de temps, une partie finale séquentielle de $5$ unités de temps, et une partie parallélisable idéalisée de $100$ unités de temps.

Illustration
$T_{init}$	$T_{trait}(1)$	$T_{final}$	$T_{total}(1)$	$P$	$\frac{T_{trait}(1)}{P}$	$T_{total}(P)$	$1-\frac{T_{total}(P)}{T_{total}(1)}$
$5$	$100$	$5$	$110$	$1$	$100$	$110$	$0$
$5$	$100$	$5$	$110$	$2$	$50$	$60$	$0,45$
$5$	$100$	$5$	$110$	$4$	$25$	$35$	$0,68$
$5$	$100$	$5$	$110$	$8$	$12,5$	$22,5$	$0,8$
$5$	$100$	$5$	$110$	$16$	$6,25$	$16,25$	$0,85$

Ce qu'il faut voir ici est que le retour sur l'investissement est de moins en moins grand alors que la partie séquentielle prend plus de place en proportion du temps total de calcul :

Passer d'une unité de traitement à deux entraîne un fort gain de $45\%$
Passer à quatre unités de traitement offre un gain de $68\%$ , donc un peu plus de $22\%$ par unité de traitement (bien moins que le $45\%$ pour la première unité de traitement mise à contribution)
Passer à huit unités de traitement entraîne un gain total de $80\%$ du temps d'exécution, mais il s'agit d'environ $11\%$ par unité de traitement supplémentaire
Enfin, avoir recours à $16$ unités de traitement donne un gain total appréciable de $85\%$ sur l'algorithme purement séquentiel, mais ce gain correspond à environ $5\%$ par unité de traitement

Fraction sérielle

On peut exprimer la même idée d'un autre angle, soit en isolant la partie « incompressible » d'un algorithme.

Les parties qui ne peuvent être parallélisées représentent une fraction $\gamma$ qu'on nomme la fraction sérielle (« sériel » étant à prendre au sens de « non-parallèle »). Cette fraction s'exprime comme proposé à droite.

La proportion d'un programme qui peut être parallélisée est alors exprimée par $(1 - \gamma)$ . Cette écriture est utile pour comprendre la loi d'Amdahl, survolée plus bas.

\[ \gamma=\frac{T_{init}+T_{final}}{T_{total}(1)} \]

Combinant le tout, on obtient que le temps total pour $P$ unités de traitement est la fraction sérielle du temps total sur une unité de traitement, à quoi on ajoute la fraction parallélisable du temps total sur une unité de traitement divisée par $P$ :

\[ T_{total}(P)=\gamma \times T_{total}(1)+\frac{(1-\gamma) \times T_{total}(1)}{P} \]

Voilà notre point de départ.

Accélération relative

L'accélération relative obtenue en passant d'une à $P$ unités de traitement peut donc s'exprimer comme proposé à droite. Pensez à $S(P)$ pour Speedup on $P$ Processors.

\[ S(P)=\frac{T_{total}(1)}{T_{total}(P)} \]

Loi d'Amdahl

En simplifiant un peu, il est possible d'exprimer l'accélération $S(P)$ sur $P$ unités de traitement comme suit :

\[ S(P) = \frac{T_{total}(1)}{(\gamma+\frac{1-\gamma}{P})T_{total}(1)} = \frac{1}{\gamma + \frac{1-\gamma}{P} } \]

Amdahl, Gene (Avril 1967) "The validity of the single processor approach to achieving large-scale computing capabilities". In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483-85

Cette écriture est l'une de celles utilisées pour exprimer ce qu'on nomme loi d'Amdahl, du nom de son auteur, Gene Amdahl, qui oeuvrait alors chez IBM.

Cette loi exprime l'accélération maximale de l'exécution résultant de l'introduction de parallélisme dans un programme, pour un programme de complexité connue au préalable et dont la complexité de la section séquentielle est indépendante du nombre d'unités de traitement.

Il se trouve donc que :

\[ \lim_{P \to \infty}S(P)=\frac{1}{\gamma} \]

...ce qui indique un plafond théorique aux gains possibles suite à l'introduction de parallélisme dans un programme.

Transgresser la loi d'Amdahl

Dans son texte Break Amdahl's Law, Herb Sutter présente cette même loi selon l'écriture suivante, où $Seq$ est la partie séquentielle, $N$ est le nombre d'unités de traitement alors que $P$ est la partie parallélisable :

\[ S(N)=\frac{Seq + P}{Seq + \frac{P}{N}} \]

Cette écriture met en relief le caractère incompressible de la partie séquentielle, du fait que, proposé sous cette forme :

\[ \lim_{N \to \infty}S(N)=\frac{Seq + P}{Seq} \]

En gros, cela nous indique que la partie séquentielle incompressible limite les gains potentiels de la partie parallélisable.

Les a priori de la loi d'Amdahl sont contraignants, cela dit. Sutter, dans son texte, mentionne qu'il est possible de tricher du fait que $Seq$ et $P$ (selon son écriture) ne sont pas fixés. Cela nous suggère qu'il soit avantageux de repenser les algorithmes pour rapprocher le traitement $P$ d'une situation de parallélisme plus important.

Loi de Gustafson

Gustafson, J. L., "Reevaluating Amdahl's Law" (1988). Communications of the ACM 31(5), pp. 532-33 .

Cette loi tire aussi son nom de son auteur, John L. Gustafson, qui travaille chez Intel au moment d'écrire ces lignes. Elle peut s'exprimer de diverses manières.

Selon Herb Sutter, elle s'exprime comme suit (à droite), où $W(N)$ est le travail pouvant être accompli avec $N$ unités de traitement, $S$ est la partie séquentielle (non-parallélisable) du traitement et $P$ en est la partie parallélisable.	\[ W(N)=S+NP \]
Une autre écriture possible pour cette loi, et qu'on rencontrera dans la littérature, est celle à droite, où $S(P)$ est l'accélération pour $P$ unités de traitement, et $\alpha$ est la partie non-parallélisable du traitement.	\[ S(P)=P - \alpha(P-1) \]
Enfin, exprimé dans les termes de la loi d'Amdahl, on a l'équation à droite, qui tient compte de ce que donnerait sur une seule unité de traitement $P$ fois le traitement parallélisable qu'on pourrait réaliser sur $P$ unités de traitement.	\[ T_{total}(1)=T_{init}+P \times T_{trait}(P)+T_{final} \]

Fraction sérielle échelonnable

Ce qu'on nomme la fraction sérielle échelonnable, tenant compte du nombre $P$ de processeurs, peut s'exprimer ainsi :	\[ \gamma_{ech}=\frac{T_{init}+T_{final}}{T_{total}(P)} \]
Par conséquent, nous avons :	\[ T_{total}(1)=\gamma_{ech}T_{total}(P)+P(1-\gamma_{ech})T_{total}(P) \]
Ceci permet d'exprimer l'accélération possible sur $P$ unités de traitement comme suit, ce qui est essentiellement équivalent. à l'accélération relative selon la loi d'Amdahl :	\[ S(P)=P + (P-1)\gamma_{ech} \]

Illustration de la loi de Gustafson

Si on considère un traitement dont $80\%$ ne peut être parallélisé, et si on compte paralléliser le $20\%$ résiduel sur deux processeurs, on obtient :

\[ S(P)=P-\alpha(P-1) \] \[ S(2)=2-0,8(2-1)=1,2 \]

Ceci est très près du résultat que nous donne la loi d'Amdahl. En fait, pour un traitement fait à $80\%$ d'une partie séquentielle (non-parallélisable), on a :

\[ S(1)=1-0,8(1-1)=1-0=1 \] \[ S(2)=2-0,8(2-1)=2-0,8=1,2 \] \[ S(3)=3-0,8(3-1)=3-1,6=1,4 \] \[ S(4)=4-0,8(4-1)=4-2,4=1,6 \]

Comme on peut le voir à droite, où la ligne verte représente $P$ et où la ligne bleue représente $S(P)$ , il est clair qu'en doublant le nombre de processeurs mis à contribution pour effectuer un traitement, on ne double pas la vitesse à laquelle ce traitement sera effectué.