Scalability of the asynchronous discontinuous Galerkin method for compressible flow simulations

Diese Studie implementiert und bewertet die skalierbare asynchrone Diskontinuierliche-Galerkin-Methode mit asynchron-toleranten Flüssen in der Bibliothek deal.II für kompressible Strömungen und zeigt, dass durch die Kombination mit einem kommunikationsvermeidenden Algorithmus Synchronisationskosten signifikant reduziert und bis zu 1,9-fache Geschwindigkeitssteigerungen bei Wahrung der hohen numerischen Genauigkeit erreicht werden können.

Das Wesentliche

Das große Problem: Der Stau im Datenverkehr

Stellen Sie sich vor, Sie haben ein riesiges Puzzle, das von Tausenden von Menschen gleichzeitig gelöst werden soll. Jeder Mensch ist für ein kleines Stück des Puzzles zuständig. Damit das Bild am Ende stimmt, müssen die Nachbarn ständig miteinander reden und sich ihre Teile zeigen.

In der Welt der Supercomputer nennt man diese Menschen Prozessoren und das Puzzle eine Simulation von Strömungen (z. B. wie Luft um ein Flugzeug strömt).

Das Problem ist: Je mehr Menschen (Prozessoren) Sie hinzufügen, desto mehr müssen sie sich unterhalten. Bald verbringen die Menschen mehr Zeit damit, auf die Antworten ihrer Nachbarn zu warten, als tatsächlich das Puzzle zu legen. In der Fachsprache nennt man das Synchronisations-Overhead. Der Computer steht quasi im Stau, weil alle aufeinander warten müssen, bevor sie den nächsten Schritt machen können.

Die Lösung: Asynchrones Rechnen (Das "Nachrichten-Prinzip")

Die Autoren dieser Studie haben einen cleveren Trick ausprobiert: Asynchrones Rechnen.

Stellen Sie sich vor, statt sich sofort zu unterhalten, schickt jeder Mensch eine Nachricht an seine Nachbarn und macht einfach weiter, auch wenn die Antwort noch nicht da ist. Er nutzt die letzte bekannte Information von seinem Nachbarn, um seinen eigenen Teil des Puzzles weiterzubauen.

• Der alte Weg (Synchron): Alle warten, bis alle Nachrichten da sind. Dann machen alle einen Schritt. (Langsam bei vielen Teilnehmern).
• Der neue Weg (Asynchron): Jeder macht weiter, solange er kann. Wenn die Nachricht des Nachbarn später kommt, nutzt er sie für den nächsten Schritt. (Schneller, aber riskant).

Das Risiko: Warum das Bild unscharf wird

Hier kommt das große "Aber". Wenn Sie einfach alte Nachrichten von Ihren Nachbarn nutzen, wird das Endergebnis oft ungenau. Es ist, als würden Sie versuchen, ein hochauflösendes Foto zu entwickeln, aber nur mit alten, verpixelten Vorlagen arbeiten.

Die Forscher haben gezeigt: Wenn man diese "Asynchronität" einfach so anwendet, verliert der Computer-Algorithmus seine Schärfe. Aus einer hochpräzisen Berechnung wird eine grobe, ungenaue Schätzung (nur noch "erste Ordnung" genau).

Der Clou: Die "Zeitmaschinen"-Formel (AT-Flüsse)

Um das Problem zu lösen, haben die Autoren eine spezielle mathematische Formel entwickelt, die sie AT-Flüsse (Asynchrony-Tolerant, also "asynchronie-tolerante Flüsse") nennen.

Stellen Sie sich diese Formel wie eine Zeitmaschine vor. Anstatt nur die eine alte Nachricht des Nachbarn zu nehmen, schaut sich der Computer die letzten mehreren Nachrichten an, die er in der Vergangenheit erhalten hat. Er kombiniert diese alten Daten clever, um eine neue, sehr genaue Vorhersage zu treffen, als hätte er die aktuelle Nachricht schon erhalten.

• Analogie: Ein Koch, der ein Rezept kocht, aber keine frischen Zutaten hat. Statt das Essen zu verderben, nutzt er eine spezielle Technik, um aus den letzten drei Einkaufslisten (die er noch hat) genau zu berechnen, wie die frischen Zutaten geschmeckt hätten. Das Ergebnis schmeckt fast genauso gut wie mit frischen Zutaten.

Was haben sie herausgefunden?

Die Forscher haben diesen neuen Algorithmus in einer großen Software-Bibliothek (deal.II) eingebaut und getestet:

