Stellen Sie sich Folgendes vor: Sie haben es eilig, ein köstliches Festmahl zuzubereiten, sind aber durch die Größe Ihrer Küche und die Anzahl der Hände an Deck eingeschränkt. In der Welt des Parallelrechnens sind das Gesetz von Amdahl und das Gesetz von Gustafson die zuverlässigen Rezepte, die Sie zur Optimierung Ihres kulinarischen Meisterwerks benötigen. Sie sind wie die geheimen Zutaten, die die Leistung von Computern über Jahrzehnte hinweg gewürzt haben und es uns ermöglichen, uns an immer schnelleren Verarbeitungsgeschwindigkeiten zu erfreuen. Diese beiden Prinzipien mögen das Yin und Yang des parallelen Rechnens sein und sie leiten technisch versierte Zauberer auf ihrem Weg, das Reich der Multi-Core-Prozessoren und des Hochleistungsrechnens zu erobern. Aber was sind die Gesetze von Amdahl und Gustafson und wie wirken sie einzeln oder im Tandem? Da wir uns der Bedeutung der parallelen Programmierung bewusst sind, werden wir heute in die Feinheiten dieser Gesetze eintauchen und herausfinden, wie sie in den Händen sachkundiger Programmierer als leistungsstarke Werkzeuge eingesetzt werden können.

Inhaltsverzeichnis

• Amdahls Gesetz: Hintergrund

  – Maximale Beschleunigung

  – Vorbehalte

• Gustafsons Gesetz: Hintergrund

  – Skalierte Beschleunigung

  – Vorbehalte

• Starke Skalierung vs. schwache Skalierung

  – Skalierungstests

  — Starke Skalierung

  — Schwache Skalierung

• Schlussfolgerungen

Amdahls Gesetz: Hintergrund

Im Jahr 1967, auf der Spring Joint Computer Conference, traf sich Dr. Gene Amdahl, der bei IBM einige ernsthafte Computer-Zaubereien durchführte, mit drei anderen technisch versierten Leuten, darunter dem klugen Daniel Slotnick, dem Genie hinter dem Innenleben von Illiac-IV. Was hatten sie vor, fragen Sie? Nun, sie dachten über die Zukunft der Computerarchitektur nach. Während dieser Konferenz legte Dr. Gene Amdahl seine Gedanken zu den Hürden dar, denen der „Multiprozessor-Ansatz“ bei der Bewältigung realer Probleme und all ihrer chaotischen Macken gegenübersteht. Und wissen Sie was, er lobte den „Einzelprozessor-Ansatz“ für Probleme dieser Art!

Während seiner Zeit bei IBM fiel Amdahl auf, dass ein erheblicher Teil der Rechenarbeit von etwas beansprucht wurde, das er treffend als „ Data Management Housekeeping “ bezeichnete. Er behauptete felsenfest, dass dieser spezielle Anteil etwa ein Jahrzehnt lang bemerkenswert konstant geblieben sei und beständig 40 % der ausgeführten Anweisungen in Produktionsläufen verschlungen habe.

Was fällt unter das Dach dieser „Housekeeping“-Arbeit? Es umfasst ein breites Spektrum an Rechenaufgaben, die zwar wesentlich sind, aber keinen direkten Beitrag zur Kernaufgabe des Computers leisten. Abhängig vom spezifischen Algorithmus und der Anwendung kann dies Daten-E/A, Vorverarbeitung, Speicherverwaltung, Dateiverwaltung und mehr umfassen. Diese Konsistenz legt nahe, dass bei vielen Anwendungen ein erheblicher Teil der Verarbeitungszeit für diese Aufgaben aufgewendet wird. Ein gewisses Maß an Datenverwaltung ist nahezu unvermeidlich und schwer zu minimieren. Amdahl weist darauf hin, dass dieser Overhead sequentiell erscheint, also Schritt für Schritt erfolgt und für parallele Verarbeitungstechniken ungeeignet ist.

