parRSB: Exascale Spectral Element Mesh Partitioning

Dieses Papier stellt parRSB vor, einen hochskalierbaren parallelen Graphenpartitionierer basierend auf der rekursiven spektralen Bisektion, der den Fiedler-Vektor nutzt, um hochwertige Partitionen für Spektralelement-Meshes zu erzeugen, wobei dessen Effektivität und Skalierbarkeit auf den Supercomputern Summit und Frontier demonstriert wird.

Das Wesentliche

Stellen Sie sich vor, Sie organisieren ein massives, komplexes Bauprojekt mit Millionen winziger Bausteine (genannt „spektrale Elemente“). Sie verfügen über eine Flotte von tausenden Baust teams (Prozessoren), die bereit sind, an diesen Blöcken zu arbeiten. Das Ziel ist es, die Blöcke so zu verteilen, dass:

1. Jedes Team etwa die gleiche Menge an Arbeit erhält (Lastverteilung/Load Balancing).
2. Die Teams nicht die ganze Zeit damit verbringen müssen, hin und her zu laufen, um miteinander zu kommunizieren (Minimierung der Kommunikation).

Wenn die Teams zu weit voneinander entfernt sind oder zu viel miteinander reden müssen, verlangsamt das das gesamte Projekt. Dieses Paper stellt ein neues Werkzeug namens parRSB vor, um dieses „Blockverteilungsproblem“ für die schnellsten Supercomputer der Welt zu lösen.

Hier ist eine Aufschlüsselung der Funktionsweise, unter Verwendung einfacher Analogien:

1. Das Problem: Das „Zu viele Telefone“-Problem

Früher waren Supercomputer wie eine Gruppe von Menschen, die in einem Raum sitzen und sich Zettel zuwerfen. Wenn man zu viele Leute hatte, wurde der Raum laut und das Zettelwechseln dauerte ewig.
Heute sind Supercomputer wie eine riesige Stadt mit Millionen von Arbeitern. Das Paper stellt fest, dass Supercomputer auf diesen neuen „Exascale“-Maschinen so effizient bei ihren lokalen Aufgaben sind, dass der größte Engpass nicht das Ausführen der Arbeit ist, sondern das Reden mit den Nachbarn.

• Der alte Weg: Wenn man die Blöcke einfach zufällig oder basierend auf einfacher Geografie verteilt (wie „Team A bekommt die Nordseite, Team B die Südseite“), könnte man am Ende Teams haben, die zwar physisch nah beieinander liegen, aber mit jedem anderen Team in der Stadt sprechen müssen, um ihre Aufgabe zu erfüllen. Dies erzeugt einen Nachrichtenstau.
• Das Ziel: Wir brauchen einen Weg, die Blöcke so zu gruppieren, dass jedes Team hauptsächlich mit seinen unmittelbaren Nachbarn kommuniziert, um das gesamte Datenvolumen, das sie senden müssen, zu minimieren.

2. Die Lösung: Die „Magische Karte“ (parRSB)

Die Autoren haben parRSB entwickelt, einen intelligenten Algorithmus, der wie ein Generalplaner fungiert. Anstatt nur zu betrachten, wo die Blöcke im Raum liegen, betrachtet er, wie die Blöcke miteinander verbunden sind.

Stellen Sie sich die Bausteine als Knoten in einem riesigen Spinnennetz vor.

• Der duale Graph: Der Algorithmus verwandelt dieses Netz in eine Karte, auf der jeder Block ein Punkt ist und eine Linie zwei Punkte verbindet, wenn sich die Blöke berühren.
• Das gewichtete Netz: Einige Verbindungen sind „schwerer“ als andere. Wenn zwei Blöcke nur eine Ecke teilen, ist die Linie leicht. Wenn sie eine ganze Fläche teilen, ist die Linie schwer (weil der Datentransfer zwischen ihnen teuer ist). parRSB achtet auf diese Gewichte.

3. Wie es den Kuchen schneidet: Der „Fiedler-Vektor“

Um dieses riesige Spinnennetz in gleich große Stücke zu schneiden, ohne zu viele Fäden zu zerreißen, nutzt parRSB einen mathematischen Trick namens Recursive Spectral Bisection (RSB).

