Amdahlsches Gesetz

Ein Programm kann nie vollständig parallel ausgeführt werden, da einige Teile wie Prozess-Initialisierung oder Speicherverwaltung 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 ${\displaystyle t_{P}}$ der Anteil der Laufzeit der parallelen Teilstücke eines Programms, dann ist ${\displaystyle t_{S}}$ der sequentielle Anteil, und die Gesamtlaufzeit ${\displaystyle T}$ ergibt sich bei Ausführung auf einem Kern aus der Summe:

Hinweise zu Formelzeichen

Formelzeichen		bezeichnete Größe
nach Amdahl	DIN 1304 / ISO 80000
1	T	Gesamtlaufzeit
–	${\displaystyle t_{S}}$	Laufzeit eines seriellen Programmabschnitts
P	${\displaystyle t_{P}}$	Laufzeit eines parallelen Programmabschnitts
N	${\displaystyle n_{P}}$	Anzahl der Prozessoren, welche von parallelen Programmabschnitten genutzt werden (können)
O(n)	${\displaystyle t_{O(n_{P})}}$	Laufzeit für Synchronisierungsaufwand
S	${\displaystyle \eta _{S}}$	Speedup-Faktor

${\displaystyle \!\,T=t_{S}+t_{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 ${\displaystyle t_{P}}$ der parallele Anteil eines Programms und ${\displaystyle n_{P}}$ die Anzahl der Prozessoren, welche zur Berechnung eingesetzt werden können. Dann ist ${\displaystyle t_{S}}$ der sequentielle Anteil und ${\displaystyle (t_{P}/n_{P})}$ der beschleunigte parallele Anteil. Die Gesamtzeit und damit die Gesamtbeschleunigung setzt sich aus der Summe der einzelnen Glieder zusammen, und daher gilt für den Speedup ${\displaystyle \eta _{S}}$:

${\displaystyle \eta _{S}={\frac {T}{t_{S}+{\frac {t_{P}}{n_{P}}}}}\leq {\frac {T}{t_{S}}}={\frac {T}{T-t_{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 anfallen. Damit erweitert sich die Ungleichung um einen Synchronisierungs-Zeitaufwand ${\displaystyle t_{O(n_{P})}}$, der dies berücksichtigt und daher mit steigendem ${\displaystyle n}$ zunimmt.

${\displaystyle \eta _{S}={\frac {T}{t_{S}+t_{O(n_{P})}+{\frac {t_{P}}{n_{P}}}}}\leq {\frac {T}{t_{S}}}={\frac {T}{T-t_{P}}}}$

Durch die Einführung des neuen Parameters konvergiert die Kurve nicht mehr gegen ${\displaystyle T/t_{S}}$, 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.

Amdahls Gesetz berücksichtigt einige Faktoren nicht, die sich positiv auf den Speedup auswirken. 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.

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.

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