Wikipedia · einfach zusammengefasst · Stand
Amdahlsches Gesetz
Das Amdahlsche Gesetz (benannt 1967 nach Gene Amdahl) ist ein Modell in der Informatik über die Beschleunigung von Programmen durch parallele Ausführung.
Inhalt3 Abschnitte
Grundidee und Begriffe
Das Amdahlsche Gesetz ist ein 1967 nach Gene Amdahl benanntes Modell der Informatik. Es beschreibt, wie stark Programme durch parallele Ausführung beschleunigt werden können. Seine zentrale Aussage lautet: Der Geschwindigkeitsgewinn wird vor allem durch den sequentiellen Anteil begrenzt. Dieser Teil muss nacheinander ablaufen und seine Ausführungszeit lässt sich daher nicht durch zusätzliche Prozessoren verringern.
Ein Programm wird dafür in vollständig sequentielle und vollständig parallele Abschnitte zerlegt. Dabei ist T die Gesamtlaufzeit auf einem Kern, t_S die Laufzeit des seriellen Programmabschnitts, t_P die Laufzeit der parallelen Programmabschnitte und n_P die Zahl der Prozessoren, die diese parallelen Abschnitte nutzen können. Für einen Kern gilt: T = t_S + t_P.
Vollständig parallel kann ein Programm nicht sein: Beispielsweise laufen Prozess-Initialisierung oder Speicherverwaltung nur einmalig auf einem Prozessor ab. Außerdem können Berechnungsschritte von bestimmten Ergebnissen abhängen und müssen deshalb nacheinander erfolgen.
Berechnung des Speedups
Bei n_P Prozessoren verkürzt sich nur der parallele Anteil auf t_P / n_P. Der Speedup-Faktor η_S, also das Verhältnis der ursprünglichen zur beschleunigten Laufzeit, ist:
η_S = T / (t_S + t_P / n_P) ≤ T / t_S = T / (T − t_P).
Die obere Schranke zeigt, dass zusätzliche Prozessoren die Beschleunigung nicht unbegrenzt erhöhen können. Ein Programm mit 20 Stunden Laufzeit, von denen 1 Stunde sequentiell ist, besitzt 19 Stunden beziehungsweise 95 % parallelisierbaren Aufwand. Selbst bei unendlich vielen Prozessoren kann die Gesamtrechenzeit nicht unter 1 Stunde sinken. Der maximale Speedup beträgt deshalb Faktor 20.
Mit steigender Prozessoranzahl hängt die Beschleunigung immer stärker vom sequentiellen Anteil und von der Kommunikation zwischen den Prozessoren ab. Zusätzlich entstehen Kosten für Kommunikation und Synchronisierung. Berücksichtigt man den Synchronisierungs-Zeitaufwand t_O(n_P), gilt:
η_S = T / (t_S + t_O(n_P) + t_P / n_P) ≤ T / t_S = T / (T − t_P).
Da t_O(n_P) mit steigender Prozessorzahl zunimmt, nähert sich die Speedup-Kurve nicht mehr T / t_S an. Sie erreicht stattdessen ein Maximum und fällt danach wieder ab: Bei sehr vielen Prozessoren kann der Aufwand für Übertragung, Synchronisierung und Rücksendung größer werden als die durch zusätzliche Kerne eingesparte Rechenzeit.
Grenzen und verwandte Anwendungen
Als Kritikpunkt gilt, dass das Gesetz Faktoren außer Acht lässt, die den Speedup positiv beeinflussen können. Jede zusätzliche CPU enthält auch Cache, also schnellen Speicher. Bei zehnmal so vielen Kernen verzehnfacht sich daher auch die Menge dieses Speichers. Im günstigen Fall kann die gesamte Problemgröße im Cache statt im langsameren Hauptspeicher liegen. Dann ist ein super-linearer Speedup möglich, also eine Beschleunigung, die über die zusätzliche reine Rechenleistung hinausgeht.
Dieser Effekt kann aber auch daraus folgen, dass der Vergleich den Cache als Teil des Prozessormoduls einbezieht. Ohne Berücksichtigung der Cache-Größe ergäbe sich kein solcher super-linearer Speedup. Die Aussage Amdahls über den maximalen Speedup bleibt in beiden Fällen gültig.
Das Gesetz ist auch in der Betriebswirtschaftslehre bedeutsam, besonders im Operations Research bei Ressourcenallokationen. Eng verwandt ist Gustafsons Gesetz, das fehlende Aspekte des Amdahlschen Gesetzes berücksichtigt. Das mooresche Gesetz analysiert dagegen den Speedup von Computerchips im Allgemeinen.