Amdahls Gesetz

Die theoretische Beschleunigung der Latenz der Ausführung eines Programms als Funktion der Anzahl der Prozessoren, die es ausführen, gemäß Amdahls Gesetz. Die Beschleunigung ist durch den seriellen Teil des Programms begrenzt. Wenn beispielsweise 95% des Programms parallelisiert werden können, wäre die theoretische maximale Beschleunigung unter Verwendung des parallelen Computing 20 -mal.

Im Rechnerarchitektur, Amdahls Gesetz (oder Amdahls Argument^[1]) ist eine Formel, die die theoretische gibt beschleunigen in Latenz der Ausführung einer Aufgabe bei festen Arbeitsbelastung Dies ist von einem System zu erwarten, dessen Ressourcen verbessert werden. Insbesondere heißt es, dass "die durch Optimierung eines einzelnen Teils eines Systems gewonnene Gesamtleistungsverbesserung durch den Bruchteil der Zeit begrenzt ist, in dem der verbesserte Teil tatsächlich verwendet wird".^{[2][Seite benötigt]} Es ist nach nach Informatiker Gene Amdahlund wurde am vorgestellt Afips Spring Joint Computer Conference im Jahr 1967.

Amdahls Gesetz wird oft in verwendet Parallele Computing Um die theoretische Beschleunigung bei der Verwendung mehrerer Prozessoren vorherzusagen. Wenn beispielsweise ein Programm 20 Stunden mit einem einzelnen Thread abgeschlossen ist, aber ein einstündiger Teil des Programms nicht parallelisiert werden kann, kann dies nur die verbleibenden 19 Stunden “(p = 0,95) Die Ausführungszeit kann parallelisiert werden, unabhängig davon, wie viele Themen einer parallelisierten Ausführung dieses Programms gewidmet sind, kann die Mindestausführungszeit nicht weniger als eine Stunde betragen. Daher ist die theoretische Beschleunigung auf die 20 -fache der einzelnen Fadenleistung beschränkt. ${\ displayStyle \ links ({\ dfrac {1} {1-p}} = 20 \ rechts)}$.

Definition

Amdahls Gesetz kann auf folgende Weise formuliert werden:^[3]

$oder$

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, dass der Teil, der ursprünglich von verbesserten Ressourcen profitiert, profitiert.

Außerdem,

$oder } 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 die theoretische Beschleunigung unabhängig von der Größe der Verbesserung immer durch den Teil der Aufgabe begrenzt ist, das nicht von der Verbesserung profitieren kann .

Amdahls Gesetz gilt nur für die Fälle, in denen die Problemgröße festgelegt ist. In der Praxis werden in der Praxis, wenn mehr Computerressourcen verfügbar werden, tendenziell für größere Probleme (größere Datensätze) verwendet, und die Zeit, die im parallelisierbaren Teil verbracht wird, wird häufig viel schneller als die von Natur aus serielle Arbeit. In diesem Fall, Gustafsons Gesetz Gibt eine weniger pessimistische und realistischere Bewertung der parallelen Leistung.^[4]

Ableitung

Eine von einem System ausgeführte Aufgabe, deren Ressourcen im Vergleich zu einem anfänglichen ähnlichen System verbessert werden, 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 verarbeitet. Ein Teil dieses Programms kann das Verzeichnis der Festplatte scannen und eine Liste von Dateien intern im Speicher erstellen. Danach übergibt ein weiterer Teil des Programms jede Datei an eine separate Faden zum Bearbeiten. Der Teil, der das Verzeichnis scannt und die Dateiliste erstellt, kann nicht auf einem parallelen Computer beschleunigt werden, aber der Teil, der die Dateien verarbeitet.

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

${\ displayStyle t = (1-p) t+pt.}$

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

${\ displayStyle {\ frac {p} {s}} t.}$

Die theoretische Ausführungszeit ${\ displayStyle t (s)}$ der gesamten Aufgabe nach der Verbesserung der Ressourcen ist damals:

${\ displayStyle t (s) = (1-p) t+{\ frac {p} {s}} t.}$

Amdahls Gesetz gibt das theoretische beschleunigen in Latenz der Ausführung der gesamten Aufgabe bei fester Arbeitsbelastung ${\ displayStyle W}$, was ergibt

$oder {1-p+{\ frac {p} {s}}}}.}$

Parallelprogramme

Wenn 30% der Ausführungszeit Gegenstand einer Beschleunigung sein können, p wird 0,3 sein; Wenn die Verbesserung den betroffenen Teil doppelt so schnell macht, s wird 2. Amdahls Gesetz besagt, dass die Gesamtbeschleunigung der Verbesserung sein wird:

