Amdahlsches Gesetz

Der Geschwindigkeitsgewinn bei der Verwendung von parallel arbeitenden Prozessoren bei der Bearbeitung eines parallelen Problems

Das Amdahlsche Gesetz (benannt 1967 nach Gene Amdahl) ist ein Modell in der Informatik über die Beschleunigung von Programmen durch parallele Ausführung. Nach Amdahl wird der Geschwindigkeitszuwachs vor allem durch den sequentiellen Anteil des Problems beschränkt, da sich dessen Ausführungszeit durch Parallelisierung nicht verringern lässt.

Beschreibung

Ein Programm kann nie vollständig parallel ausgeführt werden, da einige Teile wie Prozess-Initialisierung oder Speicher-Allokation 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$

Angenommen, ein Programm benötigt 20 Stunden auf einem Rechner mit einer CPU, und eine Stunde davon wird sequentiell ausgeführt (beispielsweise Initialisierungs-Routinen oder Speicher-Allokation). Die verbleibenden 19 Stunden machen 95 % des Gesamtaufwandes aus und können auf beliebig viele Prozessoren verteilt werden. Die Gesamtrechenzeit kann aber selbst mit unendlich vielen Prozessoren nicht unter 1 Stunde fallen, die maximale Beschleunigung (SpeedUp) ist also Faktor 20.

Seien P der parallele Anteil eines Programms und N die Anzahl der Prozessoren, die zur Berechnung eingesetzt werden. Dann ist (1 − P) der sequentielle Anteil und (P / N) der beschleunigte parallele Anteil. Die Gesamtzeit und damit die Gesamtbeschleunigung setzt sich aus der Summe der einzelnen Glieder zusammen, und daher gilt:

$S = \frac{1}{(1 - P) + \frac{P}{N}}\leq\frac{1}{1-P}$

Es ist zu beobachten, dass die Beschleunigung bei steigender Prozessoranzahl immer stärker vom sequentiellen Anteil des Algorithmus und der Prozessorkommunikation abhängt. Amdahl argumentierte, dass durch Parallelisierung zusätzliche Kosten wie etwa für die Kommunikation und zur Synchronisierung zwischen den Prozessoren anfalle. Damit erweitert sich die Ungleichung um einen Faktor o(N), der dies berücksichtigt und daher mit steigendem N zunimmt.

$S = \frac{1}{(1 - P) + o(N) + \frac{P}{N}}\leq\frac{1}{1-P}$

Durch die Einführung des neuen Parameters konvergiert die Kurve nicht mehr gegen 1 / (1 − P), sondern erreicht ein Maximum, um dahinter wieder abzufallen. Dieser Effekt wird auch in der Praxis beobachtet: Bei genügend großer Anzahl Prozessoren übersteigt der Aufwand, das Problem zu übertragen, zu synchronisieren und zurückzusenden, den Rechenaufwand, der durch die zusätzlichen Kerne abgenommen wird.

Kritik

Amdahls Gesetz ist eines der pessimistischsten zur Abschätzung des theoretischen SpeedUps, da es einige positive Faktoren nicht berücksichtigt. Nach Amdahl ist die größtmögliche Beschleunigung linear, also durch die 10-fache Anzahl von Kernen ist maximal die 10-fache Rechenleistung möglich. Jedoch ist in jeder CPU auch Cache integriert, so dass sich auch die Menge an schnellem Speicher verzehnfacht. Im günstigsten Fall ist es so möglich, die gesamte Problemgröße im Cache anstatt im langsamen Hauptspeicher zu halten, was einen super-linearen SpeedUp ermöglicht, also Beschleunigung, die über die zusätzliche, reine Rechenleistung hinausgeht. Allerdings könnte dies darauf zurückzuführen sein, dass der Vergleich aus dem Grund fehlerhaft ist, dass der integrierte Cache als Teil des Prozessormoduls betrachtet wird. Ein Vergleich ohne Berücksichtigung der Cache-Größe würde nicht zu dem benannten super-linearen SpeedUp führen. Amdahls Betrachtung für den maximalen Speedup bleibt jedoch in beiden Fällen gültig.

Weiterhin geht Amdahl in seiner Rechnung davon aus, dass die Problemgröße unverändert bleibt; das Ziel ist also, ein Problem in möglichst kurzer Zeit zu berechnen. Für den Fall, in der gleichen Zeit ein größeres Problem zu berechnen, ergeben sich günstigere Voraussetzungen, da der parallele Anteil je nach Problem dann sehr groß werden kann. Je länger eine Berechnung dauert, desto weniger fällt die Zeit für die Initialisierung und abschließende Synchronisierung ins Gewicht.

Sonstiges

Das Amdahlsche Gesetz besitzt ebenfalls Bedeutung in der Betriebswirtschaftslehre, insbesondere beim Operations Research hinsichtlich Ressourcenallokationen.

Gustafsons Gesetz ist eng verwandt, berücksichtigt aber einige fehlende Aspekte des Gesetzes von Amdahl, das Mooresche Gesetz analysiert den SpeedUp von Computerchips im Allgemeinen.

Literatur

• Gene Amdahl: Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. In: AFIPS Conference Proceedings. 30, 1967, S. 483–485 (PDF).
• Thomas Rauber, Gudula Rünger: Parallele und Verteilte Programmierung. Springer, 2000, ISBN 3-540-66009-7.
• Günther Bengel, Christian Baun, Marcel Kunze u. a.: Masterkurs Parallele und Verteilte Systeme. Vieweg+Teubner, 2008, ISBN 3-8348-0394-4.