„Eine ziemlich offensichtliche Schlussfolgerung, die an dieser Stelle gezogen werden kann, ist, dass der Aufwand, der für das Erreichen hoher paralleler Verarbeitungsraten aufgewendet wird, verschwendet ist, es sei denn, er geht mit Erfolgen bei sequentiellen Verarbeitungsraten in nahezu derselben Größenordnung einher.“ - Dr. Gene Amdahl [1]

In seiner Originalarbeit [1] fügt Amdahl hinzu, dass der Bereich der „Housekeeping“-Aufgaben nur die Spitze des Eisbergs hinsichtlich der Herausforderungen sei, denen sich der „Multiprozessor“-Ansatz gegenübersieht. Mit seinem beeindruckenden Hintergrund als ausgebildeter theoretischer Physiker mit Doktortitel verfügte Amdahl über ein tiefes Verständnis der realen physikalischen Herausforderungen, für deren Bewältigung Computer entwickelt wurden. Er weist auf viele Komplikationen hin, wie unregelmäßige Grenzen, ungleichmäßige Innenräume sowie räumliche und zeitliche Abhängigkeiten von variablen Zuständen, die allesamt gewaltige Hürden für das „Multiprozessor“-Paradigma darstellen.

Erwägen Sie beispielsweise die Berechnung der Wärmeverteilung auf einem kartesischen 2D-Gitter. An jedem Punkt hängt die Temperatur (T) von den Temperaturen benachbarter Punkte ab. Bei der Verwendung eines parallelen Rechenmodells ist es wichtig, diese Werte mit benachbarten Punkten zu kommunizieren, die auf separaten Prozessoren gespeichert werden könnten. Diese Probleme sind in zeitgenössischen Szenarien weiterhin allgegenwärtig.

Glücklicherweise hat der kollektive Einfallsreichtum von Computerexperten zahlreiche numerische Methoden und Programmiertechniken hervorgebracht, die darauf zugeschnitten sind, diese komplizierten Herausforderungen direkt anzugehen.

Amdahls Gesetz: Maximale Beschleunigung

In seiner ursprünglichen Arbeit beschäftigte sich Amdahls Formulierung nicht mit mathematischen Gleichungen; Erst in nachfolgenden Analysen wurde die maximale Beschleunigung quantifiziert.

Amdahls Gesetz basiert auf der Annahme, dass ein Bruchteil f der Ausführungszeit eines seriellen Programms idealerweise ohne Kommunikations- oder Synchronisierungsaufwand parallelisierbar ist. Der komplementäre Teil, dargestellt als s = 1 − f, ist vollständig sequentiell.

Wenn also T die Ausführungszeit des sequentiellen Programms ist, ist die Ausführungszeit auf p Kernen, T(p), gegeben durch:

Speedup , das Verhältnis der sequentiellen Ausführungszeit zur parallelen Ausführungszeit, ergibt:

Somit kann die Obergrenze der Beschleunigung wie folgt definiert werden:

Vorbehalte

Trotz seiner Einfachheit ist das Gesetz von Amdahl nicht ohne Einschränkungen. Das Modell übersieht kritische Hardware-Engpässe wie Speicherbandbreite, Latenz und I/O-Einschränkungen. Außerdem werden die Leistungsnachteile der Thread-Erstellung, der Synchronisierung, des Kommunikationsaufwands und anderer realer Faktoren nicht berücksichtigt. Bedauerlicherweise wirken sich diese unberücksichtigten Faktoren in der Regel nachteilig auf die tatsächliche Leistung aus.

Die folgende Abbildung veranschaulicht die Auswirkung der Parallelisierung auf die Beschleunigung, wie sie durch das Amdahl-Gesetz bestimmt wird. Es ist klar, dass selbst bei einem erheblichen Parallelanteil von 95 % und einer großen Auswahl an Prozessoren die maximal erreichbare Geschwindigkeitssteigerung bei etwa dem 20-fachen liegt. Wenn man den Parallelisierungsprozentsatz auf 99 % erhöht und unendlich viele Prozessoren einsetzt, kann man eine beeindruckendere Geschwindigkeitssteigerung um das Hundertfache erzielen, was vielversprechend ist.

