Amdahls Gesetz - Amdahl's law

Die theoretische Beschleunigung der Latenzzeit bei der Ausführung eines Programms als Funktion der Anzahl der Prozessoren, die es ausführen, nach dem Gesetz von Amdahl. Die Beschleunigung wird durch den seriellen Teil des Programms begrenzt. Wenn beispielsweise 95 % des Programms parallelisiert werden können, beträgt die theoretische maximale Geschwindigkeit bei Verwendung von parallelem Rechnen das 20-fache.

In der Computerarchitektur , Amdahl Gesetz (oder Amdahl Argument ist) eine Formel , die das theoretische gibt Speedup in Latenz der Ausführung einer Aufgabe zu fester Arbeitsbelastung , die verbessert werden ein System , deren Ressourcen zu erwarten ist. Es ist nach dem Informatiker Gene Amdahl benannt und wurde 1967 auf der AFIPS Spring Joint Computer Conference vorgestellt.

Das Amdahl-Gesetz wird häufig beim parallelen Rechnen verwendet , um die theoretische Beschleunigung bei Verwendung mehrerer Prozessoren vorherzusagen. Wenn ein Programm beispielsweise 20 Stunden benötigt, um mit einem einzelnen Thread fertig zu werden, aber ein einstündiger Teil des Programms nicht parallelisiert werden kann, können daher nur die verbleibenden 19 Stunden ( p = 0,95 ) der Ausführungszeit parallelisiert werden, unabhängig von wie viele Threads einer parallelisierten Ausführung dieses Programms gewidmet sind, darf die minimale Ausführungszeit nicht weniger als eine Stunde betragen. Daher ist die theoretische Beschleunigung auf höchstens das 20-fache der Single-Thread-Leistung begrenzt, . ${\displaystyle \left({\dfrac {1}{1-p}}=20\right)}$

Definition

Das Gesetz von Amdahl lässt sich wie folgt formulieren:

${\displaystyle S_{\text{Latenz}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}}$

wo

• S- _Latenz ist die theoretische Beschleunigung der Ausführung der gesamten Aufgabe;
• s ist die Beschleunigung des Teils der Aufgabe, der von verbesserten Systemressourcen profitiert;
• p ist der Anteil der Ausführungszeit, den der Teil, der von verbesserten Ressourcen profitiert, ursprünglich belegt hat.

Außerdem,

${\displaystyle {\begin{cases}S_{\text{latency}}(s)\leq {\dfrac {1}{1-p}}\\[8pt]\lim \limits_{s\to \infty }S_{\text{Latenz}}(s)={\dfrac {1}{1-p}}.\end{cases}}}$

zeigt, dass die theoretische Beschleunigung der Ausführung der gesamten Aufgabe mit der Verbesserung der Ressourcen des Systems zunimmt und dass unabhängig vom Ausmaß der Verbesserung die theoretische Beschleunigung immer durch den Teil der Aufgabe begrenzt ist, der von der Verbesserung nicht profitieren kann .

Das Gesetz von Amdahl gilt nur für die Fälle, in denen die Problemgröße festgelegt ist. In der Praxis werden sie mit zunehmender Verfügbarkeit von Rechenressourcen eher für größere Probleme (größere Datensätze) verwendet, und die Zeit, die im parallelisierbaren Teil verbracht wird, wächst oft viel schneller als die inhärent serielle Arbeit. In diesem Fall gibt das Gesetz von Gustafson eine weniger pessimistische und realistischere Einschätzung der parallelen Leistung.

Ableitung

Eine Aufgabe, die von einem System ausgeführt wird, dessen Ressourcen im Vergleich zu einem anfänglichen ähnlichen System verbessert sind, kann in zwei Teile aufgeteilt werden:

• ein Teil, der nicht von der Verbesserung der Ressourcen des Systems profitiert;
• ein Teil, der von der Verbesserung der Ressourcen des Systems profitiert.

