Gustafsons Gesetz: Warum Parallelrechner viel schneller skalieren als Amdahl verspricht

Gustafsons Gesetz ist ein Modell der parallelen Leistungssteigerung, das John L. Gustafson 1988 als Gegenposition zum Amdahlschen Gesetz formulierte („Reevaluating Amdahl's Law“, Communications of the ACM). Amdahl nimmt eine feste Problemgröße an und sagt: Der sequenzielle Anteil begrenzt den maximalen Speedup. Gustafson beobachtete in der Praxis das Gegenteil: Wer mehr Rechenleistung hat, vergrößert meist auch das Problem — mehr Daten, feinere Simulationen, größere Modelle. Genau dann skaliert die Beschleunigung fast linear mit der Kernzahl.

Die Formel

Bezeichnet s den seriellen Anteil und p den parallelen Anteil eines Programms (mit s + p = 1), dann gilt für N Prozessoren statt Amdahls Bruch:

Speedup(N) = s + p · N

Der Grund: Der parallele Teil läuft auf allen N Kernen, der serielle nur auf einem. Bei wachsender Problemgröße bleibt der serielle Anteil s konstant klein, während p·N mit jeder weiteren CPU wächst. Beispiel: Ein Programm ist zu 99 % parallel (s = 0,01). Mit 1000 Kernen ergibt Gustafsons Gesetz einen Speedup von 0,01 + 0,99 · 1000 ≈ 990 — Amdahl hätte mit 1 / (0,01 + 0,99/1000) nur etwa das 91-Fache erlaubt.

Kein Widerspruch, sondern eine andere Frage

Beide Gesetze sind richtig — sie beantworten unterschiedliche Fragen. Amdahl: „Wie schnell wird ein festes Problem mit mehr Kernen?“ (fixed-size speedup). Gustafson: „Wie viel schneller kann ich ein skaliertes Problem rechnen, das mit der Kernzahl wächst?“ (scaled speedup). Für Supercomputer, numerische Simulationen, Wettervorhersagen oder KI-Training (größere Modelle, mehr Trainingsdaten) gilt praktisch immer die Gustafson-Sicht: Deshalb lohnen sich Cluster, Grafikprozessoren und Multikern-Prozessoren trotz unvermeidbarer sequenzieller Reste.

Grenzen

  • Die Skalierung setzt voraus, dass das Problem tatsächlich wächst und sein paralleler Anteil hoch bleibt.
  • Kommunikation und Synchronisation zwischen den Kernen erzeugen reale Overhead-Kosten, die mit der Kernzahl steigen.
  • Eine nebenläufige Struktur allein genügt nicht — die Arbeit muss sich auch sinnvoll aufteilen lassen.

Verwandte Grundlagen: Amdahlsches Gesetz, Multikern-Prozessor, Cluster.