Imaginez ceci : vous êtes pressé de préparer un délicieux festin, mais vous êtes limité par la taille de votre cuisine et le nombre de personnes sur le pont. Dans le monde de l'informatique parallèle, les lois d'Amdahl et de Gustafson sont les recettes fiables dont vous avez besoin pour optimiser votre chef-d'œuvre culinaire. Ils sont comme les ingrédients secrets qui assaisonnent les performances des ordinateurs depuis des décennies, nous permettant de nous régaler de vitesses de traitement toujours plus rapides. Ces deux principes sont peut-être le yin et le yang de l’informatique parallèle, et ils guident les experts en technologie dans leur quête pour conquérir le domaine des processeurs multicœurs et du calcul haute performance. Mais quelles sont les lois d’Amdahl et de Gustafson, et comment opèrent-elles leur magie séparément ou en tandem ? Conscients de l' importance de la programmation parallèle , nous allons aujourd'hui plonger dans les subtilités de ces lois et découvrir comment elles peuvent être utilisées comme des outils puissants entre les mains de programmeurs avertis.

Table des matières

• Loi d'Amdahl : contexte

  – Accélération maximale

  – Mises en garde

• Loi de Gustavson : contexte

  – Accélération à l’échelle

  – Mises en garde

• Mise à l'échelle forte ou mise à l'échelle faible

  – Tests de mise à l’échelle

  — Forte mise à l'échelle

  - Faible mise à l'échelle

• Conclusions

Loi d'Amdahl : contexte

En 1967, lors de la Spring Joint Computer Conference, le Dr Gene Amdahl, exerçant de sérieuses compétences informatiques chez IBM, s'est réuni avec trois autres personnes férus de technologie, dont le génial Daniel Slotnick, le génie derrière le fonctionnement interne d'Illiac-IV. Que faisaient-ils, demandez-vous ? Eh bien, ils préparaient l’avenir de l’architecture informatique. Au cours de cette conférence, le Dr Gene Amdahl a exposé ses réflexions sur les obstacles rencontrés par « l'approche multiprocesseur » lorsqu'il s'agit de traiter des problèmes du monde réel et toutes leurs bizarreries. Et devinez quoi, il a salué « l’approche monoprocesseur » pour des problèmes de cette nature !

Lorsqu'il travaillait chez IBM, Amdahl a vivement remarqué qu'une part substantielle du travail informatique était consacrée à ce qu'il a appelé à juste titre « l'entretien ménager de la gestion des données ». Il a fermement soutenu que cette fraction particulière était restée remarquablement constante pendant environ une décennie, engloutissant systématiquement 40 % des instructions exécutées dans les cycles de production.

Qu’est-ce qui relève de ce travail de « ménage » ? Il englobe un large éventail de tâches informatiques qui, bien qu'essentielles, ne contribuent pas directement à la mission informatique principale. En fonction de l'algorithme et de l'application spécifiques, cela peut impliquer des E/S de données, un prétraitement, une gestion de la mémoire, une gestion des fichiers, etc. Cette cohérence suggère que, pour de nombreuses applications, une partie substantielle du temps de traitement est consacrée à ces tâches. Un certain niveau de gestion interne des données est presque inévitable et difficile à minimiser de manière significative. Amdahl note que cette surcharge semble séquentielle, ce qui signifie qu'elle se produit étape par étape et qu'elle n'est pas adaptée aux techniques de traitement parallèle.

"Une conclusion assez évidente qui peut être tirée à ce stade est que les efforts déployés pour atteindre des taux de traitement parallèles élevés sont vains à moins qu'ils ne soient accompagnés par des résultats en termes de taux de traitement séquentiels d'une ampleur très proche." - Dr Gene Amdahl [1]