${\ displaystyle s _ {\ text {latency}} = {\ frac {1} {1-p+{\ frac {p} {s}}}} = {\ frac {1} {1-0.3+{\ frac {{{\ frac {1 {1-0.3+{\ frac {{{\ frac {1 {1-0.3+{\ frac {{{\ frac {1 {1-0.3+{\ frac {{{\ frac {1-1-0.3+{\ frac {{{{ 0.3} {2}}}} = 1.18.}$

Nehmen wir beispielsweise an, dass wir eine serielle Aufgabe erhalten, die in vier aufeinanderfolgende Teile unterteilt ist, deren Prozentsätze der Ausführungszeit sind p1 = 0,11, p2 = 0,18, p3 = 0,23, und p4 = 0,48 beziehungsweise. Dann wird uns gesagt, dass der 1. Teil nicht beschleunigt ist, also s1 = 1, während der 2. Teil 5 Mal beschleunigt ist s2 = 5Der dritte Teil wird 20 Mal beschleunigt, also s3 = 20und der 4. Teil ist 1,6 Mal beschleunigt, also s4 = 1,6. Durch die Verwendung von Amdahlschen Gesetz

$oder }+{\ frac {p4} {s4}}}} = {\ frac {1} {{\ frac {0.11} {1}}+{\ frac {0.18} {5}}+{{{0,23 {0,23} {0,23} {0,23} {20}}+{\ frac {0,48} {1.6}}}} = 2.19.}$

Beachten Sie, wie die 5 -mal- und 20 -fache Beschleunigung auf dem 2. bzw. 3. Teilen keine große Auswirkung auf die Gesamtbeschläge haben, wenn der 4. Teil (48% der Ausführungszeit) nur um das 1,6 -fache beschleunigt wird.

Serienprogramme

Angenommen, eine Aufgabe hat zwei unabhängige Teile, A und B. Teil B dauert ungefähr 25% der Zeit der gesamten Berechnung. Wenn man sehr hart arbeitet, kann man diesen Teil 5 -mal schneller machen, aber dies verkürzt die Zeit der gesamten Berechnung nur geringfügig. Im Gegensatz dazu muss man möglicherweise weniger Arbeit ausführen, um teilzunehmen A doppelt so schnell durchführen. Dadurch wird die Berechnung viel schneller als durch Optimierung des Teils B, obwohl ein Teil B'S Beschleunigung ist in Bezug auf das Verhältnis (5 -mal gegenüber 2 -mal) größer.

Zum Beispiel mit einem seriellen Programm in zwei Teilen A und B für welche T_A = 3 s und T_B = 1 sAnwesend

• Wenn Teil B wird 5 -mal schneller laufen, das heißt s = 5 und p = T_B/(T_A + T_B) = 0,25, dann

$oder$

• Wenn Teil A wird 2 -mal schneller laufen, das heißt s = 2 und p = T_A/(T_A + T_B) = 0,75, dann

$oder$

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

$oder$

• Teil verbessern A Um den Faktor 2 erhöht die Gesamtprogrammgeschwindigkeit um den Faktor 1,60, was es um 37,5% schneller macht als die ursprüngliche Berechnung.
• Teil des Teils jedoch verbessert B Um den Faktor 5, der vermutlich mehr Aufwand erfordert, wird nur ein Geschwindigkeitsfaktor von 1,25 erreicht, was es 20% schneller macht.

Optimierung des sequentiellen Teils der parallelen Programme

Wenn der nicht parallelisierbare Teil durch den Faktor von optimiert wird ${\ displayStyle o}$, dann

$oder$

Aus dem Amdahlschen Gesetz folgt, dass die Beschleunigung aufgrund von Parallelität gegeben wird durch

$oder } {O}}+{p}} {{\ frac {1-p} {o}}+{\ frac {p} {s}}}}.}.}.}.}.$

Wann ${\ displayStyle s = 1}$, wir haben ${\ displayStyle S _ {\ text {Latenz}} (o, s) = 1}$Dies bedeutet, dass die Beschleunigung in Bezug auf die Ausführungszeit gemessen wird, nachdem der nicht parallelisierbare Teil optimiert wurde.

Wann ${\ displayStyle S = \ Infty}$Anwesend

$oder 1} {o}}+{p}} {{\ frac {1-p} {o}}+{\ frac {p} {s}}}} = 1+{\ frac {p} {1-P }}Ö.}$

Wenn ${\ displayStyle 1-p = 0,4}$, ${\ displayStyle o = 2}$ und ${\ displayStyle s = 5}$, dann:

$oder 2}}+0.6} {{\ frac {0,4} {2}}+{\ frac {0,6} {5}}}} = 2.5.}$

Transformation sequentielle Teile paralleler Programme in parallelisierbar

Als nächstes betrachten wir den Fall, in dem der nicht parallelisierbare Teil um einen Faktor von reduziert wird ${\ displayStyle o '}$und der parallelisierbare Teil wird entsprechend erhöht. Dann

${\ displaystyle t '(o', s) = {\ frac {1-p} {o '}} t+\ links (1-{\ frac {1-P} {o'}} \ rechts) {\ frac {T} {s}}.}$

Aus dem Amdahlschen Gesetz folgt, dass die Beschleunigung aufgrund von Parallelität gegeben wird durch

$oder oder$

Die obige Ableitung stimmt mit der Analyse von Jakob Jenkov über die Ausführungszeit im Vergleich zu beschleunigten Kompromisse überein.^[5]

Verhältnis zum Gesetz der Rückgabe von Renditen

Amdahls Gesetz wird oft mit dem in Verbindung gebracht Gesetz des abnehmenden ErtragsWährend nur ein Sonderfall der Anwendung von Amdahls Gesetz dem Gesetz der Verringerung der Renditen zeigt. Wenn man optimal (in Bezug auf die erreichte Beschleunigung) wählt, was zu verbessert werden soll, wird sich die monotoner Verbesserungen im Zusammenhang mit der Verbesserung monoton verringern. Wenn man jedoch nicht optimal wählt, kann nach Verbesserung einer suboptimalen Komponente und der Weiterentwicklung einer optimaleren Komponente eine Erhöhung der Rendite feststellen. Beachten Sie, dass es oft rational ist, ein System in einer Reihenfolge zu verbessern, die in diesem Sinne "nicht optimal" ist, da einige Verbesserungen schwieriger sind oder eine größere Entwicklungszeit erfordern als andere.

Das Amdahl-Gesetz repräsentiert das Gesetz der Rückgangsrendite, wenn man überlegt, welche Art von Rückgabe man erzielt, indem er mehr Prozessoren zu einer Maschine hinzufügt. Wenn man eine Berechnung mit fester Größe ausführt, die alle verfügbaren Prozessoren zu ihrer Kapazität verwendet. Jeder neue Prozessor, der dem System hinzugefügt wurde, fügt weniger nutzbare Leistung als der vorherige hinzu. Jedes Mal, wenn man die Anzahl der Prozessoren verdoppelt, nimmt das Beschleunigungsverhältnis ab, da der Gesamtdurchsatz in Richtung der Grenze von 1/(1 -p).

Diese Analyse vernachlässigt andere potenzielle Engpässe wie z. Speicherbandbreite und I/O -Bandbreite. Wenn diese Ressourcen nicht mit der Anzahl der Prozessoren skaliert werden, bietet das Hinzufügen von Prozessoren lediglich noch geringere Renditen.

Eine Implikation des Amdahlschen Gesetz Heterogenes Computer Techniken sind erforderlich.^[6] Es gibt neue Modelle zur Geschwindigkeits- und Energieverbrauchsmodelle, die auf einer allgemeineren Darstellung der Heterogenität basieren, die als normale Formheterogenität bezeichnet wird und die einen breiten Bereich heterogener vieler Kernarchitekturen unterstützen. Diese Modellierungsmethoden zielen darauf ab, die Effizienz und die Leistungsbereiche der Systemleistung vorherzusagen und Forschung und Entwicklung auf Hardware- und Systemsoftwareebene zu erleichtern.^[7][8]

Siehe auch

• Gustafsons Gesetz
• Analyse paralleler Algorithmen
• Kritische Pfadmethode
• Moores Gesetz

Verweise

Weitere Lektüre

• Amdahl, Gene M. (1967). "Gültigkeit des einzelnen Prozessoransatzes zur Erreichung großer Computerfunktionen" (PDF). AFIPS -Konferenzverfahren (30): 483–485. doi:10.1145/1465482.1465560.

Externe Links

• "Parallele Programmierung: Wenn Amdahls Gesetz nicht anwendbar ist?". 2011-06-25. Archiviert von das Original Am 2013-04-14. Abgerufen 2011-06-26.
• Gene M. Amdahl (1989), Oral History Interview mit Gene M. Amdahl, Charles Babbage Institute, Universität von Minnesota, HDL:11299/104341. Amdahl diskutiert seine Absolventen an der Universität von Wisconsin und seine Gestaltung von Wisc. Erörtert seine Rolle bei der Gestaltung mehrerer Computer für IBM, einschließlich der STRECKEN, IBM 701, und IBM 704. Er bespricht seine Arbeit mit Nathaniel Rochester und IBMs Management des Designprozesses. Erwähnt mit Ramo-wooldridge, Aeronutronisch, und Computer Sciences Corporation
• Amdahls Gesetz: Nicht alle Leistungsverbesserungen werden gleich geschaffen (2007)
• "Amdahls Gesetz" von Joel F. Klein, Wolfram Demonstrationsprojekt (2007)
• Amdahls Gesetz in der Multicore -Ära (Juli 2008)
• Was zum Teufel $@! Ist die Parallelität sowieso? (Charles Leiser, Mai 2008)
• Bewertung 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 als Funktion der Anzahl der Threads, von George Popov, Valeri Mladenov und Nikos Mastorakis (Januar 2010)
• Danny Hillis - Nachweis am Amdahls Gesetz falsch, Video im Oktober 2016 aufgezeichnet