1. Genauigkeit: Mit ihrer neuen "Zeitmaschinen-Formel" (AT-Flüsse) ist das Ergebnis genauso präzise wie beim alten, langsamen Weg. Ohne diese Formel war das Ergebnis schlecht.
2. Geschwindigkeit: Da die Computer nicht mehr ständig warten müssen, laufen die Simulationen viel schneller.
   • Bei 2D-Simulationen (wie eine Landkarte) wurden sie bis zu 1,9-mal schneller.
   • Bei 3D-Simulationen (wie ein ganzer Raum) wurden sie bis zu 1,6-mal schneller.
3. Zukunft: Das ist besonders wichtig für die kommenden "Exascale"-Supercomputer (die größten der Welt), die so viele Rechner haben, dass der alte Weg gar nicht mehr funktionieren würde.

Fazit

Die Studie zeigt, dass man Supercomputer effizienter nutzen kann, indem man sie nicht ständig aufeinander warten lässt. Durch einen cleveren mathematischen Trick (die Kombination aus verzögerten Daten und einer speziellen Korrekturformel) können wir komplexe Strömungen schneller und trotzdem genau berechnen. Es ist, als hätte man den Stau auf der Autobahn aufgelöst, indem man den Autofahrern erlaubt hat, weiterzufahren, solange sie ihre Route intelligent anpassen.

Technische Zusammenfassung

1. Problemstellung

Die Skalierbarkeit von zeitabhängigen partiellen Differentialgleichungs-Lösern (PDE), die auf der Diskontinuierlichen Galerkin-Methode (DG) basieren, wird auf extrem großen Rechenanlagen (Exascale-Systeme) zunehmend durch Kommunikations- und Synchronisationskosten zwischen den Verarbeitungselementen (PEs) begrenzt.

• Herausforderung: In parallelen DG-Implementierungen erfordern die numerischen Flüsse an den Grenzen der Subdomänen häufige Datenaustausche (Ghost-Value-Exchange). Mit steigender Prozessanzahl wächst das Verhältnis von Oberfläche zu Volumen der Subdomänen, wodurch Kommunikations- und Synchronisations-Overheads die Laufzeit dominieren.
• Limitierung bestehender Ansätze: Selbst optimierte Synchronisationsstrategien (z. B. nicht-blockierende Kommunikation mit Überlappung von Berechnung und Kommunikation) stoßen bei extremen Prozesszahlen an Grenzen, da Synchronisationspunkte die Skalierung bremsen.
• Ziel: Entwicklung einer Methode, die die mathematischen Anforderungen an die Kommunikation und Synchronisation lockert, ohne die Genauigkeit der Lösung zu beeinträchtigen.

2. Methodik

Die Autoren implementierten und untersuchten die asynchrone Diskontinuierliche Galerkin-Methode (ADG) mit asynchronie-toleranten (AT) Flüssen in der Open-Source-Finite-Elemente-Bibliothek deal.II.

• Asynchrone Berechnung (CAA): Es wird ein Communication-Avoiding Algorithmus (CAA) verwendet. Anstatt bei jedem Zeitschritt oder jeder Runge-Kutta-Stufe zu kommunizieren, wird die Kommunikation nur in festgelegten Intervallen durchgeführt. In den dazwischenliegenden Schritten verwendet der Löser verzögerte Daten (Ghost-Werte aus früheren Zeitstufen).
• Das Genauigkeitsproblem: Die Studie zeigt, dass die einfache Anwendung standardmäßiger numerischer Flüsse in diesem asynchronen Setting die Konvergenzordnung unabhängig vom Polynomgrad $N_p$ auf erste Ordnung degradiert.
• Lösung durch AT-Flüsse: Um die hohe Ordnung der DG-Diskretisierung wiederherzustellen, werden asynchronie-tolerante (AT) Flüsse eingeführt. Diese rekonstruieren den aktuellen Fluss an den Prozessgrenzen durch eine lineare Kombination von Flüssen aus mehreren vorherigen Zeitstufen ($N_p + 1$ Zeitstufen). Dies kompensiert die Verzögerung der Daten und erhält die formale Genauigkeit ($O(h^{N_p+1})$).
• Implementierung:
  • Basierend auf dem matrixfreien DG-Löser (Schritt-76) in deal.II.
  • Verwendung von Low-Storage-Expliziten Runge-Kutta-Verfahren (LSERK) für die Zeitintegration.
  • Die AT-Flüsse nutzen einen Rolling-Buffer, um die Historie der Flüsse zu speichern.
  • Das Synchronisationsmuster wird so gesteuert, dass für $N_p + 1$ Schritte kommuniziert wird, um die Historie zu füllen, gefolgt von $L$ Schritten ohne Kommunikation (Verzögerung $L$).