• Die Analogie: Stellen Sie sich vor, das Spinnennetz ist eine riesige, vibrierende Gitarrensaite. Der Algorithmus findet den „Sweet Spot“ (den sogenannten Fiedler-Vektor), an dem die Saite so vibriert, dass sie das Netz natürlich in zwei gleich große Hälften teilt, wobei die wenigsten Schnitte entstehen.
• Der Schnitt: Er sortiert die Blöcke basierend auf diesem Vibrationsmuster und schneidet das Netz in der Mitte durch.
• Rekursion: Er hört dort nicht auf. Er nimmt diese zwei Hälften und schneidet sie erneut in der Mitte durch, und immer wieder, bis jedes einzelne Stück klein genug ist, um auf einen spezifischen Computerprozessor zu passen.

4. Der Motor: Zwei Wege, um den „Sweet Spot“ zu finden

Um diesen „Vibrations-Sweet-Spot“ zu finden, beschreibt das Paper zwei verschiedene Motoren (mathematische Methoden), die sie gebaut haben:

1. Lanczos: Eine schnelle, iterative Methode, die sich schnell dem Ergebnis annähert.
2. Inverse Iteration: Eine Methode, die ein Rätsel Schritt für Schritt löst, indem sie einen „Präkonditionierer“ (wie eine Abkürzungs-Karte) verwendet, um die Dinge zu beschleunigen.

Die Autoren fanden heraus, dass die Verwendung einer einfachen, schnellen Methode (wie RCB), um eine grobe Sortierung vor der Verwendung dieser ausgeklügelten Motoren durchzuführen, viel Zeit spart. Es ist wie ein Entwurf, bevor man den finalen Aufsatz schreibt.

5. Der „Gather-Scatter“-Trick

Eine der größten Innovationen des Papers ist die Art und Weise, wie es mit Daten umgeht. Normalerweise muss man für diese Mathematik eine massive, explizite Karte des gesamten Netzes erstellen, was zu viel Speicherplatz benötigt.

• Der Trick: Anstatt die ganze Karte zu bauen, nutzt parRSB eine „Gather-Scatter“-Technik.
• Die Analogie: Stellen Sie sich vor, Sie sind in einem Raum mit 1.000 Menschen. Anstatt die Telefonnummern aller Leute in einem riesigen Buch aufzuschreiben (was ewig dauert), rufen Sie einfach: „Wer hat am gleichen Geburtstag wie ich?“ Die Leute heben die Hände, Sie zählen sie und dann leiten Sie die Nachricht weiter.
• Warum es wichtig ist: Dies ermöglicht es dem Computer, die Mathematik zu betreiben, ohne die gesamte massive Karte zuerst im Speicher halten zu müssen. Es ist leichtgewichtig und schnell, was entscheidend für Maschinen mit Millionen von Prozessoren ist.

6. Die Ergebnisse: Geschwindigkeit und Skalierbarkeit

Das Team hat parRSB auf zwei der schnellsten Supercomputer der Welt getestet, Summit und Frontier.

• Geschwindigkeit: Das Werkzeug ist unglaublich schnell. In ihren Tests schloss es die Partitionierung der Daten in weniger als einer Minute ab. Im Vergleich zu den Stunden oder Tagen, die die eigentliche Simulation dauert, ist diese Vorbereitungszeit vernachlässigbar.
• Qualität: Die von ihm erstellten Partitionen sind exzellent. Die Teams (Prozessoren) sind perfekt ausbalanciert und das Volumen der Kommunikation („Reden“) wird minimiert.
• Skalierbarkeit: Es arbeitet selbst dann effizient, wenn die Anzahl der Prozessoren von einigen Tausend auf über 65.000 springt.

Zusammenfassung

parRSB ist ein hocheffizientes, paralleles Werkzeug, das Supercomputern hilft, massive 3D-Simulationen in handhabbare Stücke zu unterteilen. Indem es einen „vibrationsbasierten“ mathematischen Ansatz verwendet, um zu analysieren, wie Teile einer Simulation miteinander verbunden sind (anstatt nur, wo sie sich befinden), stellt es sicher, dass die tausenden Prozessoren, die an dem Problem arbeiten, ihre Zeit mit Berechnen verbringen, anstatt mit dem Warten auf die Kommunikation untereinander. Dies ist entscheidend für das Ausführen der nächsten Generation wissenschaftlicher Simulationen auf den leistungsstärksten Computern der Welt.

Technische Zusammenfassung

