On Distributed Parallelization Strategies for Particle-in-Fourier Schemes

Dieser Beitrag stellt drei verteilte Parallelisierungsstrategien vor und vergleicht sie—Gebietszerlegung, Partikelzerlegung sowie Raum-Zeit-Zerlegung unter Verwendung des Parareal-Algorithmus—für Partikel-in-Fourier-Verfahren in kinetischen Plasmasimulationen, wobei ihre Kommunikationsmuster, Leistungsregime und Skalierbarkeit auf Supercomputern mittels der IPPL-Bibliothek analysiert werden.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, eine massive Menschenmenge (Teilchen) zu simulieren, die sich durch eine Stadt bewegt, wobei ihre Bewegung von unsichtbaren Kräften (elektrischen und magnetischen Feldern) beeinflusst wird, die davon abhängen, wo jeder andere steht. Genau das tun Wissenschaftler, wenn sie Plasma modellieren, das extrem heiße Gas, das in Sternen, Fusionsreaktoren und Teilchenbeschleunigern vorkommt.

Der von Ihnen bereitgestellte Artikel handelt davon, wie man einen Supercomputer dazu bringt, diese Simulation so schnell wie möglich durchzuführen.

Die spezifische Methode, die sie verwenden, heißt Particle-in-Fourier (PIF). Betrachten Sie PIF als eine hochpräzise Methode zur Berechnung, wie sich die Menge bewegt. Im Gegensatz zu älteren Methoden, die ein grobes Gitter verwenden (wie eine niedrig aufgelöste Karte), nutzt PIF einen „spektralen" Ansatz (wie eine hochauflösende, glatte Karte), der über lange Zeiträume hinweg sehr genau und stabil ist.

Die Simulation von Milliarden von Teilchen ist jedoch für einen einzelnen Computer zu schwierig. Daher stellten die Autoren die Frage: „Wie teilen wir diese massive Aufgabe unter Tausenden von Prozessoren (Ranks) auf, um die beste Geschwindigkeit zu erzielen?"

Sie testeten drei verschiedene Strategien, die sie mit der Analogie der Organisation eines Teams von Arbeitern vergleichen.

Die drei Strategien

1. Domänendekomposition: „Die Nachbarschaftswache"

• Funktionsweise: Stellen Sie sich vor, die Stadt wird in kleine Nachbarschaften unterteilt. Jeder Prozessor erhält eine Nachbarschaft zugewiesen. Er verfolgt nur die Personen innerhalb dieser Nachbarschaft und die lokalen Kräfte dort.
• Der Haken: Menschen bewegen sich! Wenn jemand von Nachbarschaft A in Nachbarschaft B geht, muss der Prozessor für A dem Prozessor für B mitteilen: „Hey, diese Person verlässt das Gebiet." Außerdem muss jede Nachbarschaft wissen, was direkt außerhalb ihrer Grenzen passiert (die „Halo"- oder „Ghost"-Schichten), um die Kräfte genau zu berechnen.
• Vorteile: Es ist sehr speichereffizient. Wenn die Stadt riesig ist, können Sie sie in so viele Teile zerlegen, wie Sie möchten.
• Nachteile: Es ist kompliziert. Wenn die Menge ungleichmäßig verteilt ist (manche Nachbarschaften sind vollgepackt, andere leer), bleiben einige Prozessoren stecken und erledigen die ganze Arbeit, während andere untätig sind. Das ständige Reden zwischen den Nachbarn (Kommunikation) kann die Geschwindigkeit verringern.

2. Partikeldekomposition: „Das spezialisierte Team"

• Funktionsweise: Stellen Sie sich vor, Sie teilen nicht die Stadt auf. Stattdessen teilen Sie die Menschen auf. Prozessor A verwaltet 1/100 der Menge, Prozessor B ein weiteres 1/100 und so weiter.
• Der Haken: Jeder einzelne Prozessor hat eine vollständige Kopie der Stadtkarte (der Fourier-Moden) und der Regeln, wie die Kräfte wirken.
• Vorteile: Es ist unglaublich einfach. Da jeder die vollständige Karte hat, müssen sie nicht mit Nachbarn sprechen, um Kräfte zu berechnen. Es ist auch perfekt ausbalanciert; wenn Sie 100 Personen haben, geben Sie einfach 1 Person an jeden von 100 Prozessoren. Es spielt keine Rolle, ob die Menge gehäuft oder verteilt ist.
• Nachteile: Es ist speicherintensiv. Jeder Prozessor muss die gesamte Stadtkarte halten. Wenn die Karte zu groß ist, reicht der Speicher nicht aus. Außerdem können Sie, sobald Sie die Menschen aufgeteilt haben, die Karte nicht weiter teilen, sodass es eine Grenze dafür gibt, wie viele Prozessoren Sie verwenden können, bevor sie beginnen, aufeinander zu warten.

