Exploiting repeated matrix block structures for more efficient CFD on modern supercomputers

Dieser Beitrag stellt eine neuartige CFD-Methodik vor, die die Leistung auf modernen Supercomputern verbessert, indem sie sparse Matrix-Vektor-Operationen in Matrix-Matrix-Produkte umwandelt, um die arithmetische Intensität zu erhöhen, und durch den Einsatz einer Inline-Mesh-Verfeinerungsstrategie die Konvergenz beschleunigt, wodurch insgesamt erhebliche Geschwindigkeitssteigerungen bei der Simulation turbulenter Strömungen erzielt werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, ein riesiges, komplexes Puzzle (eine Simulation, wie Luft oder Wasser strömt) auf einem Supercomputer zu lösen. Der Computer ist unglaublich schnell, bleibt aber ständig stecken, weil er auf das Eintreffen der Puzzleteile wartet.

Dies ist das Kernproblem, das der Artikel adressiert: Moderne Supercomputer sind so schnell beim Berechnen, dass sie oft untätig dastehen und darauf warten, dass Daten aus dem Speicher geholt werden. Es ist wie ein Formel-1-Rennfahrer, der bereit ist zu starten, aber das Boxenpersonal zu langsam ist, um ihm die Reifen zu geben. Der Fahrer verbringt mehr Zeit mit Warten als mit Fahren.

Hier ist, wie die Autoren dies behoben haben, erklärt durch einfache Analogien:

1. Das Problem des "Wartezimmers" (Speicher vs. Rechenleistung)

In diesen Simulationen führt der Computer eine bestimmte Aufgabe immer wieder aus: Er nimmt eine riesige, größtenteils leere Liste von Zahlen (eine "sparse matrix" oder dünnbesetzte Matrix) und multipliziert sie mit einer Liste von Werten (einem "Vector" oder Vektor).

• Der alte Weg (SpMV): Stellen Sie sich vor, der Computer muss zu einer Bibliothek laufen, ein Buch holen, eine Seite lesen, zu seinem Schreibtisch zurücklaufen, etwas rechnen und dann wiederholen. Er verbringt die meiste Zeit mit dem Laufen (Datenbewegung), nicht mit dem Lesen oder Rechnen. Dies wird als "speichergebunden" (memory-bound) bezeichnet.
• Der Engpass: Das "Gehirn" des Computers (Prozessor) ist schnell, aber der "Flur" (Speicherbandbreite) ist schmal. Er kann nicht schnell genug Daten beschaffen, um das Gehirn beschäftigt zu halten.

2. Die Lösung "Gruppenausflug" (SpMM)

Die erste große Idee der Autoren ist es, den Computer nicht mehr auf Solo-Trips zu schicken, sondern ihn auf Gruppenausflüge zu schicken.

• Die Analogie: Anstatt den Computer zu schicken, um ein Buch für eine Berechnung zu holen, organisieren sie mehrere Berechnungen gleichzeitig. Sie bündeln 4, 8 oder sogar 16 verschiedene "Was-wäre-wenn"-Szenarien zusammen.
• Wie es funktioniert: Der Computer läuft einmal zur Bibliothek, holt einen Stapel Bücher (die Matrix-Daten) und setzt sich dann hin, um alle 16 Bücher gleichzeitig zu lesen.
• Das Ergebnis: Die "Laufzeit" (Datenübertragung) bleibt gleich, aber die "Lese- und Rechenzeit" (Berechnung) steigt massiv an. Der Computer ist nun beschäftigt mit der Arbeit statt mit dem Warten. In dem Artikel wird dies als Umwandlung eines Sparse Matrix-Vector-Produkts in ein Sparse Matrix-Matrix-Produkt bezeichnet.
• Der Gewinn: Dies lässt die Simulation bis zu 50 % schneller laufen, ohne dass neue Hardware gekauft werden muss. Es ist wie ein kostenloses Tempoboot, das man nur durch bessere Organisation der Arbeit erhält.

3. Die Strategie "Fahrradstabilisatoren" (Gitterverfeinerung)

Die zweite große Idee betrifft den Start der Simulation. Normalerweise muss man, um einen Fluss (wie Wind um einen Flügel) in einen stationären Zustand übergehen zu lassen, die Simulation für eine lange Zeit auf einer sehr detaillierten, hochwertigen Karte (einem "feinen Gitter") laufen lassen. Das dauert lange.