Es ist jedoch wichtig zu erkennen, dass so viele Prozessoren eine Seltenheit sind . Wir arbeiten oft mit einer viel bescheideneren Zahl, beispielsweise 64 oder noch weniger.

Wenn wir das Amdahlsche Gesetz auf ein Programm anwenden, das 64 Prozessoren nutzt (wobei f 95 % beträgt), liegt die maximale Beschleunigung bei etwa 15,42x. Zugegebenermaßen ist dieser Wert nicht sehr vielversprechend!

Diese Einsicht wird durch die in diesem Ausdruck verwendete Grenze etwas verdeckt:

Diese Grenze verschleiert tendenziell die Tatsache, dass die Beschleunigungswerte deutlich niedriger ausfallen, wenn man die praktische, reale Anzahl von Prozessoren berücksichtigt.

Der größte Nachteil des Gesetzes von Amdahl liegt jedoch in der Annahme, dass die Problemgröße konstant bleibt, wenn mehr Kerne zur Ausführung einer Anwendung verwendet werden.

Im Wesentlichen wird davon ausgegangen, dass der parallelisierbare Anteil unabhängig von der Anzahl der verwendeten Kerne unverändert bleibt. Diese Einschränkung wurde von John L. Gustafson eingehend thematisiert und erweitert, der eine modifizierte Perspektive vorschlug, die heute als Gustafsons Gesetz bekannt ist. Trotz dieser anerkannten Probleme und Vorbehalte ist es jedoch wichtig zu erkennen, dass das Gesetz von Amdahl seine eigenen Vorzüge hat und wertvolle Einblicke in die Komplexität der Parallelisierung bietet. Das Gesetz von Amdahl findet Anwendung in Form starker Skalierungstests , ein Thema, auf das wir später noch eingehen werden.

Gustafsons Gesetz: Hintergrund

Während der Arbeit an den massiv parallelen Computersystemen in den Sandia National Laboratories erzielten Dr. John L. Gustafson und sein Team beeindruckende Beschleunigungsfaktoren für drei verschiedene Anwendungen auf einem Hypercube mit 1024 Prozessoren. Der Anteil des Seriencodes entsprach 0,4–0,8 %.

„…wir haben auf einem 1024-Prozessor-Hyperwürfel Beschleunigungsfaktoren erreicht, die unserer Meinung nach beispiellos sind: 1021 für die Strahlspannungsanalyse mit konjugierten Gradienten, 1020 für die Simulation von verblüfften Oberflächenwellen mit expliziten finiten Differenzen und 1016 für instabile Flüssigkeitsströmungen mit Flusskorrektur.“ Transport." — Dr. John L. Gustafson [2]

Wir haben im letzten Abschnitt deutlich gesehen, dass nach dem Amdahlschen Gesetz die maximal erreichbare Geschwindigkeitssteigerung für eine große Anzahl von Prozessoren 1/s beträgt. Wie kann also diese verblüffende Beschleunigung um das 1021-fache erreicht werden?

Gustafson [2] betonte, dass dem mathematischen Ausdruck eine subtile Annahme zugrunde liegt, die impliziert, dass die Variable f nichts mit p zu tun hat. Dieses Szenario entspricht jedoch selten der Realität, der wir begegnen. In realen Szenarien nehmen wir normalerweise kein Problem fester Größe und führen es auf einer unterschiedlichen Anzahl von Prozessoren aus, außer vielleicht in der kontrollierten Umgebung der akademischen Forschung. Stattdessen wächst in praktischen Anwendungen die Problemgröße tendenziell parallel zur Anzahl der Prozessoren.

Wenn leistungsstärkere Prozessoren verfügbar werden, passen sich Benutzer an, indem sie die Komplexität des Problems erweitern, um die erweiterten Funktionen voll auszunutzen. Sie können Aspekte wie die Rasterauflösung, die Anzahl der Zeitschritte, die Komplexität des Differenzoperators und andere Parameter feinabstimmen, um sicherzustellen, dass das Programm in einem gewünschten Zeitrahmen ausgeführt werden kann.

Laut Gustafson ist es oft realistischer anzunehmen, dass in der Praxis die Laufzeit relativ konstant bleibt und nicht die Problemgröße.