Ein Beispiel ist ein Computerprogramm, das Dateien von der Festplatte verarbeitet. Ein Teil dieses Programms kann das Verzeichnis der Festplatte scannen und eine Liste von Dateien intern im Speicher erstellen. Danach übergibt ein anderer Teil des Programms jede Datei zur Verarbeitung an einen separaten Thread . Der Teil, der das Verzeichnis durchsucht und die Dateiliste erstellt, kann auf einem Parallelcomputer nicht beschleunigt werden, wohl aber der Teil, der die Dateien verarbeitet.

Die Ausführungszeit der gesamten Aufgabe vor der Verbesserung der Ressourcen des Systems wird als bezeichnet . Es umfasst die Ausführungszeit des Teils, der von der Verbesserung der Ressourcen nicht profitieren würde, und die Ausführungszeit des Teils, der davon profitieren würde. Der Bruchteil der Ausführungszeit der Aufgabe, der von der Verbesserung der Ressourcen profitieren würde, wird mit bezeichnet . Diejenige, die den Teil betrifft, der davon nicht profitieren würde, ist daher . Dann: ${\displaystyle T}$${\displaystyle p}$${\displaystyle 1-p}$

${\displaystyle T=(1-p)T+pT.}$

Es ist die Ausführung des Teils, der von der Verbesserung der Ressourcen profitiert, der um den Faktor nach der Verbesserung der Ressourcen beschleunigt wird . Folglich bleibt die Ausführungszeit des Teils, der davon nicht profitiert, gleich, während der Teil, der davon profitiert, wird: ${\displaystyle s}$

${\displaystyle {\frac {p}{s}}T.}$

Die theoretische Ausführungszeit der gesamten Aufgabe nach der Verbesserung der Ressourcen beträgt dann: ${\displaystyle T(s)}$

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

Amdahl Gesetz gibt die theoretische Beschleunigung in Latenz der Ausführung der gesamten Aufgabe zu fester Arbeitsbelastung${\displaystyle W}$ , die Ausbeuten

${\displaystyle S_{\text{Latenz}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1} {1-p+{\frac{p}{s}}}}.}$

Parallele Programme

Wenn 30 % der Ausführungszeit beschleunigt werden können, beträgt p 0,3; wenn die Verbesserung das betroffene Teil doppelt so schnell macht, ist s 2. Das Gesetz von Amdahl besagt, dass die Gesamtgeschwindigkeit der Anwendung der Verbesserung beträgt:

${\displaystyle S_{\text{Latenz}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac { 0,3}{2}}}}=1,18.}$

Angenommen, wir erhalten eine serielle Aufgabe, die in vier aufeinanderfolgende Teile aufgeteilt ist, deren prozentuale Ausführungszeit p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 bzw. p 4 = 0,48 beträgt. Dann wird uns gesagt, dass der 1. Teil nicht beschleunigt wird, also s 1 = 1 , während der 2. Teil 5 Mal beschleunigt wird, also s 2 = 5 , der 3. Teil wird 20 Mal beschleunigt, also s 3 = 20 , und der vierte Teil wird 1,6-fach beschleunigt, also s 4 = 1,6 . Durch die Anwendung des Amdahl-Gesetzes beträgt die Gesamtbeschleunigung

${\displaystyle S_{\text{Latenz}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3} }+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0,11}{1}}+{\frac {0,18}{5}}+{\frac {0,23} {20}}+{\frac {0,48}{1,6}}}}=2,19.}$

Beachten Sie, dass die 5-fache bzw. 20-fache Beschleunigung des 2. bzw. 3. Teils keinen großen Einfluss auf die Gesamtbeschleunigung hat, wenn der 4. Teil (48% der Ausführungszeit) nur um das 1,6-fache beschleunigt wird.

Serielle Programme