Dans son article original [1], Amdahl ajoute que le domaine des tâches de « maintenance » n'est que la pointe de l'iceberg concernant les défis auxquels est confrontée l'approche « multiprocesseur ». Fort de son expérience impressionnante en tant que physicien théoricien de formation titulaire d'un doctorat, Amdahl possédait une compréhension approfondie des défis physiques du monde réel pour lesquels les ordinateurs étaient conçus. Il souligne de nombreuses complications, telles que des frontières irrégulières, des intérieurs non uniformes et des dépendances spatiales et temporelles à des états variables, qui présentent tous de formidables obstacles pour le paradigme « multiprocesseur ».

Par exemple, envisagez de calculer la répartition de la chaleur sur une grille cartésienne 2D. En tout point donné, la température (T) dépend des températures des points voisins. Lors de l'utilisation d'un modèle informatique parallèle, il est essentiel de communiquer ces valeurs avec des points adjacents, qui pourraient être stockés sur des processeurs distincts. Ces problèmes continuent d’être omniprésents dans les scénarios contemporains.

Heureusement, l’ingéniosité collective des experts en informatique a donné naissance à de nombreuses méthodes numériques et techniques de programmation adaptées pour relever de front ces défis complexes.

Loi d'Amdahl : accélération maximale

Dans son travail original, la formulation d'Amdahl ne s'intéressait pas aux équations mathématiques ; ce n'est que lors d'analyses ultérieures que l'accélération maximale a été quantifiée.

La loi d'Amdahl repose sur l'hypothèse qu'une fraction f du temps d'exécution d'un programme série est idéalement parallélisable sans aucune surcharge de communication ou de synchronisation. La partie complémentaire, représentée par s = 1 − f, est entièrement séquentielle.

Ainsi, si T est le temps d'exécution du programme séquentiel, le temps d'exécution sur p cœurs, T(p), est donné par :

Speedup , étant le rapport entre le temps d'exécution séquentielle et le temps d'exécution parallèle, donne :

Ainsi, la limite supérieure de l’accélération peut être définie comme :

Mises en garde

Malgré sa simplicité, la loi d’Amdahl n’est pas sans limites. Le modèle néglige les goulots d'étranglement matériels critiques tels que la bande passante mémoire, la latence et les contraintes d'E/S. Il ne prend pas non plus en compte les inconvénients de performances liés à la création de threads, à la synchronisation, à la surcharge de communication et à d'autres facteurs du monde réel. Malheureusement, ces facteurs non pris en compte ont généralement un impact négatif sur les performances réelles.

La figure suivante illustre l'impact de la parallélisation sur l'accélération, tel que déterminé par la loi d'Amdahl. Il est clair que, même avec une fraction parallèle substantielle de 95 % et une vaste gamme de processeurs, l'accélération maximale réalisable plafonne à environ 20 fois. Pousser le pourcentage de parallélisation à 99 % et utiliser une infinité de processeurs peut donner lieu à une accélération 100 fois plus impressionnante, ce qui est prometteur.

Cependant, il est crucial de reconnaître que disposer d’un tel nombre de processeurs est une rareté . Nous travaillons souvent avec un nombre beaucoup plus modeste, comme 64 ou même moins.

Lorsque nous appliquons la loi d'Amdahl à un programme utilisant 64 processeurs (avec f étant 95 %), l'accélération maximale oscille autour de 15,42x. Certes, ce chiffre n'est pas très prometteur !

Cette idée est quelque peu obscurcie par la limite employée dans cette expression :

Cette limite tend à masquer le fait que les chiffres d’accélération sont nettement inférieurs si l’on considère le nombre pratique et réel de processeurs.

Néanmoins, l'inconvénient le plus important de la loi d'Amdahl réside dans son hypothèse selon laquelle la taille du problème reste constante lorsque l'on utilise davantage de cœurs pour exécuter une application.

Essentiellement, cela suppose que la fraction parallélisable reste inchangée, quel que soit le nombre de cœurs utilisés. Cette limitation a été soigneusement abordée et développée par John L. Gustafson , qui a proposé une perspective modifiée maintenant connue sous le nom de loi de Gustafson . Cependant, malgré ces problèmes et mises en garde reconnus, il est essentiel de reconnaître que la loi d'Amdahl a ses propres mérites, car elle offre des informations précieuses sur les complexités de la parallélisation. La loi d'Amdahl trouve des applications sous la forme de tests d'échelle forts , un sujet que nous explorerons plus tard.