Gustafson bemerkte, dass der Parallel- oder Vektoranteil eines Programms proportional zur Problemgröße wächst. Elemente wie Vektorstart, Programmladen, serielle Engpässe und E/A-Vorgänge, die zusammen zur s- Komponente der Programmlaufzeit beitragen, bleiben normalerweise relativ konstant und weisen kein signifikantes Wachstum mit der Problemgröße auf.

Gustafson führte das Argument weiter und betonte, dass in Szenarien, in denen wir die Freiheitsgrade in einer physikalischen Simulation verdoppeln, oft eine entsprechende Verdoppelung der Prozessoranzahl unerlässlich ist. Einer vorläufigen Schätzung zufolge wächst das Arbeitsvolumen, das effektiv parallel verteilt werden kann, tendenziell linear mit der Anzahl der Prozessoren.

Bei ihrer eingehenden Untersuchung der drei genannten Anwendungen stellten Gustafson und seine Kollegen fest, dass die Parallelkomponente Skalierungsfaktoren von etwa 1023,9969, 1023,9965 und 1023,9965 aufwies.

Gustafsons Gesetz: Skalierte Beschleunigung

Gustafsons Annahme liegt darin, die normalisierte Laufzeit auf p Kernen zu berücksichtigen, die sich zu (1 − f) + f summiert, was zu einem Gesamtwert von 1 führt. Nach dieser Logik bezeichnet if (1 − f) + f die Laufzeit auf p Kernen , dann kann die Laufzeit auf einem einzelnen Kern ausgedrückt werden als (1 − f) + p*f . Folglich kann die Beschleunigung, die Gustafson als „ skalierte Beschleunigung “ bezeichnet, wie folgt berechnet werden:

Wenn wir das Gustafson-Gesetz auf ein Programm anwenden, das 64 Prozessoren verwendet (wobei f 95 % beträgt), beträgt die vorhergesagte Beschleunigung das 60,85-fache (im Vergleich zu 15,42-fach beim Amdahl-Gesetz). Jetzt reden wir😉

Die folgenden Abbildungen verdeutlichen die Unterschiede zwischen den beiden Gesetzen.

Vorbehalte

Die Perspektiven von Amdahl und Gustafson bieten unterschiedliche Ansichten zur Parallelisierung, jede mit ihren eigenen Annahmen.

Das Gesetz von Amdahl geht davon aus, dass die Menge an Arbeit, die parallelisiert werden kann, konstant und unabhängig von der Anzahl der Prozessoren ist, was es sehr pessimistisch macht. Gustafsons Sichtweise, die davon ausgeht, dass die Menge an Arbeit, die parallelisiert werden kann, linear mit der Anzahl der Kerne wächst, ist zweifellos für viele Szenarien praktikabel. Es kann jedoch manchmal zu optimistisch sein.

In realen Anwendungen stoßen sie häufig auf Einschränkungen, die diese lineare Skalierbarkeit einschränken können. Wenn beispielsweise die Anzahl der Kerne zunimmt, kann es aufgrund der Komplexität der Parallelverarbeitung, der Datenabhängigkeiten und des Kommunikationsaufwands zu sinkenden Erträgen kommen. Darüber hinaus beschränken Hardware-Einschränkungen praktisch die Anzahl der Kerne, die effektiv in einen einzelnen Chip integriert werden können. Gustafsons Gesetz berücksichtigt diese komplizierten Herausforderungen der realen Welt möglicherweise nicht immer, weshalb es notwendig ist, die Vorbehalte zu berücksichtigen, die seine Anwendbarkeit beeinträchtigen.

Die Wirksamkeit des Gustafsonschen Gesetzes kann auch von der Art der Anwendung selbst abhängen. Während sich einige Anwendungen natürlich für eine lineare Skalierbarkeit mit zunehmender Kernanzahl eignen, kann es bei anderen aufgrund inhärenter Einschränkungen oder der Art des Problems viel früher zu einem Plateau kommen. Bei der Prüfung der Machbarkeit linearer Skalierbarkeit in praktischen Anwendungen müssen die Komplexität der Programmierung und das Potenzial sinkender Erträge berücksichtigt werden.

