Gustafsons Gesetz

Evolution nach Gustafsons Gesetz der theoretischen Beschleunigung in der Latenz der Ausführung eines Programms als Funktion der Anzahl der ausführenden Prozessoren für verschiedene Werte von a.

Im Rechnerarchitektur, Gustafsons Gesetz (oder Gustafson -Barsis -Gesetz^[1]) gibt die beschleunigen in der Ausführungszeit einer Aufgabe, die theoretisch vom parallelen Computing unter Verwendung eines hypothetischen Laufs von durchnimmt die Aufgabe auf einer einkernigen Maschine als Grundlinie. Anders ausgedrückt, es ist die theoretische "Verlangsamung" von einem bereits parallelisiert Aufgabe, wenn Sie auf einer Serienmaschine ausgeführt werden. Es ist nach Informatiker benannt John L. Gustafson und sein Kollege Edwin H. Barsis und wurde in dem Artikel vorgestellt Neubewertung des Amdahls Gesetzes 1988.^[2]

Definition

Gustafson schätzte die Beschleunigung ${\ displayStyle S}$ eines Programms, das durch die Verwendung paralleler Computing wie folgt gewonnen wurde:

$oder$

wo

• ${\ displayStyle S}$ ist die theoretische Beschleunigung des Programms mit Parallelität (skalierte Beschleunigung^[2]);
• ${\ displayStyle n}$ ist die Anzahl der Prozessoren;
• ${\ displayStyle S}$ und ${\ displayStyle p}$ sind die Fraktionen der Zeit, die für die Ausführung der seriellen Teile und die parallelen Teile des Programms auf dem parallel System, wo ${\ displayStyle s+p = 1}$;

Alternative, ${\ displayStyle S}$ kann mit Verwendung ausgedrückt werden ${\ displayStyle p}$:

$oder$

Das Gustafson -Gesetz befasst sich mit den Mängel von Amdahls Gesetz, was auf der Annahme eines festen Grundstücks beruht ProblemgrößeDas ist eine Arbeitsbelastung ausführend, die sich in Bezug auf die Verbesserung der Ressourcen nicht ändert. Gustafsons Gesetz schlägt stattdessen vor, dass Programmierer dazu neigen, die Größe der Probleme zu erhöhen, um die Rechenleistung, die mit der Verbesserung der Ressourcen verfügbar zu sein wird, vollständig auszunutzen.^[2]

Gustafson und seine Kollegen beobachteten diese Zeit für den seriellen Teil von ihrer Arbeitsbelastung weiterhin nicht als Problem und die Systemskala.^[2] das ist, ${\ displayStyle S}$ Ist repariert. Dies gibt ein lineares Modell zwischen der Prozessorzahl ${\ displayStyle n}$ und die Beschleunigung ${\ displayStyle S}$ mit Neigung ${\ displayStyle 1-s}$, wie in der obigen Abbildung gezeigt (die unterschiedliche Notationen verwendet: ${\ displayStyle p}$ zum ${\ displayStyle n}$ und ${\ displayStyle a}$ zum ${\ displayStyle S}$). Ebenfalls, ${\ displayStyle S}$ skaliert linear mit ${\ displayStyle S}$ eher als exponentiell im Amdahl -Gesetz.^[2] Mit diesen Beobachtungen erwarten Gustafson "erwarten, dass [ed] [ihren] Erfolg [auf paralleles Computing] auf einen breiteren Bereich von Anwendungen und sogar größere Werte für erweitert wird ${\ displayStyle n}$".^[2]

Die Auswirkungen des Gustafson -Gesetzes bestand darin, die Forschungsziele zu verändern, um Probleme auszuwählen oder neu formuliert, so dass die Lösung eines größeren Problems in der gleichen Zeit möglich ist. In gewisser Weise definiert das Gesetz die Effizienz neu, da die durch den sequentiellen Teil eines Programms auferlegten Einschränkungen durch Erhöhen der Gesamtberechnungsmenge entgegengewirkt werden können.

Ableitung

Die Ausführungszeit eines Programms, das auf einem ausgeführt wird parallel System kann in zwei Teile aufgeteilt werden:

• ein Teil, der tut nicht profitieren von der zunehmenden Anzahl von Prozessoren (serieller Teil);
• Ein Teil, der von der zunehmenden Anzahl von Prozessoren profitiert (paralleler Teil).

Beispiel. - 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 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.

Lassen Sie die Gesamtausführungszeit ohne Verlust der Allgemeinheit auf die parallel System sein ${\ displayStyle t = 1}$. Bezeichnen die Seriennauer als ${\ displayStyle S}$ und die parallele Zeit als ${\ displayStyle p}$, wo ${\ displayStyle s+p = 1}$. Bezeichnen die Anzahl der Prozessor als ${\ displayStyle n}$.

