Gustafsons Gesetz

Gesetz in der theoretischen Informatik

Gustafsons Gesetz ist ein Gesetz in der theoretischen Informatik, das von John Gustafson 1988 aufgestellt wurde.[1] 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

Bearbeiten

Gustafsons Gesetz basiert auf dem Gesetz von Amdahl, das, ausgehend von einer festen Problemgröße, versucht eine zu bewältigende Aufgabe durch Parallelisierung mit   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  ) 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   der Anteil der Laufzeit der parallelen Teilstücke eines Programms, dann ist   der sequentielle Anteil und die Gesamtlaufzeit ergibt sich bei Ausführung auf einem Kern aus der Summe:

 .

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   Prozessoren gleichzeitig ausführen. Für den Beschleunigungsfaktor (Speedup)   gilt damit

 .

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   unbedeutender wird. Geht   gegen unendlich, so wächst der Speedup linear mit der Anzahl der Prozessoren  .

Anwendung

Bearbeiten

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[2] bei AMD an Radeon-Grafikkarten.

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[3] erklärt, dass ein Algorithmus mit einer Komplexität in   durch Verdopplung der Nebenläufigkeit einen Speed-up von nur 9 % erzielt.

Einzelnachweise

Bearbeiten
  1. John L. Gustafson: Reevaluating Amdahl's law. In: Communications of the ACM. Band 31, Nr. 5, 1988, S. 532–533, doi:10.1145/42411.42415 (archive.org [PDF]).
  2. Benjamin Benz: AMD wirbt Intel-Guru ab. In: heise online. 29. August 2012, abgerufen am 6. Juni 2022.
  3. Lawrence Snyder: Type Architectures, Shared Memory, and the Corollary of Modest Potential. In: Annual Review of Computer Science. Band 1, 1986, S. 289–317, doi:10.1146/annurev.cs.01.060186.001445 (washington.edu [PDF]).