3. Raum-Zeit-Dekomposition: „Die Zeitreisenden"

• Funktionsweise: Dies baut auf dem „spezialisierten Team" (Partikeldekomposition) auf. Stellen Sie sich ein Team von Arbeitern vor, das nicht nur an den Menschen arbeitet, sondern auch an der Zeit.
• Der Haken: Die Simulation wird in Zeitabschnitte unterteilt (z. B. die erste Stunde, die zweite Stunde). Eine Gruppe von Prozessoren simuliert die erste Stunde, eine andere Gruppe die zweite Stunde, und alle tun dies gleichzeitig.
• Der Trick: Da die Zukunft von der Vergangenheit abhängt, verwenden sie eine „Versuch-und-Irrtum"-Methode (Parareal genannt). Sie machen eine schnelle, grobe Schätzung der Zukunft und führen dann die genaue Simulation parallel durch, um die Schätzung zu korrigieren.
• Vorteile: Es kann zusätzliche Geschwindigkeit herausholen, wenn Sie so viele Prozessoren haben, dass die Methode des „spezialisierten Teams" nicht schneller werden kann.
• Nachteile: Es erfordert viel zusätzlichen Speicher und Rechenleistung, da sie dieselben Zeitabschnitte mehrfach simulieren, um das Ergebnis richtig zu bekommen. Es funktioniert auch nur gut, wenn die Simulation über einen sehr langen Zeitraum läuft.

Was sie herausfanden (Die Ergebnisse)

Die Autoren testeten diese Strategien an zwei verschiedenen „Menschenmengen-Szenarien" mit zwei der schnellsten Supercomputer der Welt (Alps und JUWELS):

1. Szenario A: Landau-Dämpfung (Die glatte Menge)

   • Die Menschen sind gleichmäßig verteilt.
   • Gewinner: Domänendekomposition (Nachbarschaftswache) war am schnellsten, insbesondere bei der Verwendung vieler Prozessoren. Sie bewältigte die glatte Verteilung perfekt.
   • Platz zwei: Das „spezialisierte Team" (Partikeldekomposition) war großartig für kleine Gruppen von Prozessoren, stieß aber an eine Wand, als die Gruppe zu groß wurde.

2. Szenario B: Penning-Falle (Die gehäufte Menge)

   • Die Menschen sind in dichten Clustern zusammengeballt (wie bei einem Mosh-Pit).
   • Gewinner: Partikeldekomposition (Spezialisiertes Team) und Raum-Zeit-Dekomposition (Zeitreisende) überrannten die Konkurrenz.
   • Warum? Bei der Methode der „Nachbarschaftswache" wurden die Prozessoren mit den überfüllten Nachbarschaften überwältigt, während die leeren nichts taten. Das „spezialisierte Team" kümmerte sich nicht um die Cluster; es teilte die Menschen einfach gleichmäßig auf, sodass alle beschäftigt blieben.
   • Ergebnis: Für dieses gehäufte Szenario waren die neuen Strategien bis zu 2,5-mal schneller als die traditionelle Methode.

Das Fazit

Die Autoren kommen zu dem Schluss, dass es keinen einzigen „besten" Weg gibt, diese Simulationen durchzuführen. Es hängt von Ihrem Problem ab:

• Wenn Ihre Daten riesig und gleichmäßig verteilt sind, teilen Sie den Raum auf (Domänendekomposition).
• Wenn Ihre Daten geklumpt sind oder Sie viele Teilchen haben, aber eine überschaubare Karte, teilen Sie die Teilchen auf (Partikeldekomposition).
• Wenn Sie massive Rechenleistung haben und für eine sehr lange Zeit laufen müssen, fügen Sie eine Zeitteilung darüber hinzu (Raum-Zeit-Dekomposition).

Die Autoren haben diese Strategien in eine freie Softwarebibliothek namens IPPL integriert, damit andere Wissenschaftler sie nutzen können, um Plasmaphysik effizienter zu simulieren.

Technische Zusammenfassung

Technisches Fazit: Verteilte Parallelisierungsstrategien für Partikel-in-Fourier-Verfahren

Problemstellung

Kinetische Plasmasimulationen, die für die Modellierung von Kernfusion, Teilchenbeschleunigern und astrophysikalischen Phänomenen unerlässlich sind, verlassen sich traditionell auf Partikel-in-Zelle-Verfahren (PIC). Allerdings leiden Standard-Explizit-PIC-Methoden unter Nicht-Energieerhaltung und Aliasing, was zu numerischen Instabilitäten wie der Finite-Grid-Instabilität und Gittererwärmung führt. Die Minderung dieser Probleme erfordert typischerweise übermäßige Gitterpunkte und Partikel, was die Rechenkosten erheblich steigert.