Technische Zusammenfassung von „parRSB: Exascale Spectral Element Mesh Partitioning“

Problemdefinition
Da der Hochleistungsrechnen (HPC) den Übergang zu Exascale-Systemen vollzieht, die durch beschleunigerbasierte Architekturen (GPUs) dominiert werden, nimmt die Skalierung von Spectral-Element-Methode (SEM)-Simulationen rasant zu und bewegt sich von Millionen hin zu Billionen von Freiheitsgraden (DOF). In diesem Kontext ist eine effiziente Problemzerlegung (Partitionierung) entscheidend. Die gesamte Lösungszeit wird sowohl durch die Rechenzeit als auch durch die Kommunikationszeit bestimmt. Während die Rechenzeit durch Lastverteilung minimiert wird, wird die Kommunikationszeit auf GPU-basierten Systemen aufgrund großer lokaler Problemgrößen zunehmend durch das Nachrichtenvolumen statt durch die Nachrichtenanzahl dominiert. Daher ist eine Partitionierungsstrategie, die das Kommunikationsvolumen minimiert und gleichzeitig eine strikte Lastverteilung gewährleistet, für Exascale-SEM-Simulationen unerlässlich. Bestehende Partitionierer verfügen oft nicht über die notwendige Skalierbarkeit, Kontrolle oder die Fähigkeit, Multi-Material-Domänen mit variierenden Rechenkosten pro Element zu handhaben.

Methodik
Das Paper stellt parRSB vor, einen parallelen, hochskalierbaren Graph-Partitionierer, der auf dem Algorithmus der rekursiven spektralen Bisektion (Recursive Spectral Bisection, RSB) basiert. Die Methode operiert auf dem Dualgraphen des Eingangsnetzes, wobei Knoten spektrale Elemente repräsentieren und Kanten die Verbindungen (gemeinsame Knoten, Kanten oder Flächen) darstellen.

• Graphformulierung: Das Partitionierungsproblem wird als das Finden einer Menge disjunkter Teilmengen von Knoten modelliert, die den Kanten-Schnitt (Kommunikationsvolumen) minimieren. Die Autoren verwenden eine gewichtete Laplace-Matrix, bei der die Kettengewichte der Anzahl der gemeinsam genutzten geometrischen Merkmale entsprechen (1 für Knoten, 2 für Kanten, 4 für Flächen in 3D), um sicherzustellen, dass die Partitionen das tatsächliche Datentransfervolumen minimieren.
• Berechnung des Fiedler-Vektors: Der Kern von RSB beruht auf dem Fiedler-Vektor (dem Eigenvektor, der mit dem zweitkleinsten Eigenwert des Laplace-Operators assoziiert ist). Die Autoren implementierten zwei numerische Ansätze zur Berechnung dieses Vektors:
  1. Lanczos-Iteration: Eine Methode, die aufgrund ihrer geringeren Anzahl an Gleitkommaoperationen pro Iteration bevorzugt wird.
  2. Inverse Iteration: Implementiert mittels einer vorkonditionierten flexiblen Konjugierten-Gradienten-Methode (flexCG). Dieser Ansatz wird verwendet, wenn Lanczos bei größeren Problemen nicht konvergiert.
• Laplace-Auswertung (Gather-Scatter): Um den Speicheraufwand für die explizite Konstruktion und Speicherung der dünnbesetzten Laplace-Matrix zu vermeiden, verwenden die Autoren einen Gather-Scatter-Ansatz. Diese Methode nutzt die gslib-Bibliothek zur Handhabung der Inter-Prozessor-Kommunikation. Sie bildet lokale Elementwerte auf globale Freiheitsgrade ab und zurück, wodurch der Laplace-Operator ($L = D - A$) effektiv angewendet wird, ohne eine explizite Matrix-Assemblierung durchzuführen. Dies ist besonders vorteilhaft während der Partitionierungsphase, in der das Problem-Setup auf den Prozessoren noch nicht vollständig definiert ist.
• Präkonditionierung und Optimierung:
  • Für die inverse Iteration wird ein Aggregations-basierter Algebraischer Multigrid (AMG)-Präkonditionierer verwendet. Die Autoren beschreiben eine spezifische Strategie zur Verfeinerung der Laplace-Matrix über Multigrid-Ebenen hinweg, beginnend mit einer Recursive Coordinate Bisection (RCB)-Ordnung, um die Prolongationsoperatoren zu initialisieren.
  • RCB als Pre-Partitionierer: Die Autoren stellten fest, dass das Ausführen eines geometrischen Partitionierers (RCB oder Recursive Inertial Bisection) vor der spektralen Bisektion die Laufzeit des RSB-Algorithmus signifikant reduziert, insbesondere auf den oberen Ebenen des Bisektionbaums.