Loi de Gustavson : contexte

En travaillant sur les systèmes informatiques massivement parallèles des Sandia National Laboratories, le Dr John L. Gustafson et son équipe ont obtenu des facteurs d'accélération impressionnants pour trois applications différentes sur un hypercube à 1 024 processeurs. La fraction du code de série correspondait à 0,4 à 0,8 %.

« …nous avons atteint des facteurs d'accélération sur un hypercube à 1024 processeurs que nous pensons sans précédent : 1021 pour l'analyse des contraintes de faisceau utilisant des gradients conjugués, 1020 pour la simulation d'ondes de surface déflectrices utilisant des différences finies explicites et 1016 pour l'écoulement de fluide instable utilisant des flux corrigés. transport." — Dr John L. Gustafson [2]

Nous avons clairement vu dans la dernière section que selon la loi d'Amdahl, la vitesse maximale réalisable pour un grand nombre de processeurs est de 1/s. Alors, comment atteindre cette accélération déconcertante de 1021x ?

Gustafson [2] a souligné que l'expression mathématique a une hypothèse subtile, impliquant que la variable f n'est pas liée à p . Cependant, ce scénario correspond rarement à la réalité à laquelle nous sommes confrontés. Dans les scénarios du monde réel, nous ne prenons généralement pas un problème de taille fixe et ne l'exécutons pas sur un nombre différent de processeurs, sauf peut-être dans l'environnement contrôlé de la recherche universitaire. Au contraire, dans les applications pratiques, la taille du problème a tendance à évoluer en fonction du nombre de processeurs.

Lorsque des processeurs plus puissants deviennent disponibles, les utilisateurs s'adaptent en augmentant la complexité du problème pour tirer pleinement parti des capacités améliorées. Ils peuvent affiner des aspects tels que la résolution de la grille, le nombre de pas de temps, la complexité de l'opérateur de différence et d'autres paramètres pour garantir que le programme peut être exécuté dans le délai souhaité.

Selon Gustafson, il est souvent plus réaliste de supposer qu'en pratique, le temps d'exécution reste relativement constant plutôt que la taille du problème.

Gustafson a remarqué que la fraction parallèle ou vectorielle d'un programme augmente proportionnellement à la taille du problème. Des éléments tels que le démarrage vectoriel, le chargement du programme, les goulots d'étranglement en série et les opérations d'E/S, qui contribuent collectivement à la composante s de l'exécution du programme, restent généralement relativement constants et ne présentent pas de croissance significative avec la taille du problème.

Gustafson a poussé l'argument plus loin en soulignant que dans les scénarios où l'on double les degrés de liberté dans une simulation physique, un doublement correspondant du nombre de processeurs est souvent essentiel. À titre préliminaire, le volume de travail pouvant être efficacement réparti en parallèle tend à croître linéairement avec le nombre de processeurs.

Dans leur examen approfondi des trois applications mentionnées, Gustafson et ses collègues ont découvert que le composant parallèle affichait des facteurs d'échelle d'environ 1 023,9969, 1 023,9965 et 1 023,9965.

Loi de Gustafson : accélération progressive

L'hypothèse de Gustafson consiste à considérer le temps d'exécution normalisé sur p cœurs, qui totalise (1 − f) + f , ce qui donne une valeur globale de 1. Par cette logique, si (1 − f) + f signifie le temps d'exécution sur p cœurs , alors le temps d'exécution sur un seul cœur peut être exprimé comme (1 − f) + p*f . Par conséquent, l’accélération, que Gustafson appelle « accélération échelonnée », peut être calculée comme suit :

Lorsque nous appliquons la loi de Gustafson à un programme utilisant 64 processeurs (avec f étant 95 %), l'accélération prévue est de 60,85x (contre 15,42x avec la loi d'Amdahl). Maintenant, nous parlons😉

