Gustafson's Law – Wenn das Problem mitwächst

Eine Vertiefung zur Serie Skalierbarkeit.

June 26, 2026 scalability gustafson amdahl parallelism hpc exkurs

Amdahl’s Law gehört zum Allgemeinwissen der Informatik: Parallelisierung hat eine harte Obergrenze. Sein optimistischeres Gegenstück ist Gustafson’s Law – dieselbe Rechnung, anders aufgestellt. Doch der Reihe nach.

Mehr Prozessoren, proportional mehr Tempo – so die naheliegende Hoffnung. Wer eine Berechnung von einem auf zehn Kerne verteilt, möchte das Ergebnis gern zehnmal schneller erhalten. In der Praxis bleibt die Beschleunigung – der Speedup – fast immer darunter, und ab einem gewissen Punkt bringt jeder weitere Kern kaum noch einen Vorteil. Der Grund dafür ist der serielle Teil der Arbeit, also der Teil, der sich eben nicht aufteilen lässt.

Genau das hält Amdahl’s Law fest – mit einer unbequemen Botschaft: Der serielle Anteil deckelt die maximale Beschleunigung. Bei einem seriellen Anteil von 10 % ist Faktor 10 das Maximum, egal wie viele Prozessoren hinzugefügt werden (ausführlich in Amdahl’s Law und die Grenzen des Wachstums). Das klingt deprimierend. 1988 hielt John Gustafson dagegen, die Rechnung sei zwar richtig, aber irreführend.

Die Grundkritik

Gustafson arbeitete am Sandia National Laboratory mit massiv parallelen Rechnern mit über 1.000 Prozessoren und stellte regelmäßig eine bessere Beschleunigung fest, als es Amdahls Gesetz eigentlich zuließ.

Amdahls Modell gilt für ein festes Problem: Ein Entwickler hat bestehenden Code, die Problemgröße steht fest und mehr Prozessoren sollen die Ausführungszeit senken. Genau dort greift die Deckelung durch den seriellen Anteil.

Gustafson hatte jedoch eine andere Problemstellung vor Augen. Wer eine Wettersimulation durchführt, möchte mit mehr Prozessoren nicht dasselbe Problem schneller lösen, sondern ein größeres Problem: ein feineres Gitter, mehr Datenpunkte, eine höhere Auflösung in derselben Rechenzeit. Die Problemgröße ist nicht fix, sondern wächst mit den Ressourcen. Unter dieser Annahme sieht die Skalierung völlig anders aus.

Die Formel

Gustafson fasste diese Beobachtung in einer Formel für den skalierten Speedup zusammen. Diese Formel beschreibt, wie viel Arbeit ein paralleles System gegenüber einem einzelnen Prozessor schafft.

\[S(n) = n - s \times (n - 1) \quad\text{bzw.}\quad S(n) = s + n \times (1 - s)\]

$n$ ist die Anzahl der Prozessoren.
$s$ ist der Zeitanteil, den der serielle Teil auf dem parallelen System einnimmt – nicht der Anteil am Gesamtproblem, sondern der Anteil an der tatsächlichen Ausführungszeit.
$S(n)$ ist der skalierte Speedup.

Das entscheidende Detail steckt in der Definition von $s$. Bei Amdahl ist $s$ der Anteil des Problems, der seriell bleiben muss – eine Eigenschaft des Algorithmus, die unabhängig von der Anzahl der Prozessoren ist. Bei Gustafson hingegen ist $s$ der Anteil an der gemessenen Laufzeit, den der serielle Code tatsächlich einnimmt. Wächst das Problem und der parallele Anteil proportional mit, so schrumpft $s$ mit steigendem $n$.

Eine Klimasimulation etwa braucht eine Stunde Initialisierung (seriell), danach folgt die eigentliche Berechnung (parallel). Auf 100 Prozessoren dauert die Berechnung ebenfalls eine Stunde. Der serielle Zeitanteil beträgt also $s = 0{,}5$, und der skalierte Speedup beträgt $S(100) = 100 - 0{,}5 \times 99 = 50{,}5$. Verzehnfacht man die Prozessorzahl auf 1.000, bleibt die Berechnung bei einer Stunde – jetzt aber auf einem Gitter mit zehnmal so vielen Punkten: $s$ bleibt 0,5, und $S(1000) = 1000 - 0{,}5 \times 999 = 500{,}5$. Der Speedup wächst also nahezu linear mit der Prozessorzahl.

Amdahl hätte für dasselbe $s = 0{,}5$ bei einem Faktor von $1/s = 2$ Schluss gemacht. Der Widerspruch löst sich durch die folgende Annahme auf: Amdahls Faktor 2 gilt, wenn die eine Stunde Initialisierung einen fixen Anteil am Gesamtproblem ist. Sobald der parallele Anteil mit der Prozessorzahl mitwächst, fällt dieselbe Stunde relativ immer weniger ins Gewicht – und der skalierte Speedup zieht davon.

Wo die Rechnung aufgeht