Obwohl energieerhaltende und strukturerhaltende PIC-Verfahren existieren, beinhalten sie oft komplexe implizite Integratoren oder variationsbasierte Formulierungen, die schwer in bestehende Produktionscodes zu integrieren sind. Partikel-in-Fourier-Verfahren (PIF) bieten eine vielversprechende Alternative, die spektrale Genauigkeit, hervorragende Langzeitstabilität und Erhaltungseigenschaften bietet, während sie die strukturelle Einfachheit von Standard-PIC beibehalten. PIF vermeidet Realraumgitter, indem es direkt zwischen Partikeln und Fourier-Moden unter Verwendung von Nicht-Uniformen Fast-Fourier-Transformationen (NUFFT) interpoliert.

Trotz der Vorteile von PIF sind verteilte Parallelisierungsstrategien für diese Verfahren weniger entwickelt als für Standard-PIC. Die bestehende Literatur fehlt es an einem umfassenden Vergleich verschiedener Parallelisierungsansätze hinsichtlich ihrer Kommunikationsmuster, Skalierbarkeit und Eignung für spezifische Parameterbereiche (Partikelanzahl, Fourier-Moden und Zeitschritte). Dieser Beitrag schließt diese Lücke, indem er drei verschiedene verteilte Parallelisierungsstrategien für PIF-Verfahren analysiert und vergleicht.

Methodik

Die Autoren implementierten und verglichen drei Parallelisierungsstrategien innerhalb der Open-Source-Leistungstransportfähigen C++-Bibliothek IPPL. Die Strategien wurden mittels starker Skalierungsstudien an zwei Benchmark-Problemen evaluiert: 3D-3V Landau-Dämpfung (homogene Partikelverteilung) und eine Penning-Falle-Simulation (geklumpte, inhomogene Partikelverteilung). Die Simulationen wurden auf den Supercomputern Alps (CSCS, Schweiz) und JUWELS Booster (Jülich, Deutschland) unter Verwendung von NVIDIA A100- und GH200-GPUs durchgeführt.

Die drei analysierten Strategien sind:

1. Gebietszerlegung (Domain Decomposition, DD):

   • Mechanismus: Sowohl der räumliche Bereich (Partikel) als auch die Fourier-Moden werden über MPI-Ranks partitioniert.
   • Implementierung: Erfordert verteilte NUFFTs. Partikel und Halo-Schichten werden über Punkt-zu-Punkt-Kommunikation (P2P) ausgetauscht. Verteilte FFTs innerhalb von NUFFTs beinhalten kollektive Alltoall-Kommunikation.
   • Merkmale: Speicher- und arbeitsoptimal bis zu den Halo-Schichten. Erfordert dynamisches Puffermanagement aufgrund sich ändernder Partikelverteilungen. Benötigt eine kombinierte Lastverteilung für Partikel und Felder bei inhomogenen Verteilungen.

2. Partikelzerlegung (Particle Decomposition, PD):

   • Mechanismus: Partikel werden über die Ranks partitioniert, während alle Fourier-Moden auf jedem Rank dupliziert (repliziert) werden.
   • Implementierung: Lokale NUFFTs werden auf lokalen Partikeln durchgeführt. Eine globale Allreduce-Operation fasst die Ladungsdichte im Fourier-Raum zusammen. Feldlösungen und Sammlungen werden lokal durchgeführt.
   • Merkmale: Durch Konstruktion lastbalanciert für sowohl Partikel als auch Felder, was sie gegenüber inhomogenen Verteilungen robust macht. Die Kommunikation ist statisch und auf eine einzelne Allreduce beschränkt. Sie ist jedoch nicht speicheroptimal (aufgrund der Modenreplikation) und erzeugt einen seriellen Engpass für Feldoperationen, wenn die Anzahl der Ranks steigt.

3. Raum-Zeit-Zerlegung (Space-Time Decomposition, ST):

   • Mechanismus: Zeitparallelisierung (unter Verwendung des Parareal-Algorithmus) wird auf die Partikelzerlegung aufgesetzt.
   • Implementierung: Der Zeitbereich wird in Intervalle unterteilt. Ein „grober Propagator" (entweder ein PIF mit gröberer NUFFT-Toleranz oder ein Standard-PIC-Verfahren) läuft seriell, um Anfangsschätzungen zu liefern, während ein „feiner Propagator" (PIF mit Partikelzerlegung) parallel läuft.
   • Merkmale: Fügt Redundanz in Berechnung und Speicher hinzu, ermöglicht jedoch eine Skalierung über die Grenzen der räumlichen Parallelisierung hinaus. Die Kommunikation beinhaltet P2P-Austausch von Partikelzuständen zwischen Zeit-Schichten und Allreduce für Dichtefelder.

Hauptbeiträge