3. Wichtige Beiträge

1. Implementierung: Erste vollständige Implementierung des ADG-Verfahrens mit AT-Flüssen in einem modernen, skalierbaren DG-Löser (deal.II) für kompressible Strömungen.
2. Nachweis der Genauigkeitsdegradation: Demonstration, dass Standard-Flüsse in asynchronen DG-Schemata die Genauigkeit auf erste Ordnung reduzieren, unabhängig vom Polynomgrad.
3. Wiederherstellung der Genauigkeit: Erfolgreicher Nachweis, dass AT-Flüsse die formale hohe Ordnung (zweite und dritte Ordnung) wiederherstellen, selbst bei signifikanten Kommunikationsverzögerungen.
4. Umfassende Skalierungsstudie: Durchführung detaillierter Strong-Scaling-Studien für 2D- und 3D-Fälle (Euler-Gleichungen) auf einem Supercomputer (PARAM Pravega, IISc) mit bis zu 20.400 Prozessen.

4. Ergebnisse

Die numerischen Experimente basierten auf zwei Testfällen: einem 2D-isentropischen Wirbel und einer 3D-Strömung um einen Zylinder.

• Genauigkeit:
  • Synchron (SA): Erreicht die erwartete Konvergenzordnung ($O(h^{N_p+1})$).
  • ADG mit Standard-Flüssen: Zeigt nur erste Konvergenzordnung, was zu signifikanten Fehlern in Schockstrukturen und Gradienten führt.
  • ADG mit AT-Flüssen: Erreicht exakt die gleiche Konvergenzordnung und Fehlerverteilung wie der synchrone Löser. Die visuellen Unterschiede in Druck- und Dichtefeldern sind vernachlässigbar.
• Performance und Skalierung:
  • Synchroner Löser: Die Laufzeit wird bei hohen Prozesszahlen schnell durch die Synchronisationszeit (Warten auf Ghost-Werte) dominiert. Die parallele Effizienz bricht stark ein (z. B. auf 0,13 bei 20.400 Kernen im 3D-Fall).
  • Asynchroner Löser (CAA-AT): Reduziert die Synchronisations-Overheads drastisch.
    • Beschleunigung (Speedup): Im Vergleich zum synchronen Löser wurden Speedups von bis zu 1,9-fach (2D) und 1,6-fach (3D) erreicht.
    • Parallele Effizienz: Der asynchrone Löser behält bei extremen Prozesszahlen eine deutlich höhere parallele Effizienz bei (z. B. 0,53 vs. 0,13 im 3D-Fall bei 20.400 Kernen).
  • Einfluss der Verzögerung $L$: Größere Verzögerungen (weniger häufige Kommunikation) führen zu höheren Speedups, da der Kommunikations-Overhead weiter reduziert wird.

5. Bedeutung und Fazit

Das Paper beweist, dass asynchrone Rechenansätze in DG-Lösern nicht nur theoretisch, sondern auch in der Praxis für hochauflösende, kompressible Strömungssimulationen auf Exascale-Systemen geeignet sind.

• Schlüsselerkenntnis: Die Kombination aus Kommunikationsvermeidung (CAA) und mathematisch korrekter Rekonstruktion der Flüsse (AT-Flüsse) ist entscheidend. Ohne AT-Flüsse ist die Methode ungenau; ohne CAA ist sie nicht skalierbar.
• Stabilität: Asynchrone Schemata haben strengere CFL-Stabilitätsgrenzen als synchrone. Die Verwendung von AT-Flüssen mildert dies teilweise ab, erfordert aber dennoch konservative Zeitschritte. Für Probleme mit steifen Quelltermen (z. B. chemische Reaktionen), wo der Zeitschritt ohnehin durch die Chemie limitiert ist, ist dieser Nachteil jedoch irrelevant.
• Zukunftsperspektive: Die Methode bietet einen vielversprechenden Weg, um die Skalierbarkeit von DG-Lösern auf zukünftigen Exascale-Systemen zu erhalten, wo Kommunikationskosten der Hauptengpass sein werden. Zukünftige Arbeiten könnten adaptive Verzögerungsparameter und Anwendungen auf komplexere physikalische Modelle (Viskosität, Mehrphysik) untersuchen.

Zusammenfassend stellt dieser Ansatz einen bedeutenden Schritt hin zu effizienten, hochgenauen DG-Lösern für die nächste Generation von Hochleistungsrechnern dar.