• Die Analogie: Stellen Sie sich vor, Sie versuchen, Fahrrad auf einem schwierigen, felsigen Bergpfad zu lernen. Sie könnten Stunden damit verbringen, nur das Gleichgewicht zu halten und sich auf den Felsen in Bewegung zu setzen, bevor Sie überhaupt Ihre echte Fahrt beginnen.
• Die neue Strategie: Die Autoren schlagen vor, zuerst auf einem glatten, flachen, leichten Weg (einem "grobmaschigen Gitter") zu beginnen. Sie bringen das Fahrrad schnell in Bewegung und ins Gleichgewicht. Sobald Sie reibungslos rollen, wechseln Sie auf den felsigen Bergpfad (das "feine Gitter") und fahren von dort weiter.
• Das Ergebnis: Sie überspringen die langsame, frustrierende "Anfangsphase" auf dem schwierigen Gelände. Der Artikel zeigt, dass dies erhebliche "Wall-Clock-Zeit" (echte Zeit) spart, weil der Computer auf der leichten Karte größere, schnellere Schritte machen kann, bevor er auf die schwierige wechselt.

4. Realwelt-Tests

Die Autoren testeten diese beiden Tricks in drei verschiedenen Szenarien:

1. Turbulente Kanalströmung: Simulation von Wasser, das durch ein Rohr strömt.
2. Rayleigh-Bénard-Konvektion: Simulation von aufsteigender warmer Luft (wie ein Topf mit kochendem Wasser).
3. Flügelsimulation: Simulation von Luft, die über einen komplexen Flugzeugflügel strömt (der 30P30N-Flügel).

Die Ergebnisse:

• Im Flügel-Test (ein industrieller Realwelt-Fall) beschleunigten sie nicht nur eine Simulation; sie führten mehrere Simulationen des Flügels bei verschiedenen Winkeln gleichzeitig mit der "Gruppenausflug"-Methode durch. Dies ermöglichte ihnen, Leistungskurven viel schneller zu generieren.
• Im Kanalströmungs-Test führte die Kombination der "Gruppenausflug"-Methode mit der "Fahrradstabilisatoren"-Strategie (Gitterverfeinerung) zu Geschwindigkeitssteigerungen von über 50 %.
• Sie stellten fest, dass je komplexer die Mathematik war (mit detaillierteren Gittern), desto größer der Geschwindigkeitsschub war, weil der Computer, sobald die Daten ankamen, noch mehr Arbeit zu erledigen hatte.

Zusammenfassung

Der Artikel erfindet keinen neuen Computertyp oder ein neues physikalisches Gesetz. Stattdessen fungiert er wie ein Verkehrsmanager für den Supercomputer:

1. Bündelung: Er verhindert, dass der Computer immer nur eine Reise nach dem anderen macht, und zwingt ihn, eine schwere Ladung Daten für mehrere Berechnungen gleichzeitig zu transportieren.
2. Aufwärmen: Er lässt den Computer eine einfache Version des Problems üben, bevor er die schwierige, detaillierte Version angeht.

Dadurch stellen sie sicher, dass das leistungsstarke Gehirn des Supercomputers tatsächlich Mathematik betreibt, statt nur auf das Eintreffen von Daten zu warten. Dies lässt teure Simulationen viel schneller abschließen und spart Zeit und Energie.

Technische Zusammenfassung

1. Problemstellung

Computational Fluid Dynamics (CFD)-Simulationen, insbesondere für inkompressible Navier-Stokes-Gleichungen, werden zunehmend durch die Speicherbandbreite und nicht durch die Rechenleistung begrenzt. Diese Einschränkung ergibt sich daraus, dass die Kernalgebraoperationen (Sparse Matrix-Vector Products, oder SpMV) eine niedrige arithmetische Intensität (das Verhältnis von Gleitkommaoperationen zu übertragenen Daten) aufweisen.