Angenommen, eine Aufgabe hat zwei unabhängige Teile, A und B . Teil B nimmt ungefähr 25 % der Zeit der gesamten Berechnung in Anspruch. Wenn man sehr hart arbeitet, kann man diesen Teil vielleicht fünfmal schneller machen, aber dies reduziert die Zeit der gesamten Berechnung nur geringfügig. Im Gegensatz dazu muss man möglicherweise weniger Arbeit leisten, damit Teil A doppelt so schnell funktioniert . Dadurch wird die Berechnung viel schneller als durch einen Teil der Optimierung B , obwohl Teil B‘ s Speedup mehr in Bezug auf das Verhältnis ist, (5 - mal im Vergleich zu 2 - mal).

Zum Beispiel mit einem seriellen Programm in zwei Teilen A und B, für das T _A = 3 s und T _B = 1 s ist ,

• wenn Teil B 5 mal schneller läuft, also s = 5 und p = T _B /( T _A + T _B ) = 0,25 , dann

${\displaystyle S_{\text{Latenz}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;}$

• wenn Teil A 2 mal schneller laufen soll, also s = 2 und p = T _A /( T _A + T _B ) = 0,75 , dann

${\displaystyle S_{\text{Latenz}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.}$

Daher ist es besser , Teil A 2 mal schneller laufen zu lassen, als Teil B 5 mal schneller laufen zu lassen. Die prozentuale Geschwindigkeitsverbesserung kann berechnet werden als

${\displaystyle {\text{prozentuale Verbesserung}}=100\left(1-{\frac {1}{S_{\text{Latenz}}}}\right).}$

• Eine Verbesserung von Teil A um den Faktor 2 erhöht die Gesamtgeschwindigkeit des Programms um den Faktor 1,60, was ihn um 37,5% schneller macht als die ursprüngliche Berechnung.
• Eine Verbesserung von Teil B um den Faktor 5, was vermutlich mehr Aufwand erfordert, wird jedoch nur einen Gesamtgeschwindigkeitsfaktor von 1,25 erreichen, was ihn um 20 % schneller macht.

Optimierung des sequentiellen Teils paralleler Programme

Wenn der nicht parallelisierbare Teil um den Faktor optimiert wird , dann ${\displaystyle O}$

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

Aus dem Gesetz von Amdahl folgt, dass die Beschleunigung durch Parallelität gegeben ist durch

${\displaystyle S_{\text{Latenz}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1 }{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}$

Wenn haben wir , was bedeutet, dass die Beschleunigung in Bezug auf die Ausführungszeit gemessen wird, nachdem der nicht parallelisierbare Teil optimiert wurde. ${\displaystyle s=1}$${\displaystyle S_{\text{Latenz}}(O,s)=1}$

Wann , ${\displaystyle s=\infty}$

${\displaystyle S_{\text{Latenz}}(O,\infty)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac { 1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}}=1+{\frac {p}{1-p }}Ö.}$

Wenn , und , dann: ${\displaystyle 1-p=0.4}$${\displaystyle O=2}$${\displaystyle s=5}$

${\displaystyle S_{\text{Latenz}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0,4}{\frac {1}{ 2}}+0,6}{{\frac {0,4}{2}}+{\frac {0,6}{5}}}}=2,5.}$

Umwandeln von sequentiellen Teilen paralleler Programme in parallelisierbare