Im Wesentlichen bietet das Gesetz von Gustafson zwar einen optimistischeren Ausblick auf die Parallelisierung, muss jedoch mit einem tiefen Verständnis der Anwendung, der Hardwarebeschränkungen und der Feinheiten der parallelen Programmierung angewendet werden, um es an die realen Komplexitäten moderner Computer anzupassen.

Starke Skalierung vs. schwache Skalierung

Im Kern bezieht sich Skalierbarkeit auf die Fähigkeit eines Systems oder einer Anwendung, mit zunehmender Größe steigende Arbeitslasten effizient zu bewältigen.

In der Datenverarbeitung, sei es Hardware oder Software, bezeichnet Skalierbarkeit die Fähigkeit, die Rechenleistung durch Erweiterung der verfügbaren Ressourcen zu steigern.

Im Kontext von High-Performance Computing (HPC)-Clustern ist die Erzielung von Skalierbarkeit von entscheidender Bedeutung; es bedeutet die Möglichkeit, die Gesamtkapazität des Systems durch die Integration zusätzlicher Hardwarekomponenten nahtlos zu erweitern. In Bezug auf Software ist Skalierbarkeit oft gleichbedeutend mit Parallelisierungseffizienz , die das Verhältnis zwischen der tatsächlich erzielten Beschleunigung und der idealen Beschleunigung darstellt, die bei Verwendung einer bestimmten Anzahl von Prozessoren erreichbar ist. Diese Metrik bietet Erkenntnisse darüber, wie effektiv Software die Parallelverarbeitung nutzen kann, um die Leistung zu steigern.

Skalierungstests

Im typischen Entwicklungsprozess großer Anwendungen ist es oft unpraktisch, von Anfang an mit dem Testen mit der vollen Problemgröße und der maximalen Prozessoranzahl zu beginnen. Dieser Ansatz bringt längere Wartezeiten und eine übermäßige Ressourcenauslastung mit sich. Daher besteht eine pragmatischere Strategie darin, diese Faktoren zunächst herunterzuskalieren, was die Testphase beschleunigt und eine genauere Schätzung der für den endgültigen Gesamtlauf benötigten Ressourcen ermöglicht, was die Ressourcenplanung unterstützt.

Skalierbarkeitstests dienen dazu, zu bewerten, wie gut sich eine Anwendung an unterschiedliche Problemgrößen und unterschiedliche Prozessorzahlen anpassen kann, um eine optimale Leistung sicherzustellen.

Es ist wichtig zu beachten, dass Skalierbarkeitstests nicht die Gesamtfunktionalität oder Korrektheit der Anwendung prüfen; Sein Hauptaugenmerk liegt auf Leistung und Effizienz, wenn die Rechenressourcen angepasst werden.

Zwei Standard-Skalierungstests, stark und schwach , werden häufig beim parallelen Rechnen eingesetzt.

Starke Skalierung

Bei einer starken Skalierung wird die Anzahl der Prozessoren erhöht und gleichzeitig die Problemgröße konstant gehalten. Dieser Ansatz reduziert die Arbeitslast pro Prozessor, was besonders bei CPU-intensiven Anwendungen mit langer Laufzeit von Vorteil ist. Das Hauptziel einer starken Skalierung besteht darin, eine Konfiguration zu identifizieren, die angemessene Ausführungszeiten liefert und gleichzeitig die Ressourcenkosten in einem überschaubaren Bereich hält.

Im Amdahlschen Gesetz ist eine starke Skalierung verankert, wobei die Problemgröße konstant bleibt, während die Anzahl der Verarbeitungselemente erhöht wird. Diese Methode ist häufig für Programme mit erheblicher CPU-gebundener Arbeitslast gerechtfertigt.

Das ultimative Ziel der starken Skalierung besteht darin, den optimalen „Sweet Spot“ zu finden, der es ermöglicht, Berechnungen innerhalb eines angemessenen Zeitrahmens abzuschließen und gleichzeitig die Verschwendung von Verarbeitungszyklen aufgrund des parallelen Overheads zu minimieren.