Die klarsten Beispiele hierfür kommen aus dem Bereich des High Performance Computing. Bei einer Wettersimulation werden mehr Prozessoren für ein feineres räumliches Gitter genutzt: Die Zahl der Gitterpunkte wächst linear mit der Prozessorzahl, während die Initialisierung – das Laden von Daten und das Setzen von Randbedingungen – nahezu konstant bleibt. Das ergibt einen nahezu linearen Geschwindigkeitsgewinn, genau wie Gustafson vorhersagt.

Beim Rendering wiederholt sich dieses Muster. Eine Render-Farm verteilt nicht einen Frame auf alle Knoten, sondern jeden Frame auf einen eigenen Knoten. Mehr Knoten bedeuten also: derselbe Film in höherer Auflösung oder mit mehr Details in derselben Zeit, nicht ein einzelner Frame in einem Bruchteil davon. In der Genomsequenzierung beschleunigen mehr Rechenknoten nicht die Sequenzierung eines einzelnen Genoms, sondern sie verarbeiten mehr Genome parallel. Jeder Knoten arbeitet dabei unabhängig an einem anderen Datensatz, ohne Abstimmung mit den übrigen. Solche Probleme, die ganz ohne Koordination zwischen den Einheiten auskommen, bezeichnet man als „embarrassingly parallel“.

In allen drei Fällen ist das Muster dasselbe: Der parallele Anteil wächst proportional zur Prozessorzahl, während der serielle Anteil – bestehend aus Initialisierung, Koordination und Zusammenführung der Ergebnisse – absolut konstant bleibt oder deutlich langsamer wächst.

Wo sie kippt

Die Formel steht und fällt mit einer leicht zu übersehenden Annahme: Der serielle Anteil muss absolut konstant bleiben, wenn die Zahl der Prozessoren steigt. In den HPC-Beispielen ist das plausibel – eine Stunde Initialisierung bleibt eine Stunde, egal ob 100 oder 10.000 Prozessoren rechnen.

Sobald die Koordination zwischen den Einheiten jedoch mit $n$ wächst, bröckelt diese Annahme. Wenn jeder neue Prozessor nicht nur seinen parallelen Anteil, sondern auch zusätzlichen Kommunikationsaufwand mitbringt, dann ist $s$ nicht mehr konstant, sondern steigt mit $n$. In diesem Fall kippt die optimistische Prognose.

Genau das passiert in verteilten Systemen ohne Shared-Nothing-Muster. Cache-Invalidierung, verteilte Locks, Konsensalgorithmen – all das verursacht Koordinationskosten, die mit der Knotenzahl wachsen. Hier hilft Gustafson nicht weiter. Gunthers Universal Scalability Law (siehe Amdahl’s Law und die Grenzen des Wachstums) modelliert diesen Fall, indem sein quadratisch wachsender Kohärenz-Term κ genau die Kosten erfasst, die Gustafson ausblendet.

Amdahl oder Gustafson – wann gilt was?

Die beiden Gesetze sind keine Konkurrenten, da sie verschiedene Fragen beantworten. Amdahls Gesetz gilt, wenn die Problemgröße feststeht, beispielsweise bei einem Suchdienst, der 1.000 Requests pro Sekunde bei einer Antwortzeit von 50 ms bedienen soll. Dann ist nur noch die Frage, wie viel Parallelität überhaupt hilft. Gustafson gilt hingegen, wenn die Problemgröße mit den Ressourcen wächst, beispielsweise bei einer Datenanalyse auf einem Cluster, bei der mehr Knoten mehr Daten bedeuten statt einer schnelleren Verarbeitung.

Für die meisten Web-Systeme ist Amdahl die richtige Wahl. Die Last kommt von außen und ist nicht frei wählbar. Niemand sagt: „Wir haben jetzt 10 Server, also verdoppeln wir die Seitenanzahl.“ Die Nutzer kommen – oder eben nicht – und die Frage ist immer, ob die Kapazität ausreicht. Genau um diese Skalierung unter extern vorgegebener Last geht es in meiner Serie über Skalierbarkeit von Web-Systemen, aus der dieser Exkurs stammt.

Gustafsons optimistische Prognose hängt am konstanten seriellen Anteil, und genau der bleibt unter Last nicht konstant. Mehr gleichzeitige Nutzer bedeuten mehr Koordination um geteilte Ressourcen – eine gemeinsame Datenbank, Locks auf denselben Datensätzen –, und dieser serielle Anteil wächst mit der Last, statt mit zusätzlichen Servern zu schrumpfen. Gustafson ist hier also kein Gegenbeweis zu Amdahl, sondern eine Erinnerung an dessen Grenzen und an Bedingungen, die in der Praxis selten von allein erfüllt sind.

Quellen

Gustafson (1988) – Reevaluating Amdahl’s Law. Communications of the ACM, 31(5), 532–533.
Amdahl (1967) – Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Spring Joint Computer Conference Proceedings, Vol. 30, 483–485.
Gunther (2007) – Guerrilla Capacity Planning. Springer.