Amdahlsches Gesetz

Geschwindigkeitsgewinn eines parallelisierbaren Problems durch parallel arbeitende Prozessoren

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 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 $t_{P}$ der Anteil der Laufzeit der parallelen Teilstücke eines Programms, dann ist $t_{S}$ der sequentielle Anteil, und die Gesamtlaufzeit $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
–	$t_{S}$	Laufzeit eines seriellen Programmabschnitts
P	$t_{P}$	Laufzeit eines parallelen Programmabschnitts
N	$n_{P}$	Anzahl der Prozessoren, welche von parallelen Programmabschnitten genutzt werden (können)
O(n)	$t_{O(n_{P})}$	Laufzeit für Synchronisierungsaufwand
S	$\eta _{S}$	Speedup-Faktor

$\!\,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 $t_{P}$ der parallele Anteil eines Programms und $n_{P}$ die Anzahl der Prozessoren, welche zur Berechnung eingesetzt werden können. Dann ist $t_{S}$ der sequentielle Anteil und $(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 $\eta _{S}$:

$\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 $t_{O(n_{P})}$, der dies berücksichtigt und daher mit steigendem $n$ zunimmt.

$\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 $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.

Kritik

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.

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. Band 30, 1967, S. 483–485 (berkeley.edu [PDF]). 

Weblinks

Commons: Amdahlsches Gesetz – Sammlung von Bildern, Videos und Audiodateien