Gustafsons Gesetz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Gustafsons Gesetz (auch bekannt als Gesetz von Gustafson-Barsis) 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.

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 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 soviel 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 soviel 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 Part 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[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 fixes 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, Maschinen-Steuerung und -Überwachung und ähnlichen Aufgabenbereichen.

Gustafson selbst arbeitet aktuell[2] bei AMD an Radeon-Grafikkarten.

Kritik[Bearbeiten]

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 O(N3) durch Verdopplung der Nebenläufigkeit einen SpeedUp von nur 9 % erzielt.

Einzelnachweise[Bearbeiten]

  1.  John L. Gustafson: Reevaluating Amdahl's law. In: Commun. ACM. 31, Nr. 5, 1988, S. 532–533, doi:10.1145/42411.42415 (PDF, abgerufen am 10. November 2010).
  2. AMD wirbt Intel Guru ab
  3.  Lawrence Snyder: Type Architectures, Shared Memory, and the Corollary of Modest Potential. In: Annual Review of Computer Science. 1, 2003, S. 289–317, doi:10.1146/annurev.cs.01.060186.001445 (PDF, abgerufen am 20. September 2009).