Parallele Algorithmen und Performance

Das Design paralleler Algorithmen zielt auf Berechnungen ab, die eine reichhaltige Parallelität bei geringer Kommunikation aufweisen, und die Performance-Analyse quantifiziert, wie gut sie zusätzliche Prozessoren nutzen.

Definition

Ein paralleler Algorithmus spezifiziert, wie ein Problem durch die Zusammenarbeit mehrerer Prozessoren gelöst wird; seine Qualität wird anhand von Work (Gesamtoperationen) und Depth (längste Abhängigkeitskette) sowie anhand von Performance-Metriken wie Speedup und Effizienz beurteilt, die den Nutzen der Verwendung von p Prozessoren messen.

Scope

Dieses Thema behandelt Modelle für den Entwurf und die Analyse paralleler Algorithmen – insbesondere das PRAM-Modell und seine Work-Depth-Analyse –, den Entwurf paralleler Primitive wie Präfixsummen (Scan), Reduktion und Sortierung sowie das Performance-Framework von Speedup, Effizienz, Kostenoptimalität, Isoeffizienz und die Skalierungsgesetze von Amdahl und Gustafson. Es bietet die analytische Grundlage für die Argumentation über parallele Programme über alle Programmiermodelle hinweg.

Core questions

• Wie wird die inhärente Parallelität eines Problems durch seine Work und Depth charakterisiert?
• Wie werden Speedup, Effizienz und Skalierbarkeit definiert und gemessen?
• Wie bestimmt der serielle Anteil oder das Wachstum eines Problems seine parallele Skalierbarkeit?

Key theories

PRAM und Work-Depth-Analyse

Das PRAM-Modell idealisiert eine parallele Maschine mit gemeinsamem Speicher und synchronen Schritten, was die Analyse der Work (Gesamtoperationen) und Depth (Länge des kritischen Pfades) eines Algorithmus unterstützt, die zusammen seine erreichbare parallele Zeit begrenzen.

Speedup, Effizienz und Isoeffizienz

Speedup misst, wie viel schneller p Prozessoren ein Problem lösen, Effizienz normalisiert dies pro Prozessor, und Isoeffizienz drückt aus, wie die Problemgröße mit der Anzahl der Prozessoren wachsen muss, um die Effizienz konstant zu halten, was die Skalierbarkeit erfasst.

Amdahls und Gustafsons Gesetze

Amdahls Gesetz begrenzt den Speedup bei fester Problemgröße durch den seriellen Anteil, während Gustafsons Gesetz besagt, dass die Skalierung des Problems mit der Maschine einen nahezu linearen Speedup ermöglicht, was gemeinsam die starke versus schwache Skalierung umreißt.

Clinical relevance

Work-Depth-Analyse und Skalierungsgesetze leiten an, ob und wie eine Berechnung parallelisiert werden sollte, und prognostizieren ihr Verhalten in großem Maßstab, was das Design von Sortier- und Graph-Kernels bis hin zu großen Simulationen und Machine-Learning-Trainings beeinflusst.

History

Amdahls Argument von 1967 und Gustafsons Widerlegung von 1988 prägten die Speedup-Debatte; das PRAM-Modell und das Work-Depth-Framework reiften in den 1980er Jahren und wurden in JaJas Text von 1992 sowie in der Analyse der Skalierbarkeit von Grama und Kollegen kodifiziert, wodurch das parallele Rechnen seinen theoretischen Kern erhielt.

Debates

Starke Skalierung versus schwache Skalierung

Amdahls Sicht der starken Skalierung (festes Problem, mehr Prozessoren) prognostiziert abnehmende Erträge, während Gustafsons Sicht der schwachen Skalierung (Problem wächst mit den Prozessoren) einen anhaltenden Speedup vorhersagt; welche die richtige Messgröße ist, hängt davon ab, ob die Problemgröße oder die Lösungszeit fest ist.

Key figures

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

Seminal works

• jaja1992
• amdahl1967
• gustafson1988

Frequently asked questions

Was ist der Unterschied zwischen der Work und der Depth eines parallelen Algorithmus?

Work ist die Gesamtzahl der Operationen, die über alle Prozessoren hinweg ausgeführt werden, während Depth (oder Spanne) die Länge der längsten Kette abhängiger Operationen ist. Depth begrenzt die bestmögliche parallele Laufzeit, und das Work-to-Depth-Verhältnis gibt an, wie viel Parallelität verfügbar ist.