Les chiffres suivants mettent en évidence les différences entre les deux lois.

Mises en garde

Les perspectives d'Amdahl et de Gustafson offrent des points de vue distincts sur la parallélisation, chacun avec ses propres hypothèses.

La loi d'Amdahl suppose que la quantité de travail pouvant être parallélisée est constante et indépendante du nombre de processeurs, ce qui la rend très pessimiste. Le point de vue de Gustafson, qui suppose que la quantité de travail pouvant être parallélisée augmente de manière linéaire avec le nombre de cœurs, est sans aucun doute pratique pour de nombreux scénarios. Cependant, il peut parfois être trop optimiste.

Les applications du monde réel rencontrent fréquemment des contraintes qui peuvent limiter cette évolutivité linéaire. Par exemple, à mesure que le nombre de cœurs augmente, des rendements décroissants peuvent survenir en raison de la complexité du traitement parallèle, des dépendances en matière de données et des frais de communication. De plus, les limitations matérielles limitent pratiquement le nombre de cœurs pouvant être efficacement intégrés dans une seule puce. La loi de Gustafson ne tient pas toujours compte de ces défis complexes du monde réel, ce qui rend nécessaire la prise en compte des réserves affectant son applicabilité.

L'efficacité de la loi de Gustafson peut également dépendre de la nature de son application elle-même. Alors que certaines applications se prêtent naturellement à une évolutivité linéaire avec un nombre croissant de cœurs, d'autres peuvent stagner beaucoup plus tôt en raison de contraintes inhérentes ou de la nature du problème. Les complexités de la programmation et le potentiel de rendements décroissants doivent être pris en compte lors de l’examen de la faisabilité d’une évolutivité linéaire dans des applications pratiques.

Essentiellement, tout en offrant une vision plus optimiste de la parallélisation, la loi de Gustafson doit être appliquée avec une compréhension approfondie de l'application, des contraintes matérielles et des subtilités de la programmation parallèle pour s'aligner sur les complexités réelles de l'informatique moderne.

Mise à l'échelle forte ou mise à l'échelle faible

À la base, l’évolutivité fait référence à la capacité d’un système ou d’une application à gérer efficacement des charges de travail accrues à mesure que sa taille augmente.

En informatique, qu'elle soit matérielle ou logicielle, l'évolutivité désigne la capacité d'améliorer la puissance de calcul en augmentant les ressources disponibles.

Dans le contexte des clusters de calcul haute performance (HPC), parvenir à l’évolutivité est essentiel ; cela signifie la capacité d'étendre de manière transparente la capacité globale du système en intégrant des composants matériels supplémentaires. En ce qui concerne les logiciels, l'évolutivité est souvent synonyme d' efficacité de parallélisation , représentant le rapport entre l'accélération réelle réalisée et l'accélération idéale réalisable lors de l'utilisation d'un nombre spécifique de processeurs. Cette métrique offre un aperçu de l'efficacité avec laquelle les logiciels peuvent exploiter le traitement parallèle pour améliorer les performances.

Tests de mise à l'échelle

Dans le processus de développement typique d'applications volumineuses, il est souvent peu pratique de commencer les tests avec la taille complète du problème et le nombre maximal de processeurs dès le départ. Cette approche entraîne des temps d'attente prolongés et une utilisation excessive des ressources. Par conséquent, une stratégie plus pragmatique implique dans un premier temps de réduire ces facteurs, ce qui accélère la phase de test et permet une estimation plus précise des ressources nécessaires pour une éventuelle exécution à grande échelle, facilitant ainsi la planification des ressources.

Les tests d'évolutivité permettent d'évaluer dans quelle mesure une application peut s'adapter à différentes tailles de problèmes et à différents nombres de processeurs, garantissant ainsi des performances optimales.

Il est important de noter que les tests d’évolutivité n’examinent pas la fonctionnalité globale ou l’exactitude de l’application ; son objectif principal est la performance et l'efficacité à mesure que les ressources informatiques sont ajustées.