Wesentliche Beiträge
Das Paper beschreibt mehrere spezifische technische Beiträge:

1. Speichereffiziente Speicherung: Implementierung eines skalierbaren Gather-Scatter-Operators zur Auswertung des Laplace-Operators, wodurch die explizite Matrix-Speicherung vermieden wird.
2. Hybride numerische Methoden: Integration sowohl von Lanczos als auch von vorkonditionierter inverser Iteration (mit voller Projektion), um Robustheit über verschiedene Problemgrößen hinweg zu gewährleisten.
3. AMG-Präkonditionierung: Entwicklung eines Aggregations-basierten AMG-Präkonditionierers, der speziell auf den Prozess der inversen Iteration zugeschnitten ist, einschließlich einer spezifischen Verfeinerungsstrategie, die die Anzahl der aktiven Prozessoren verringert, während die Matrixgröße abnimmt.
4. Optimierung via RCB: Demonstration, dass die Verwendung von RCB als Pre-Partitionierer den Prozess der spektralen Bisektion beschleunigt.
5. Skalierbarkeit: Implementierung, die darauf ausgelegt ist, auf $10^6$–$10^7$ Ranks zu skalieren, um den spezifischen Anforderungen von Exascale-Plattformen wie Summit und Frontier gerecht zu werden.

Ergebnisse
Die Autoren evaluierten parRSB auf den Supercomputern Summit und Frontier am Oak Ridge National Laboratory (OLCF).

• Performance: Auf Summit waren die Partitionierungszeiten (unter einer Minute) im Vergleich zur gesamten Setup-Zeit von NekRS (einem GPU-beschleunigten SEM-Solver) vernachledlich. Für ein Netz mit 13 Millionen Elementen reduzierte die Verwendung von RCB als Pre-Partitionier die Lanczos-Laufzeit um etwa das Zweifache.
• Skalierbarkeit: Schwache Skalierbarkeitstests auf Frontier (Erhöhung der Prozessoren von 8 auf 65.536 bei gleichbleibenden Elementen pro Prozessor von ca. 8.000) zeigten, dass parRSB die Partitionqualität beibehielt. Die durchschnittliche und maximale Anzahl der Nachbarn blieb im erwarteten Bereich (ca. 26) für SEM-Netze.
• Kommunikationsmetriken: Die Ergebnisse zeigten, dass für diese GPU-basierten Simulationen die durchschnittliche Nachrichtengröße den Latenz-Bandbreiten-Crossover-Punkt ($m_2$) deutlich überschreitet, was bestätigt, dass das Kommunikationsvolumen der dominierende Faktor in der Kommunikationszeit ist. parRSB hat dieses Volumen erfolgreich minimiert.
• Lastverteilung: Die Partitionen erreichten eine strikte Lastverteilung mit einer maximalen Imbalance von nur einem einzigen Element.

Bedeutung und Ansprüche
Das Paper positioniert parRSB als notwendiges Werkzeug für die nächste Generation von Exascale-SEM-Simulationen. Die Autoren behaupten, dass zwar viele Partitionierer existieren, aber nur wenige die spezifische Kombination aus strikter Lastverteilung, minimalem Kommunikationsvolumen und der detaillierten Kontrolle bieten, die für Multi-Material-SEM-Domänen auf modernen beschleunigerbasierten Systemen erforderlich ist. Durch die Nutzung des Gather-Scatter-Ansatzes und die Optimierung des spektralen Bisektionsprozesses ermöglicht parRSB die effiziente Zerlegung massiver Netze (Milliarden von Elementen), die für zukünftige Exascale-Anwendungen benötigt werden. Die Autoren merken an, dass die aktuelle Implementierung auf CPUs läuft, die Partitionierungszeit jedoch derzeit im Vergleich zum Solver-Setup vernachlässigbar ist; da jedoch die lokalen Problemgrößen wachsen, ist die Portierung von parRSB auf Beschleuniger eine genannte zukünftige Zielsetzung.