Gemäß dem Roofline-Modell ist die Leistung bei niedriger arithmetischer Intensität „speichergebunden" (memory-bound), was bedeutet, dass das System mehr Zeit damit verbringt, auf Daten aus dem Speicher zu warten, als Berechnungen durchzuführen. Dieser Engpass verhindert, dass moderne High-Performance-Computing (HPC)-Systeme ihre theoretische Spitzenleistung erreichen. Obwohl verschiedene Sparse-Matrix-Formate (z. B. ELLPACK, SELL-C-σ) entwickelt wurden, um SpMV zu optimieren, erhöhen sie die arithmetische Intensität nicht grundlegend genug, um die „Memory Wall" zu überwinden.

2. Methodik

Die Autoren schlagen eine zweigleisige Strategie vor, um CFD-Simulationen durch eine Erhöhung der arithmetischen Intensität von einem speichergebundenen Regime in ein rechenleistungsgebundenes (compute-bound) Regime zu verschieben.

A. Transformation von SpMV zu SpMM (Ausnutzung wiederholter Blockstrukturen)

Anstatt nacheinander einen einzelnen Strömungszustand zu lösen, führt die Methode $m$ gleichzeitige Simulationen durch (entweder mehrere Strömungszustände oder mehrere Parametersätze).

• Mechanismus: Wenn $m$ unabhängige Simulationen dieselbe Geometrie und dieselben Randbedingungen teilen, sind ihre zugrunde liegenden linearen Operatoren (Divergenz, Gradient, Laplace und Poisson-Matrix) identisch.
• Transformation: Die $m$ separaten rechten Seiten (RHS-Vektoren) werden zu einer einzigen dichten Matrix $X \in \mathbb{R}^{n \times m}$ gestapelt. Die Standard-SpMV-Operation ($A \cdot x$) wird durch ein Sparse Matrix-Matrix Product (SpMM) ($A \cdot X$) ersetzt.
• Vorteil: Die Sparse-Matrix $A$ wird nur einmal für alle $m$ RHS-Vektoren aus dem Speicher geladen, während die Anzahl der Gleitkommaoperationen linear mit $m$ zunimmt. Dies erhöht die arithmetische Intensität drastisch und ermöglicht es der Hardware, ihr volles Rechenpotenzial auszuschöpfen.
• Umfang: Im Gegensatz zu früheren Arbeiten, die dies nur auf den Poisson-Gleichungslöser anwendeten, erstreckt diese Methode die SpMM-Transformation auf alle Operatoren in der CFD-Schleife (konvektiv, diffusiv, Gradient, Divergenz und Laplace).

B. Inline-Mesh-Verfeinerungsstrategie

Um die Wandzeit weiter zu reduzieren, führen die Autoren eine Strategie ein, um die Übergangsphase (die Zeit, die eine Strömung benötigt, um einen statistisch stationären Zustand zu erreichen, bevor die Mittelung beginnt) zu beschleunigen.

• Prozess:
  1. Grobe Phase: Die Simulation beginnt auf einem grobmaschigen Gitter, um die Strömung bis zu einem Zeitpunkt $T_D$ schnell zu entwickeln.
  2. Abbildung: Das Strömungsfeld wird vom groben Gitter auf das Ziel-feine Gitter interpoliert.
  3. Feine Phase: Die Simulation wird auf dem feinen Gitter fortgesetzt, bis die Übergangszeit $T_T$ erreicht ist, gefolgt von der Mittelungsphase.
• Begründung: Grobe Gitter ermöglichen größere Zeitschritte und schnellere Iterationen. Durch die Entwicklung der Strömung auf einem groben Gitter wird die gesamte Wandzeit bis zum Erreichen des statistisch stationären Zustands erheblich verkürzt, ohne die Genauigkeit der abschließenden Mittelungsphase zu beeinträchtigen.

3. Hauptbeiträge

1. Verallgemeinerung von SpMM: Erweiterung des SpMM-Ansatzes vom reinen Poisson-Gleichungslöser auf alle Sparse-Operatoren (Gradient, Divergenz, Laplace) im CFD-Algorithmus, um den Leistungsgewinn über die gesamte Simulation hinweg zu maximieren.
2. Inline-Mesh-Verfeinerung: Ein neuartiger Workflow, der Ensemble-Mittelung mit dynamischer Mesh-Verfeinerung kombiniert, um die Zeit, die in der nicht-mittelnden (Übergangs-)Phase verbracht wird, zu minimieren.
3. Theoretische Schranken: Herleitung von oberen und unteren Schranken für die Beschleunigung basierend auf der Anzahl der rechten Seiten ($m$), der Matrix-Sparsity (Nicht-Null-Elemente pro Zeile) und dem Verhältnis von Mittelungszeit zu Übergangszeit ($\beta$).
4. Validierung über Skalen hinweg: Umfassende Tests sowohl auf strukturierten (akademischen) als auch auf unstrukturierten (industriellen) Gittern.