Deux tests de mise à l'échelle standard, fort et faible , sont largement utilisés en calcul parallèle.

Forte mise à l'échelle

Une mise à l’échelle forte implique d’augmenter le nombre de processeurs tout en maintenant la taille du problème constante. Cette approche réduit la charge de travail par processeur, ce qui est particulièrement utile pour les applications de longue durée et gourmandes en CPU. L’objectif principal d’une forte mise à l’échelle est d’identifier une configuration qui offre des temps d’exécution raisonnables tout en maintenant les coûts des ressources dans une fourchette gérable.

Une forte mise à l'échelle est ancrée dans la loi d'Amdahl, la taille du problème restant fixe tandis que le nombre d'éléments de traitement est augmenté. Cette méthodologie est souvent justifiée pour les programmes avec des charges de travail importantes liées au processeur.

L’objectif ultime d’une mise à l’échelle forte est de localiser le « point idéal » optimal qui permet d’effectuer les calculs dans un délai raisonnable, tout en minimisant le gaspillage de cycles de traitement dû aux frais généraux parallèles.

En cas de mise à l'échelle forte, un programme est considéré comme évoluant de manière linéaire si l'accélération, en termes d'unités de travail terminées par unité de temps, s'aligne sur le nombre d'éléments de traitement utilisés (N). De même, l’accélération peut être sous-linéaire, voire super-linéaire, selon la façon dont elle évolue avec le nombre de processeurs.

Enfin, j'ai essayé d'effectuer des tests de mise à l'échelle poussée sur l'un de mes codes. Fluidchen-EM est un solveur informatique de dynamique des fluides capable de résoudre de nombreux problèmes de dynamique des fluides. Les résultats suivants correspondent à la simulation de la cavité entraînée par le couvercle . La vitesse à l'horodatage final (après convergence) est visualisée et le temps d'exécution est calculé. Fluidchen-EM utilise MPI pour distribuer le domaine de calcul dans les processeurs iproc*jproc .

Remarque : Les résultats ont été exécutés sur mon ordinateur personnel et tous les cœurs correspondent à un seul processeur. Les résultats peuvent varier si la simulation est exécutée sur une machine plus grande et meilleure !

Le domaine de calcul est divisé en un total de points de grille imax*jmax .

iproc : nombre de processeurs dans la direction x

jproc : nombre de processeurs dans la direction y

Comme le montre la figure, le temps d'exécution diminue fortement à mesure que le nombre de processeurs double de 1 à 2. Cependant, l'accélération n'est pas aussi spectaculaire pour le prochain doublement de processeurs de 2 à 4, et elle commence même à saturer pour de nouvelles augmentations. en nombre de processeurs. Cependant, les résultats ont été compilés sur un processeur à huit cœurs, ces résultats peuvent donc changer si l'exécution est effectuée sur une machine plus grande et plus puissante.

Faible mise à l'échelle

En cas de faible mise à l'échelle, le nombre de processeurs et la taille du problème augmentent, maintenant une charge de travail constante par processeur. Une mise à l'échelle faible s'aligne sur la loi de Gustafson, où l'accélération échelonnée est calculée en fonction de la charge de travail d'une taille de problème mise à l'échelle, par opposition à la loi d'Amdahl, qui se concentre sur une taille de problème fixe.

La taille du problème allouée à chaque élément de traitement reste constante, ce qui permet à des éléments supplémentaires de résoudre collectivement un problème global plus vaste, qui peut dépasser la capacité de mémoire d'un seul nœud.

Une faible mise à l'échelle justifie les applications ayant des besoins importants en mémoire ou en ressources (ceux liés à la mémoire) qui nécessitent plus de mémoire qu'un seul nœud ne peut en fournir. De telles applications présentent souvent une mise à l'échelle efficace, car leurs stratégies d'accès à la mémoire donnent la priorité aux nœuds proches, ce qui les rend bien adaptées à un nombre de cœurs plus élevé.

