Algorithmes parallèles et performance

La conception d'algorithmes parallèles vise des calculs qui révèlent un parallélisme abondant avec une faible communication, et l'analyse de performance quantifie leur capacité à exploiter efficacement des processeurs supplémentaires.

Definition

Un algorithme parallèle spécifie comment un problème est résolu par plusieurs processeurs coopérant ; sa qualité est évaluée par le travail (opérations totales) et la profondeur (chaîne de dépendances la plus longue), ainsi que par des métriques de performance telles que l'accélération (speedup) et l'efficacité qui mesurent le bénéfice de l'utilisation de p processeurs.

Scope

Ce sujet couvre les modèles de conception et d'analyse des algorithmes parallèles — notamment le PRAM et son analyse travail-profondeur — la conception de primitives parallèles telles que les sommes de préfixes (scan), la réduction et le tri, ainsi que le cadre de performance incluant l'accélération (speedup), l'efficacité, l'optimalité en coût, l'iso-efficacité et les lois de mise à l'échelle d'Amdahl et de Gustafson. Il fournit la base analytique pour raisonner sur les programmes parallèles à travers tous les modèles de programmation.

Core questions

• Comment le parallélisme inhérent à un problème est-il caractérisé par son travail et sa profondeur ?
• Comment l'accélération (speedup), l'efficacité et la scalabilité sont-elles définies et mesurées ?
• Comment la fraction séquentielle ou la croissance d'un problème détermine-t-elle sa scalabilité parallèle ?

Key theories

PRAM et analyse travail-profondeur

Le modèle PRAM idéalise une machine parallèle avec mémoire partagée et étapes synchrones, permettant l'analyse du travail (opérations totales) et de la profondeur (longueur du chemin critique) d'un algorithme, qui ensemble bornent son temps parallèle réalisable.

Accélération (speedup), efficacité et iso-efficacité

L'accélération (speedup) mesure la rapidité avec laquelle p processeurs résolvent un problème, l'efficacité la normalise par processeur, et l'iso-efficacité exprime comment la taille du problème doit croître avec le nombre de processeurs pour maintenir une efficacité constante, capturant ainsi la scalabilité.

Lois d'Amdahl et de Gustafson

La loi d'Amdahl borne l'accélération (speedup) à taille fixe par la fraction séquentielle, tandis que la loi de Gustafson observe que la mise à l'échelle du problème avec la machine permet une accélération quasi linéaire, encadrant conjointement la scalabilité forte versus faible.

Clinical relevance

L'analyse travail-profondeur et les lois de mise à l'échelle guident la décision de paralléliser un calcul et la manière de le faire, et prédisent son comportement à grande échelle, éclairant la conception de tout, des algorithmes de tri et des noyaux de graphes aux grandes simulations et à l'entraînement en apprentissage automatique.

History

L'argument d'Amdahl en 1967 et la réfutation de Gustafson en 1988 ont encadré le débat sur l'accélération (speedup) ; le modèle PRAM et le cadre travail-profondeur ont mûri au cours des années 1980 et ont été codifiés dans le texte de JaJa en 1992 et l'analyse de la scalabilité par Grama et ses collègues, conférant ainsi à l'informatique parallèle son cœur théorique.

Debates

Scalabilité forte versus scalabilité faible

La vision de la scalabilité forte d'Amdahl (problème fixe, plus de processeurs) prédit des rendements décroissants, tandis que la vision de la scalabilité faible de Gustafson (faire croître le problème avec les processeurs) prédit une accélération (speedup) soutenue ; la mesure appropriée dépend de la fixation de la taille du problème ou du temps de résolution.

Key figures

• Joseph JaJa
• Gene Amdahl
• John Gustafson
• Vipin Kumar

Seminal works

• jaja1992
• amdahl1967
• gustafson1988

Frequently asked questions

Quelle est la différence entre le travail et la profondeur d'un algorithme parallèle ?

Le travail est le nombre total d'opérations effectuées par tous les processeurs, tandis que la profondeur (ou étendue) est la longueur de la plus longue chaîne d'opérations dépendantes. La profondeur borne le meilleur temps d'exécution parallèle possible, et le rapport travail-profondeur indique la quantité de parallélisme disponible.