Hypothetisch dauert der serielle Teil immer noch, wenn das Programm auf einem seriellen System (nur ein Prozessor) ausgeführt wird ${\ displayStyle S}$, während der parallele Teil jetzt nimmt ${\ displayStyle np}$. Die Ausführungszeit des seriellen Systems lautet:

${\ displayStyle t '= s+np}$

Verwendung ${\ displayStyle t '}$ Als Grundlinie lautet die Beschleunigung für das parallele System:

$oder$

Durch Ersetzen ${\ displayStyle p = 1-s}$ oder ${\ displayStyle s = 1-p}$Es können verschiedene Formen im vorherigen Abschnitt abgeleitet werden.

Anwendungen

Anwendung in der Forschung

Das Gesetz von Amdahl setzt voraus, dass die Rechenanforderungen bei einer erhöhten Verarbeitungsleistung gleich bleiben. Mit anderen Worten, eine Analyse derselben Daten dauert weniger Zeit, da mehr Rechenleistung.

Gustafson hingegen argumentiert, dass mehr Rechenleistung dazu führt, dass die Daten genauer und vollständig analysiert werden: Pixel von Pixel oder Einheit nach Einheit und nicht in größerem Maßstab. Wo es nicht möglich oder praktisch gewesen wäre, die Auswirkungen der nuklearen Detonation auf jedes Gebäude, jedes Auto und deren Inhalt (einschließlich Möbel, Strukturfestigkeit usw.) zu simulieren Antwort, die Zunahme der Rechenleistung führt zu den Forschern, mehr Daten hinzuzufügen, um mehr Variablen besser zu simulieren und ein genaueres Ergebnis zu erzielen.

Anwendung in alltäglichen Computersystemen

Das Amdahl -Gesetz zeigt eine Einschränkung in der Fähigkeit mehrerer Kerne, die Zeit zu verkürzen, die ein Computer benötigt, um zu seinem Betriebssystem zu starten und zur Verwendung bereit zu sein. Unter der Annahme, dass der Boot -Prozess größtenteils parallel war, kann die Vierfalle -Computerleistung eines Systems, das eine Minute dauerte, um die Startzeit auf etwas mehr als fünfzehn Sekunden zu verkürzen. Aber immer mehr Parallelisierung würde letztendlich nicht dazu führen, dass das Bootup schneller wird, wenn ein Teil des Startprozesses von Natur aus sequentiell wäre.

Gustafsons Law argumentiert, dass eine vierfache Zunahme der Rechenleistung stattdessen zu einer ähnlichen Erwartung der Erwartungen an das, wozu das System fähig sein werden, führen würde. Wenn die einminütige Ladezeit für die meisten Benutzer akzeptabel ist, ist dies ein Ausgangspunkt, um die Funktionen und Funktionen des Systems zu erhöhen. Die Zeit, die zum Starten des Betriebssystems benötigt wird, ist gleich, d. H. Eine Minute, aber das neue System würde grafischere oder benutzerfreundlichere Funktionen enthalten.

Einschränkungen

Einige Probleme haben keine grundlegend größeren Datensätze. Beispielsweise wird die Verarbeitung eines Datenpunkts pro Weltbürger mit nur wenigen Prozent pro Jahr größer. Der Hauptpunkt des Gustafson -Gesetzes ist, dass solche Probleme wahrscheinlich nicht die fruchtbarsten Anwendungen der Parallelität sind.

Algorithmen mit nichtlinearen Laufzeiten können es schwierig finden, die Parallelität durch Gustafsons Gesetz "entlarvt" zu nutzen. Snyder^[3] weist auf ein ${\ displayStyle o (n^{3})}$ Algorithmus bedeutet, dass die Verdoppelung der Parallelität nur etwa 26% der Problemgröße erhöht. Obwohl es möglich sein mag, eine große Parallelität zu besetzen, kann dies jedoch wenig Vorteil gegenüber der ursprünglichen, weniger gleichzeitigen Lösung bringen - in der Praxis gab es jedoch immer noch erhebliche Verbesserungen.

Hill und Marty^[4] Betonen Sie auch, dass Methoden zur Beschleunigung der sequentiellen Ausführung auch für Multicore -Maschinen noch benötigt werden. Sie weisen darauf hin, dass lokal ineffiziente Methoden global effizient sein können, wenn sie die sequentielle Phase reduzieren. Außerdem Woo und Lee^[5] Untersuchte die Auswirkungen von Energie und Macht auf zukünftige viele Kernprozessoren auf der Grundlage des Amdahls Gesetz .

Al-Hayanni, Rafiev et al. Haben neuartige Geschwindigkeits- und Energieverbrauchsmodelle entwickelt, die auf einer allgemeinen Darstellung der Kernheterogenität basieren, die als normale Form der Heterogenität bezeichnet wird und eine breite Palette heterogener viel-Kern-Architekturen 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.^[6][7]

Siehe auch

• Amdahls Gesetz
• Skalierbare Parallelität
• Parkinsons Gesetz
• Jevons Paradox

Verweise