Als nächstes betrachten wir den Fall, bei dem der nicht parallelisierbare Teil um einen Faktor von verringert wird und der parallelisierbare Teil entsprechend erhöht wird. Dann ${\displaystyle O'}$

${\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

Aus dem Gesetz von Amdahl folgt, dass die Beschleunigung durch Parallelität gegeben ist durch

${\displaystyle S'_{\text{Latenz}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{ {\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}$

Die obige Ableitung stimmt mit Jakob Jenkovs Analyse des Kompromisses zwischen Ausführungszeit und Beschleunigung überein.

Verhältnis zum Gesetz vom abnehmenden Ertrag

Das Gesetz von Amdahl wird oft mit dem Gesetz des abnehmenden Ertrags verschmolzen , während nur ein Sonderfall der Anwendung des Amdahl-Gesetzes das Gesetz des abnehmenden Ertrags zeigt. Wählt man optimal (im Hinblick auf die erreichte Beschleunigung) aus, was verbessert werden soll, dann sieht man mit zunehmender Verbesserung monoton abnehmende Verbesserungen. Wenn man jedoch nicht optimal wählt, nachdem man eine suboptimale Komponente verbessert und eine optimalere Komponente verbessert hat, kann man eine Erhöhung der Rendite feststellen. Beachten Sie, dass es oft sinnvoll ist, ein System in einer in diesem Sinne "nicht optimalen" Reihenfolge zu verbessern, da einige Verbesserungen schwieriger sind oder eine längere Entwicklungszeit erfordern als andere.

Das Gesetz von Amdahl stellt das Gesetz der abnehmenden Renditen dar, wenn man bedenkt, welche Art von Rendite man erhält, wenn man einer Maschine mehr Prozessoren hinzufügt, wenn man eine Berechnung mit fester Größe durchführt, die alle verfügbaren Prozessoren bis zu ihrer Kapazität ausnutzt. Jeder neue Prozessor, der dem System hinzugefügt wird, fügt weniger nutzbare Leistung hinzu als der vorherige. Jedes Mal, wenn die Anzahl der Prozessoren verdoppelt wird, verringert sich das Geschwindigkeitsverhältnis, da der Gesamtdurchsatz auf die Grenze von 1/(1 − p ) zusteuert  .

Diese Analyse vernachlässigt andere potenzielle Engpässe wie Speicherbandbreite und E/A-Bandbreite. Wenn diese Ressourcen nicht mit der Anzahl der Prozessoren skalieren, bietet das bloße Hinzufügen von Prozessoren noch geringere Erträge.

Eine Implikation des Amdahl-Gesetzes besteht darin, dass zur Beschleunigung realer Anwendungen, die sowohl serielle als auch parallele Teile aufweisen, heterogene Rechentechniken erforderlich sind.

Siehe auch

• Gustavsons Gesetz
• Kritische Pfadmethode
• Moores Gesetz

Verweise

Weiterlesen

• Amdahl, Gene M. (1967). "Gültigkeit des Einzelprozessor-Ansatzes zur Erzielung von Rechenkapazitäten im großen Maßstab" (PDF) . Tagungsband der AFIPS-Konferenz (30): 483–485. doi : 10.1145/1465482.1465560 .

Externe Links

• "Parallelprogrammierung: Wenn das Gesetz von Amdahl nicht anwendbar ist?" . 2011-06-25. Archiviert vom Original am 2013-04-14 . Abgerufen am 26.06.2011 .
• Gene M. Amdahl (1989), Oral History Interview mit Gene M. Amdahl , Charles Babbage Institute , University of Minnesota, hdl : 11299/104341. Amdahl spricht über seine Abschlussarbeit an der University of Wisconsin und sein Design von WISC . Bespricht seine Rolle beim Design mehrerer Computer für IBM, einschließlich des STRETCH , IBM 701 und IBM 704 . Er bespricht seine Arbeit mit Nathaniel Rochester und dem Management des Designprozesses von IBM. Erwähnungen arbeiten mit Ramo-Wooldridge , Aeronutronic und Computer Sciences Corporation zusammen
• Amdahls Gesetz: Nicht alle Leistungsverbesserungen sind gleich (2007)
• "Amdahls Gesetz" von Joel F. Klein, Wolfram Demonstrations Project (2007)
• Amdahls Gesetz in der Multicore-Ära (Juli 2008)
• Was zum $#@! ist Parallelität, irgendwie? (Charles Leiserson, Mai 2008)
• Evaluierung der Intel Core i7 Turbo Boost-Funktion von James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat und Alexandra Fedorova (2009)
• Berechnung der Beschleunigung paralleler Programme in Abhängigkeit von der Anzahl der Threads , von George Popov, Valeri Mladenov und Nikos Mastorakis (Januar 2010)
• Danny Hillis - Beweise, dass Amdahls Gesetz falsch ist, Video aufgenommen im Oktober 2016