Gustafsons Gesetz

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

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.

Kritik

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

Nicht-lineare Algorithmen können oft nicht in vollem Umfang von der von Gustafson beschriebenen Parallelisierung profitieren. Lawrence Snyder^[2] erklärt, dass ein Algorithmus mit einer Komplexität in O(N³) durch Verdopplung der Nebenläufigkeit einen SpeedUp von nur 9 % erzielt.

Einzelnachweise

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. ↑ 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).