Deutsch
Menü

Amdahlsches vs. Gustafsonsches Gesetz: Annahmen und Skalierung

Beide Gesetze schätzen ab, wie viel schneller ein Programm mit mehr Prozessoren wird, beruhen aber auf unterschiedlichen Annahmen. Das Amdahlsche Gesetz hält die Problemgröße fest und betrachtet, wie dieselbe Arbeit schneller erledigt wird; daher bestimmt der nicht parallelisierbare Anteil die Obergrenze der Beschleunigung. Das Gustafsonsche Gesetz hält die Laufzeit fest und betrachtet, dass mit mehr Prozessoren entsprechend größere Probleme gelöst werden; daher wächst die Beschleunigung nahezu proportional zur Prozessorzahl. Die beiden widersprechen sich nicht, sondern beantworten unterschiedliche Fragen.

MerkmalAmdahlsches GesetzGustafsonsches Gesetz
Was festgehalten wirdProblemgröße (gesamte Arbeitsmenge)Laufzeit (Arbeitsmenge pro Prozessor)
FragestellungWie viel schneller lässt sich dasselbe Problem lösen?Wie viel größere Probleme lassen sich in derselben Zeit lösen?
Formel (N = Prozessorzahl)S = 1 / ((1 − p) + p / N)S = s + (1 − s) × N = N − s × (N − 1)
Messung der Anteilep ist der Zeitanteil des parallelisierbaren Teils bei Ausführung auf 1 Prozessors ist der Zeitanteil des sequenziellen Teils bei paralleler Ausführung auf N Prozessoren
Bei wachsendem NSättigt bei 1 / (1 − p)Wächst nahezu proportional zu N weiter
RechenbeispielBei p = 0,95 etwa 17-fach für N = 100; selbst für N gegen unendlich höchstens 20-fachBei s = 0,05 etwa 95-fach für N = 100
Zugehörige SkalierungStarke SkalierungSchwache Skalierung
SichtweisePessimistisch. Schon ein kleiner sequenzieller Anteil bestimmt die ObergrenzeOptimistisch. Mit größeren Problemen zahlt sich Parallelisierung aus
Passende BeispieleWenn eine Eingabe fester Größe sofort verarbeitet werden soll. Etwa die Bearbeitung eines einzelnen Bildes oder interaktive AntwortenSimulationen mit feinerem Gitter oder wenn größere Daten oder Modelle in derselben Zeit verarbeitet werden sollen
In beiden nicht berücksichtigtKommunikations- und Synchronisationsaufwand, ungleiche Lastverteilung, unzureichende SpeicherbandbreiteKommunikations- und Synchronisationsaufwand, ungleiche Lastverteilung, unzureichende Speicherbandbreite

Die Zahlenwerte sind typische Größenordnungen und variieren je nach Prozessgeneration und Produkt.

Wann welche Variante?

Amdahlsches Gesetz
Wenn die Problemgröße feststeht und die Antwortzeit verkürzt werden soll. Es dient dazu, die Obergrenze der Parallelisierung abzuschätzen und zu beurteilen, ob der sequenzielle Anteil verringert werden sollte.
Gustafsonsches Gesetz
Wenn sich das Problem mit der Prozessorzahl vergrößern lässt. Es dient dazu, bei großen Simulationen und Datenverarbeitung den Nutzen feinerer und größerer Berechnungen abzuschätzen.
Darstellung von Ergebnissen
Bei Angaben zur parallelen Leistung wird angegeben, ob starke oder schwache Skalierung gemessen wurde. Unter anderen Bedingungen ändert sich die Beschleunigung desselben Programms erheblich.

Häufige Fragen

Widersprechen sich die beiden Gesetze nicht?

Nein. Das Amdahlsche Gesetz hält die Problemgröße fest, das Gustafsonsche Gesetz die Laufzeit; sie beantworten also unterschiedliche Fragen. Außerdem wird der sequenzielle Anteil beim Amdahlschen Gesetz anhand der Laufzeit auf 1 Prozessor, beim Gustafsonschen Gesetz anhand der Laufzeit auf N Prozessoren gemessen, sodass man nicht denselben Zahlenwert einsetzen und vergleichen kann.

Warum ergibt sich bei 90 % parallelisierbarem Anteil höchstens eine 10-fache Beschleunigung?

Weil die restlichen 10 % nicht kürzer werden, egal wie viele Prozessoren man hinzufügt. Selbst wenn die Zeit des parallelen Teils gegen null geht, wird die Gesamtzeit nicht kürzer als 10 % der ursprünglichen, sodass die Beschleunigung bei 1 / 0,1 = 10-fach sättigt.

Warum ist die tatsächliche Beschleunigung kleiner als von diesen Gesetzen vorhergesagt?

Weil keines der beiden Gesetze Kommunikation und Synchronisation zwischen Prozessoren, ungleiche Lastverteilung oder unzureichende gemeinsame Speicherbandbreite berücksichtigt. Je mehr Prozessoren, desto größer werden diese Einflüsse und desto geringer die parallele Effizienz.

Welches Gesetz gilt für mein Programm?