4. Ergebnisse

Die Methodik wurde mit drei Testfällen auf dem MareNostrum 5-Supercomputer validiert:

• Turbulente planare Kanalströmung ($Re_\tau = 180$):

  • SpMM-Kernel: Erzielte Beschleunigungen von 3,0x für SpMM-Operationen im Vergleich zu SpMV.
  • Poisson-Löser: Erzielte Beschleunigungen von bis zu 2,0x.
  • Gesamte Iteration: Erzielte Beschleunigungen von 1,3x bis 1,5x.
  • Vollständige Simulation: Mit Mesh-Verfeinerung erreichte die gesamte Simulationsbeschleunigung ~1,55x (55% Reduktion der Wandzeit) für 4–8 gleichzeitige Strömungszustände, ohne zusätzliche Rechenressourcen.
  • Höherordige Schemata: Tests mit dichteren Matrizen (13 und 27 Nicht-Null-Elemente pro Zeile) zeigten noch höhere potenzielle Beschleunigungen (bis zu 4,1x für Kernel), was auf größere Vorteile für Diskretisierungsmethoden höherer Ordnung hindeutet.

• Rayleigh-Bénard-Konvektion ($Ra = 10^9$):

  • Validierung der Methode mit einer zusätzlichen Transportgleichung (Energie).
  • Die Ergebnisse zeigten, dass die Methode trotz der Verdünnung des SpMM-Einflusses durch die Hinzunahme der Energiegleichung robust bleibt und ähnliche Beschleunigungstrends wie bei der Kanalströmung erzielt.

• Industrieller Fall (30P30N-Profil):

  • Anwendung auf ein unstrukturiertes Gitter mit 14 Millionen Zellen.
  • Demonstrierte, dass die Methode effektiv auf komplexen, industriellen Geometrien funktioniert.
  • Erzielte Iterationsbeschleunigungen von bis zu 80% für mehrere Parametersstudien (z. B. Variation des Anstellwinkels), was die Ensemble-Mittelungsfälle aufgrund der Natur der Vollsimulationsparallelisierung deutlich übertraf.

5. Bedeutung und Ausblick

• Überwindung der Memory Wall: Das Papier zeigt einen praktischen, softwarebasierten Ansatz auf, um Speicherbandbreitenbeschränkungen in der CFD durch die Ausnutzung des „rechenleistungsgebundenen" Regimes mittels SpMM zu umgehen.
• Kosteneffizienz: Die Methode reduziert die Wandzeit und die Rechenkosten ohne die Notwendigkeit neuer Hardware und macht hochpräzise Simulationen (DNS/LES) zugänglicher.
• Skalierbarkeit: Der Ansatz ist unabhängig von der spezifischen Diskretisierungsmethode (FVM, FEM, DG) oder dem Gittertyp (strukturiert/unstrukturiert), was ihn für verschiedene CFD-Löser äußerst vielseitig macht.
• Zukünftige Trends: Die Autoren prognostizieren, dass sich die Effizienz von Supercomputern (FLOPS/Watt) langsamer verbessert als die Rohleistung, wodurch die relativen Kosten speichergebundener Operationen steigen werden. Daher werden Techniken zur Erhöhung der arithmetischen Intensität, wie SpMM, für zukünftige CFD-Anwendungen kritisch.

Fazit: Durch die Transformation von SpMV zu SpMM über alle Operatoren hinweg und die Integration einer Inline-Mesh-Verfeinerungsstrategie haben die Autoren ein robustes Framework entwickelt, das CFD-Simulationen auf modernen Supercomputern erheblich beschleunigt und Beschleunigungen von bis zu 50–80% in der Wandzeit für komplexe turbulente Strömungen bietet.