Bei der starken Skalierung wird davon ausgegangen, dass ein Programm linear skaliert, wenn die Beschleunigung, ausgedrückt in den pro Zeiteinheit abgeschlossenen Arbeitseinheiten, mit der Anzahl der verwendeten Verarbeitungselemente (N) übereinstimmt. Ebenso kann die Beschleunigung sublinear oder sogar superlinear sein, je nachdem, wie sie mit der Anzahl der Prozessoren skaliert.

Schließlich habe ich versucht, die starken Skalierungstests für einen meiner Codes durchzuführen. Fluidchen-EM ist ein Computational Fluid Dynamics Solver, der viele Probleme der Fluiddynamik lösen kann. Die folgenden Ergebnisse entsprechen der Simulation der deckelgesteuerten Kavität . Die Geschwindigkeit zum letzten Zeitstempel (nach der Konvergenz) wird visualisiert und die Ausführungslaufzeit berechnet. Fluidchen-EM verwendet MPI, um die Rechendomäne auf iproc*jproc- Prozessoren zu verteilen.

Hinweis : Die Ergebnisse wurden auf meinem PC ausgeführt und alle Kerne entsprechen nur einem Prozessor. Die Ergebnisse können variieren, wenn die Simulation auf einer größeren und besseren Maschine ausgeführt wird!

Der Rechenbereich ist in insgesamt imax*jmax- Gitterpunkte unterteilt.

iproc: Anzahl der Prozessoren in x-Richtung

jproc: Anzahl der Prozessoren in y-Richtung

Wie in der Abbildung gezeigt, nimmt die Ausführungszeit stark ab, wenn sich die Anzahl der Prozessoren von 1 auf 2 verdoppelt. Bei der nächsten Verdoppelung der Prozessoren von 2 auf 4 ist die Beschleunigung jedoch nicht so dramatisch und beginnt bei weiteren Steigerungen sogar die Sättigung zu erreichen in der Anzahl der Prozessoren. Allerdings wurden die Ergebnisse auf einem Prozessor mit acht Kernen zusammengestellt, sodass sich diese Ergebnisse ändern können, wenn die Ausführung auf einer größeren und leistungsstärkeren Maschine erfolgt.

Schwache Skalierung

Bei einer schwachen Skalierung nehmen die Anzahl der Prozessoren und die Problemgröße zu, sodass die Arbeitslast pro Prozessor konstant bleibt. Eine schwache Skalierung steht im Einklang mit dem Gustafson-Gesetz, bei dem die skalierte Beschleunigung basierend auf der Arbeitsbelastung einer skalierten Problemgröße berechnet wird, im Gegensatz zum Amdahl-Gesetz, das sich auf eine feste Problemgröße konzentriert.

Die jedem Verarbeitungselement zugewiesene Problemgröße bleibt konstant, sodass zusätzliche Elemente gemeinsam ein größeres Gesamtproblem lösen können, das möglicherweise die Speicherkapazität eines einzelnen Knotens überschreitet.

Eine schwache Skalierung rechtfertigt Anwendungen mit erheblichem Speicher- oder Ressourcenbedarf (speichergebundene Anwendungen), die mehr Speicher benötigen, als ein einzelner Knoten bereitstellen kann. Solche Anwendungen weisen häufig eine effiziente Skalierung auf, da ihre Speicherzugriffsstrategien nahegelegene Knoten priorisieren, wodurch sie sich gut für höhere Kernzahlen eignen.

Bei schwacher Skalierung wird lineare Skalierbarkeit erreicht, wenn die Laufzeit konstant bleibt, da die Arbeitslast direkt proportional zur Anzahl der Prozessoren steigt.

Die meisten Programme, die diesen Modus verwenden, lassen sich günstig auf höhere Kernzahlen skalieren, insbesondere solche, die Kommunikationsmuster für den nächsten Nachbarn verwenden, da ihr Kommunikationsaufwand unabhängig von der Anzahl der verwendeten Prozesse relativ konstant bleibt. Ausnahmen von diesem Trend sind Algorithmen, die stark auf globalen Kommunikationsmustern basieren.