• Vergleichende Analyse: Der Beitrag liefert den ersten detaillierten Vergleich von Gebiets-, Partikel- und Raum-Zeit-Zerlegungsstrategien speziell für PIF-Verfahren und identifiziert die Kommunikationsmuster und Parameterbereiche, in denen jede Strategie glänzt.
• Implementierung: Die Strategien wurden in der IPPL-Bibliothek implementiert, mit Schnittstellen zu nativen NUFFT-Implementierungen und der FINUFFT-Bibliothek (für GPU-Unterstützung).
• Skalierungsstudien: Umfassende Ergebnisse zur starken Skalierung wurden für 256³ Fourier-Moden und ca. 168 Millionen Partikel über zwei verschiedene physikalische Regime (homogen vs. geklumpt) präsentiert.
• Leistungscharakterisierung: Die Autoren analysierten dominierende Kernel-Zeiten (Scatter, Gather, Allreduce, Kommunikation), um Engpässe zu identifizieren, wie etwa die seriellen Feldkosten bei PD und Kommunikationsaufwände bei ST.

Ergebnisse

• Landau-Dämpfung (Homogen):

  • Gebietszerlegung schnitt bei hohen GPU-Anzahlen am besten ab und bot aufgrund ihres arbeitsoptimalen Charakters eine überlegene Skalierung.
  • Partikelzerlegung war bei niedrigen GPU-Anzahlen (bis zu 8 GPUs) konkurrenzfähig, litt jedoch bei steigender Anzahl der Ranks unter seriellen Engpässen.
  • Raum-Zeit-Zerlegung bot zusätzlichen Geschwindigkeitsgewinn, wenn die Effizienz der räumlichen Parallelisierung unter 50 % fiel, und überbrückte effektiv die Lücke zwischen PD und DD bei hohen Kernzahlen.

• Penning-Falle (Geklumpt/Inhomogen):

  • Gebietszerlegung hatte aufgrund von Partikel-Lastungleichgewichten erhebliche Schwierigkeiten, was zu Feld-Lastungleichgewichten führte und zu einer schlechten Skalierung jenseits von 8 GPUs führte.
  • Partikelzerlegung schnitt deutlich besser ab als die Gebietszerlegung (bis zu 2× schneller bei 8 GPUs), da ihr Design inhomogene Verteilungen ohne Lastverteilung von Natur aus handhabt.
  • Raum-Zeit-Zerlegung erreichte bei 512 GPUs einen Geschwindigkeitsgewinn von bis zu 2,5× gegenüber der Gebietszerlegung und 2× gegenüber der Partikelzerlegung und demonstrierte damit ihren Nutzen für Probleme, bei denen die räumliche Skalierung sättigt.

• Hardware-Beobachtungen:

  • Auf dem JUWELS Booster (GH200) stieß die Gebietszerlegung bei einzelnen GPUs aufgrund des höheren Speicherbedarfs der nativen NUFFT-Implementierung im Vergleich zu FINUFFT an Speicherlimits, während die Partikelzerlegung weiterhin praktikabel blieb.
  • Die absoluten Laufzeiten auf JUWELS waren 1,5–2× langsamer als auf Alps (A100), was auf Hardwareunterschiede zurückzuführen ist.

Bedeutung und Behauptungen

Der Beitrag behauptet, eine kritische Lücke in der PIF-Literatur zu schließen, indem er eine Basis für die Auswahl von Parallelisierungsstrategien basierend auf Problemcharakteristika (Partikelanzahl, Modenanzahl, Verteilungshomogenität) bietet.

• Für homogene Probleme: Die Gebietszerlegung bleibt die am besten skalierende und effizienteste Strategie für großskalige Simulationen, sofern die Lastverteilung verwaltet wird.
• Für inhomogene Probleme: Die Partikelzerlegung bietet eine robuste, wenig invasive Alternative, die die komplexe Lastverteilung vermeidet, die für die Gebietszerlegung erforderlich ist, und bei moderaten Skalen gut abschneidet.
• Für extreme Skalierung: Die Raum-Zeit-Zerlegung bietet einen Weg, die Lösungszeit weiter zu reduzieren, wenn die räumliche Parallelisierung sättigt, führt jedoch Redundanz und Kommunikationsaufwände ein, die sorgfältig verwaltet werden müssen.

Die Autoren betonen, dass diese Strategien zwar unterschiedliche Kompromisse bieten, keine jedoch universell überlegen ist; die optimale Wahl hängt vom spezifischen Parameterbereich und der Art der Partikelverteilung ab. Als zukünftige Arbeiten werden die Entwicklung einer kombinierten Partikel-Feld-Lastverteilung für die Gebietszerlegung und die Erforschung von Multigrid-Reduktion in der Zeit zur Minderung der Kommunikationskosten bei der Raum-Zeit-Zerlegung identifiziert.