Dans le cas d'une faible mise à l'échelle, l'évolutivité linéaire est obtenue lorsque le temps d'exécution reste constant à mesure que la charge de travail augmente en proportion directe avec le nombre de processeurs.

La plupart des programmes adoptant ce mode présentent une évolutivité favorable vers un nombre de cœurs plus élevé, en particulier ceux qui emploient des modèles de communication avec le plus proche voisin, car leur surcharge de communication reste relativement constante quel que soit le nombre de processus utilisés. Les exceptions à cette tendance incluent les algorithmes fortement dépendants des modèles de communication mondiaux.

Enfin, j'ai effectué les tests de mise à l'échelle faible en utilisant Fluidchen-EM . Les résultats suivants correspondent à la simulation de la convection de Rayleigh – Bénard . Encore une fois, la vitesse à l'horodatage final (après convergence) est visualisée et le temps d'exécution est calculé. Fluidchen-EM utilise MPI pour distribuer le domaine de calcul dans les processeurs iproc*jproc .

Remarque : les résultats ont été exécutés sur mon ordinateur personnel et tous les cœurs correspondent à un seul processeur. Les résultats peuvent varier si la simulation est exécutée sur une machine plus grande et meilleure !

Le domaine de calcul est divisé en un total de points de grille imax*jmax .

iproc : nombre de processeurs dans la direction x

jproc : nombre de processeurs dans la direction y

imax : nombre de points de grille sur toute la longueur du canal

jmax : Nombre de points de grille sur la hauteur du canal

xlength : longueur du canal

ylength : hauteur du canal

Comme l'illustre la figure ci-dessus, le temps d'exécution augmente avec la croissance de la taille du problème et du nombre de processeurs. Ce comportement peut être attribué à plusieurs facteurs. Tous les cœurs résidant sur un seul processeur, à mesure que la taille du problème augmente et que davantage de processeurs sont utilisés, une partie du temps de traitement est consommée pour configurer la communication MPI (Message Passing Interface). De plus, la taille plus importante du problème nécessite un échange de données accru entre les cœurs, amplifiant la latence de communication en raison de la bande passante limitée du réseau de communication.

Ainsi, ces résultats de tests fournissent des informations cruciales sur la parallélisation du problème.

Conclusion

Le choix entre la loi de Gustafson et la loi d'Amdahl dans la parallélisation des algorithmes dépend de l'adaptabilité de la charge de travail de calcul. La loi de Gustafson est pertinente lorsqu'un algorithme peut ajuster dynamiquement la quantité de calcul pour correspondre à la parallélisation disponible. En revanche, la loi d'Amdahl est plus adaptée lorsque la charge de calcul est fixe et ne peut pas être modifiée de manière significative par la parallélisation. Dans des scénarios réels, l'adaptation d'un algorithme pour la parallélisation implique souvent un certain degré de modification du calcul, et les deux lois servent de références précieuses, offrant des limites supérieures et inférieures sur l'accélération prévue. Le choix entre eux dépend de l’ampleur des changements informatiques introduits lors de la parallélisation, permettant une évaluation complète des gains potentiels en accélération.

Lecture suggérée

[1] Validité de l'approche à processeur unique pour atteindre des capacités informatiques à grande échelle, réimprimé des actes de la conférence AFIPS, Vol. 30 (Atlantic City, NJ, 18-20 avril), AFIPS Press, Reston, Virginie, 1967, pp. 483-485, lorsque le Dr Amdahl était chez International Business Machines Corporation, Sunnyvale, Californie | Journaux et magazines IEEE | IEEE Xplore

[2] Réévaluer la loi d'Amdahl | Communication de l'ACM

[3] Durganshu/Fluidchen-EM

[4] La loi d'Amdahl pour prédire l'avenir des multicœurs considérée comme nuisible (tu-berlin.de)

[5] Mise à l'échelle — Wiki HPC (hpc-wiki.info)

[6] Amdahl contre gustafson par r1parks — Infogram

Photo en vedette par Marc Sendra Martorell sur Unsplash