Schließlich habe ich die schwachen Skalierungstests mit Fluidchen-EM durchgeführt. Die folgenden Ergebnisse entsprechen der Simulation der Rayleigh-Bénard-Konvektion . Auch hier wird die Geschwindigkeit zum letzten Zeitstempel (nach der Konvergenz) visualisiert und die Ausführungslaufzeit berechnet. Fluidchen-EM verwendet MPI, um die Rechendomäne auf iproc*jproc- Prozessoren zu verteilen.

Hinweis: Die Ergebnisse wurden auf meinem PC ausgeführt und alle Kerne entsprechen nur einem Prozessor. Die Ergebnisse können variieren, wenn die Simulation auf einer größeren und besseren Maschine ausgeführt wird!

Der Rechenbereich ist in insgesamt imax*jmax- Gitterpunkte unterteilt.

iproc: Anzahl der Prozessoren in x-Richtung

jproc: Anzahl der Prozessoren in y-Richtung

imax: Anzahl der Gitterpunkte entlang der Länge des Kanals

jmax: Anzahl der Gitterpunkte entlang der Höhe des Kanals

xlength: Länge des Kanals

ylength: Höhe des Kanals

Wie in der Abbildung oben dargestellt, nimmt die Ausführungslaufzeit mit zunehmender Problemgröße und Anzahl der Prozessoren zu. Dieses Verhalten kann auf mehrere Faktoren zurückgeführt werden. Da sich alle Kerne auf einem einzigen Prozessor befinden und die Problemgröße zunimmt und mehr Prozessoren eingesetzt werden, wird ein Teil der Verarbeitungszeit für die Einrichtung der MPI-Kommunikation (Message Passing Interface) verbraucht. Darüber hinaus erfordert die größere Problemgröße einen verstärkten Datenaustausch zwischen den Kernen, wodurch sich die Kommunikationslatenz aufgrund der begrenzten Bandbreite des Kommunikationsnetzwerks erhöht.

Somit liefern diese Testergebnisse entscheidende Erkenntnisse zur Parallelisierung des Problems.

Abschluss

Die Wahl zwischen Gustafsons Gesetz und Amdahls Gesetz bei der Algorithmusparallelisierung hängt von der Anpassungsfähigkeit der Rechenarbeitslast ab. Das Gustafsonsche Gesetz ist geeignet, wenn ein Algorithmus den Rechenaufwand dynamisch an die verfügbare Parallelisierung anpassen kann. Im Gegensatz dazu ist das Amdahlsche Gesetz passender, wenn die Rechenlast fest ist und durch Parallelisierung nicht wesentlich verändert werden kann. In realen Szenarien erfordert die Anpassung eines Algorithmus für die Parallelisierung häufig eine gewisse Änderung der Berechnungen, und beide Gesetze dienen als wertvolle Benchmarks und bieten Ober- und Untergrenzen für die vorhergesagte Geschwindigkeitssteigerung. Die Wahl zwischen ihnen hängt vom Ausmaß der rechnerischen Änderungen ab, die während der Parallelisierung eingeführt werden, und ermöglicht so eine umfassende Bewertung potenzieller Beschleunigungsgewinne.

Vorgeschlagene Literatur

[1] Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities, nachgedruckt aus den AFIPS Conference Proceedings, Bd. 30 (Atlantic City, NJ, 18.–20. April), AFIPS Press, Reston, Virginia, 1967, S. 483–485, als Dr. Amdahl bei International Business Machines Corporation, Sunnyvale, Kalifornien, arbeitete | IEEE-Zeitschriften und -Magazine | IEEE Xplore

[2] Neubewertung des Amdahlschen Gesetzes | Mitteilungen der ACM

[3] Durganshu/Fluidchen-EM

[4] Amdahls Gesetz zur Vorhersage der Zukunft von Multicores, die als schädlich gelten (tu-berlin.de)

[5] Skalierung – HPC Wiki (hpc-wiki.info)

[6] Amdahl vs. Gustavson von r1parks – Infogram

Ausgewähltes Foto von Marc Sendra Martorell auf Unsplash