Wenn die Eingabegröße feststeht und das Ergebnis schneller vorliegen soll, das Amdahlsche Gesetz. Wenn mit mehr Prozessoren feinere Gitter oder größere Daten bearbeitet werden sollen, das Gustafsonsche Gesetz. Auch für dasselbe Programm hängt das zutreffende Gesetz von der Nutzung ab.

Verständnis prüfen

Wie groß ist die theoretisch maximale Beschleunigung, wenn ein Programm, dessen Verarbeitung zu 90 % parallelisierbar ist, mit unbegrenzt vielen Prozessoren ausgeführt wird?

  1. A10-fach
  2. B90-fach
  3. CUnendlich
Antwort und Erläuterung anzeigen

Antwort: A. 10-fach

Nach dem Amdahlschen Gesetz beträgt die Beschleunigung 1/((1 − p) + p/N), mit p als parallelisierbarem Anteil und N als Prozessorzahl. Bei p = 0,9 ist selbst für N gegen unendlich 1/0,1 = 10-fach die Obergrenze, und bei N = 10 sind es nur etwa 5,3-fach. Schon ein kleiner nicht parallelisierbarer Anteil bestimmt die Grenze, daher ist es wichtig, den sequenziellen Teil zu verringern. Die Überlegung, die Problemgröße zu erhöhen und den parallelen Anteil zu vergrößern, ist das Gustafsonsche Gesetz.

Ein Teil, der 50 % der Gesamtverarbeitung ausmacht, wurde 4-mal schneller gemacht. Wie groß ist der Gesamt-Speedup (Amdahlsches Gesetz)?

  1. A2-fach
  2. B1,6-fach
  3. C4-fach
Antwort und Erläuterung anzeigen

Antwort: B. 1,6-fach

Die Zeit nach der Verbesserung ist die Summe aus den übrigen, nicht beschleunigten 50 % (0,5) und den 4-fach beschleunigten 50 % (0,5 ÷ 4 = 0,125), also 0,625. Der Speedup beträgt 1 ÷ 0,625 = 1,6. Egal wie stark der beschleunigte Teil verbessert wird, bleiben die übrigen 50 % bestehen, sodass das Ganze höchstens 2-fach schneller werden kann. Um das Ganze stark zu beschleunigen, müssen Teile gefunden und verbessert werden, die viel Zeit beanspruchen.

Welche Lehre aus dem Amdahlschen Gesetz für das Vorgehen bei Leistungsverbesserungen ist am zutreffendsten?

  1. AVorrang hat die Beschleunigung der Teile, die viel Zeit beanspruchen (der häufige Fall)
  2. BZuerst werden Teile beschleunigt, die nur selten ausgeführt werden
  3. CEgal welcher Teil beschleunigt wird, der Effekt auf das Ganze ist gleich
Antwort und Erläuterung anzeigen

Antwort: A. Vorrang hat die Beschleunigung der Teile, die viel Zeit beanspruchen (der häufige Fall)

Wird ein Teil, der nur 1 % des Ganzen beansprucht, unendlich beschleunigt, wird das Ganze nur um etwa 1 % schneller. Wird dagegen ein Teil mit 80 % Anteil 2-fach beschleunigt, wird das Ganze etwa 1,7-fach schneller. Grundsätzlich werden daher zuerst mit einem Profiler die zeitintensiven Teile gefunden und von dort aus verbessert. „Make the common case fast“ ist ein auch im Computerentwurf immer wieder genutzter Grundsatz.

  1. Welcher Gedanke ist mit dem Gustafsonschen Gesetz verbunden?
  2. Worin besteht bei der Bewertung paralleler Berechnungen der Unterschied zwischen „starker Skalierung“ und „schwacher Skalierung“?
  3. Wie wird der „Speedup“ (Geschwindigkeitszuwachs) zur Angabe einer Leistungsverbesserung berechnet?

Übungsfragen zu Leistungsbewertung und Profiling

Wichtige Begriffe erklärt

Amdahlsches Gesetz
Gesetz, nach dem bei teilweiser Parallelisierung eines Programms die Gesamtbeschleunigung durch den nicht parallelisierbaren Anteil begrenzt wird. Selbst bei 90 % parallelisiertem Anteil ist maximal eine 10-fache Beschleunigung möglich.
Gustafsons Gesetz
Gedanke, dass bei mehr Prozessoren und entsprechend größerem Problem der parallelisierbare Anteil wächst und der Gewinn nahezu proportional zur Prozessorzahl ausfällt.
Strong Scaling
Bewertung der Parallelleistung, bei der die Problemgröße fest bleibt, die Prozessorzahl erhöht wird und betrachtet wird, wie stark sich die Zeit verkürzt.
Schwache Skalierung (Weak Scaling)
Bewertung der Parallelleistung, bei der die Problemgröße pro Prozessor konstant bleibt, das Gesamtproblem wächst und geprüft wird, ob die Zeit konstant bleibt.
Parallele Effizienz
Wert, der durch Teilen des Speedups durch Parallelisierung durch die Prozessorzahl entsteht. Zeigt, wie wirksam die Kerne genutzt werden.

Verwandte Vergleiche