Gustafsons Gesetz

Gustafsons Gesetz ist ein Gesetz in der theoretischen Informatik, das von John Gustafson 1988 aufgestellt wurde. Es besagt, dass ein genügend großes Problem effizient parallelisiert werden kann. In der Erstpublikation nimmt Gustafson auch auf einen Ansatz seines Kollegen Edwin H. Barsis Bezug, weswegen das Gesetz auch als Gesetz von Gustafson-Barsis bezeichnet wird.

Beschreibung

Gustafsons Gesetz basiert auf dem Gesetz von Amdahl, das, ausgehend von einer festen Problemgröße, versucht eine zu bewältigende Aufgabe durch Parallelisierung mit $N$ Prozessoren in kürzerer Zeit zu lösen. Es geht dabei davon aus, dass das bestmögliche Ergebnis eine lineare Verbesserung der benötigten Zeit (also $1/N$) sei. Verwendet man doppelt so viele Prozessoren, benötige man bestenfalls die halbe Zeit.

Gustafson veränderte das Gesetz so, dass es ein festes Zeitfenster verwendet, in dem die Problemgröße mit der Anzahl der Prozessoren wächst. Verwendet man doppelt so viele Prozessoren, kann man bestenfalls eine doppelt so große Aufgabe lösen. Obwohl sie auf den ersten Blick gleich erscheinen, unterscheiden sich die Aussagen signifikant.

Ein Programm kann nie vollständig parallel ausgeführt werden, da einige Teile, wie Prozessinitialisierung oder Speicherallokation nur einmalig auf einem Prozessor ablaufen oder der Ablauf von bestimmten Ergebnissen abhängig ist. Daher zerlegt man den Programmlauf in Abschnitte, die entweder vollständig sequentiell oder vollständig parallel ablaufen, und fasst sie zu jeweils einer Gruppe zusammen. Sei $P$ der Anteil der Laufzeit der parallelen Teilstücke eines Programms, dann ist $(1-P)$ der sequentielle Anteil und die Gesamtlaufzeit ergibt sich bei Ausführung auf einem Kern aus der Summe:

$\!\,1=(1-P)+P$.

Gemäß dieser Formel werden beide Teile auf einem seriellen Rechner hintereinander ausgeführt, die Zeiten addieren sich auf. Vernachlässigt man den Overhead für Kommunikation, Synchronisierung und dergleichen, so lässt sich der parallele Anteil auf $N$ Prozessoren gleichzeitig ausführen. Für den Beschleunigungsfaktor (Speedup) $S(N)$ gilt damit

$S(N)=(1-P)+N\cdot P$.

Der entscheidende Unterschied zu Amdahl ist, dass der parallele Anteil mit der Anzahl der Prozessoren wächst. Der sequentielle Teil wirkt hier nicht beschränkend, da er mit zunehmendem $N$ unbedeutender wird. Geht $N$ gegen unendlich, so wächst der Speedup linear mit der Anzahl der Prozessoren $N$.

Anwendung

Gustafsons Gesetz lässt sich gut auf Probleme anwenden, die in Echtzeit verarbeitet werden. Die Echtzeit ist fix, und das Problem darf dann mittels mehr Prozessoren komplexer werden. Beispielsweise müssen beim 3D-Rendering mind. 30 Bilder pro Sekunde berechnet werden, das ist ein festes Zeitfenster. Allerdings kann das Bild realistischer werden, wenn man die Datenmenge vergrößert, z. B. mehr Polygone oder detailreichere Texturen. Das kann laut Gustafson mittels mehr Prozessoren erreicht werden.

Ähnliches gilt für die Logik-Berechnungen in Spielen, Physik-Simulation und künstliche Intelligenz, die mit Menschen interagiert. Gleiches gilt aber auch theoretisch in der Robotik, Maschinensteuerung und -überwachung und ähnlichen Aufgabenbereichen.

Gustafson selbst arbeitet aktuell bei AMD an Radeon-Grafikkarten.

Kritik

Es gibt eine Reihe von Problemstellungen, die sich nicht sinnvoll beliebig vergrößern lassen, oder Probleme, die in möglichst kurzer Zeit berechnet werden müssen.

Nicht-lineare Algorithmen können oft nicht in vollem Umfang von der von Gustafson beschriebenen Parallelisierung profitieren. Lawrence Snyder erklärt, dass ein Algorithmus mit einer Komplexität in $O(n^{3})$ durch Verdopplung der Nebenläufigkeit einen Speed-up von nur 9 % erzielt.