cuGUGA: Operator-Direct Graphical Unitary Group Approach Accelerated with CUDA

Das Paper stellt cuGUGA vor, einen leistungsstarken, GPU-beschleunigten, operator-direkten Graphical Unitary Group Approach (GUGA) Configuration Interaction Solver, der konstante Zeitalgorithmen und maßgeschneiderte CUDA-Kernel nutzt, um signifikante Beschleunigungen gegenüber bestehenden CPU- und PySCF-Implementierungen für kleine bis mittlere aktive Räume zu erzielen, während gleichzeitig eine hohe numerische Genauigkeit beibehalten wird.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen vorherzusagen, wie sich ein komplexes Molekül verhält. Um dies genau zu tun, besonders wenn die Elektronen „verschränkt“ sind oder sich seltsam verhalten, müssen Sie ein massives mathematisches Rätsel lösen, das als Configuration Interaction (CI)-Problem bezeichnet wird.

Denken Sie an dieses Rätsel wie an ein riesiges Labyrinth. Jede mögliche Art und Weise, wie sich die Elektronen anordnen können, ist ein anderer Pfad durch das Labyrinth. Je mehr Elektronen und Orbitale vorhanden sind, desto größer wird das Labyrinth – so groß, dass es eine Supercomputer Jahre dauern würde, jeden einzelnen Pfad nacheinander zu überprüfen.

Dieses Paper stellt cuGUGA vor, ein neues Werkzeug, das darauf ausgelegt ist, dieses Labyrinth viel schneller zu lösen, indem es speziell moderne Grafikkarten (GPUs) für die schwere Arbeit nutzt.

So funktioniert es, unterteilt in einfache Konzepte:

1. Die Karte vs. Die Liste (Der „Graph“-Ansatz)

Traditionelle Methoden versuchen oft, jede einzelne mögliche Elektronenanordnung aufzulisten (wie das Aufschreiben jeder einzelnen Adresse in einer Stadt). Das ist langsam und verschwendet Speicherplatz.

cuGUGA verwendet einen Graphical Unitary Group Approach (GUGA). Anstatt einer langen Liste verwendet es ein Flussdiagramm (einen sogenannten Shavitt-Graphen oder DRT).

• Die Analogie: Stellen Sie sich ein „Wähle dein eigenes Abenteuer“-Buch vor. Anstatt jedes mögliche Ende der Geschichte in einer riesigen Liste aufzuschreiben, haben Sie einfach eine Karte der Entscheidungen. Sie gehen nur den Pfaden nach, die tatsächlich möglich sind.
• Der Vorteil: Diese „Karte“ ist extrem dünn besiedelt (voll mit leerem Raum). cuGUGA weiß genau, wie es von einem gültigen Pfad zum nächsten springen kann, ohne jemals die unmöglichen zu betrachten.

2. Der „Sofort-Übersetzer“ (Lookup-Tabellen)

In den alten Zeiten musste der Computer jedes Mal, wenn er den Wert eines Schritts im Labyrinth wissen wollte, eine komplexe Berechnung durchführen, wie das Lösen eines Mini-Mathematikproblems im laufenden Betrieb. Das ist langsam.

cuGUGA verwendet vortabulierte Faktoren.

• Die Analogie: Stellen Sie sich vor, Sie spielen ein Brettspiel. Anstatt jedes Mal, wenn Sie würfeln, die Wahrscheinlichkeit zu berechnen, eine 6 zu würfeln, haben Sie einen Spickzettel, auf dem steht: „Wenn du eine 6 würfelst, ziehe 3 Felder vorwärts.“
• Der Vorteil: Der Computer rechnet nicht; er schlägt die Antwort einfach in einer vorgefertigten Tabelle nach. Dies geschieht in „konstanter Zeit“, was bedeutet, dass es in derselben Millisekunde erfolgt, egal ob die Tabelle klein oder riesig ist.

3. Die „Fließbandarbeit“ (Trennung der Aufgaben)

Der schwierigste Teil der Berechnung ist das Multiplizieren der Elektronenanordnungen mit den Kräften zwischen ihnen (Integrale).

• Der alte Weg: Der Computer würde versuchen, das „Gehen“ (das Finden der Pfade) und das „Rechnen“ (das Multiplizieren der Kräfte) alle miteinander zu vermischen. Das ist, als würde ein Koch versuchen, gleichzeitig Gemüse zu schneiden, im Topf umzurühren und abzuwaschen.
• Der cuGUGA-Weg: Es teilt die Aufgabe in zwei deutliche Phasen auf:
  1. Enumeration (Aufzählung): Schnelles Finden aller gültigen Pfade (das „Schneiden“).
  2. Contraction (Kontraktion): Durchführung der schweren Mathematik-Multiplikationen auf diesen Pfaden (das „Umrühren“).
• Der Vorteil: Diese Trennung ermöglicht es dem Computer, die besten Werkzeuge für den jeweiligen Job einzusetzen. Das „Schneiden“ wird mit spezialisiertem, maßgeschneidertem Code erledigt, während das „Umrühren“ (die schwere Mathematik) an leistungsstarke, vorgefertigte Bibliotheken übergeben wird, für die GPUs berühmt sind.

4. Die GPU-Superkraft

GPUs (wie die im Paper erwähnte NVIDIA RTX 4090) sind wie ein Schwarm aus tausenden winzigen Arbeitern. Sie sind fantastisch darin, dieselbe einfache mathematische Aufgabe immer und immer wieder parallel auszuführen, aber sie werden verwirrt, wenn jeder Arbeiter etwas anderes tun muss oder auf Anweisungen warten muss.

• Die Herausforderung: Der Teil des „Labyrinth-Gehens“ ist sehr unregelmäßig (einige Pfade sind lang, andere kurz, manche enden früh). Dies verwirrt GPUs normalerweise.
• Die cuGUGA-Lösung: Die Autoren haben einen benutzerdefinierten Code geschrieben, der diese unregelmäßigen Pfade in ordentliche Batches organisiert. Sie verwenden eine „Count-Scan-Write“-Strategie:
  1. Count (Zählen): Fragen Sie jeden Arbeiter: „Wie viele Ergebnisse wirst du produzieren?“
  2. Scan (Scannen): Finden Sie heraus, an welcher Stelle im Speicher jeder Arbeiter seine Ergebnisse ablegen soll, damit sie sich nicht gegenseitig behindern.
  3. Write (Schreiben): Alle schreiben ihre Ergebnisse gleichzeitig.
• Das Ergebnis: Dies verwandelt eine unordentliche, unregelmäßige Aufgabe in ein reibungsloses, Hochgeschwindigkeits-Fließband.

Die Ergebnisse: Wie schnell ist es?

Die Autoren haben dies auf einer Standard-Grafikkarte für Endverbraucher (RTX 4090) getestet und mit Folgendem verglichen:

1. Standard-CPU-Code (der „alte“ Weg).
2. Anderer populärer Chemiesoftware (PySCF).

• Genauigkeit: Es ist genauso genau wie die besten existierenden Methoden (die Unterschiede sind kleiner als das Gewicht eines einzelnen Atoms).
• Geschwindigkeit:
  • Für kleinere bis mittelgroße molekulare Probleme ist die GPU-Version etwa 10-mal schneller als die CPU-Version.
  • Im Vergleich zur populären Software PySCF ist cuGUGA auf der CPU bereits 2- bis 4-mal schneller und bis zu 40-mal schneller, wenn die GPU für kleinere aktive Räume genutzt wird.
  • Die Einschränkung: Wenn das molekulare Problem sehr groß wird, schrumpft der Geschwindigkeitsvorteil. Das liegt daran, dass der Teil der „schweren Mathematik“ (das Multiplizieren riesiger Matrizen) zum Engpass wird und Consumer-Grafikkarten bei dieser speziellen Art von Mathematik nicht so leistungsstark sind wie spezialisierte Rechenzentrum-Supercomputer.

Zusammenfassung

cuGUGA ist ein neuer, hochoptimierter Motor zur Lösung komplexer Elektronen-Rätsel. Es verwendet eine intelligente Karte statt einer langen Liste, fertige Spickzettel für sofortige Antworten und ein spezialisiertes Fließband, um die Kraft moderner Grafikkarten zu nutzen. Es ermöglicht Wissenschaftlern, diese Probleme deutlich schneller als zuvor zu lösen, wodurch komplexe chemische Simulationen zugänglicher werden.

Technische Zusammenfassung

Technische Zusammenfassung von cuGUGA: Operator-direkter Graphical Unitary Group Approach beschleunigt mit CUDA

Problemstellung
Genaue elektronische Strukturvorhersagen für stark korrelierte Moleküle erfordern oft Multireferenz-Behandlungen, insbesondere Complete Active Space Self-Consistent Field (CASSCF)-Methoden. Diese Methoden beinhalten das Lösen eines Full Configuration Interaction (FCI)-Problems innerhalb eines gewählten aktiven Orbital-Subraums. Der Rechenengpass in den CASSCF-Makroiterationen ist die wiederholte Auswertung des Matrix-Vektor-Produkts (des „$\sigma$-Vektors“, $\sigma = Hc$), das durch iterative Eigengleichungslöser wie Davidson erforderlich ist.

Obwohl die Arbeit in einer spin-adaptierten Configuration State Function (CSF)-Basis (via Graphical Unitary Group Approach, GUGA) die Dimensionalität des Problems im Vergleich zu einer Slater-Determinanten-Basis reduziert und die Spin-Reinheit erzwingt, stehen praktische Implementierungen vor Herausforderungen. Bestehende Codes führen oft Determinanten-Zwischenschritte oder große Cache-Objekte in den innersten Schleifen ein, um Hamiltonian-Kopplungen zu handhaben. Dieser Ansatz maskiert die feingliedrige Sparsity der CSF-Kopplungen und erschwert eine effiziente Ausführung auf moderner Hardware, insbesondere auf GPUs, die mit irregulären Graph-Traversierungen und pointer-lastiger Logik, wie sie in Legacy-GUGA-Implementierungen üblich ist, Schwierigkeiten haben.

Methodik
Die Arbeit stellt cuGUGA vor, einen operator-direkten GUGA CI-Solver, der die Trennung der spärlichen Kopplungs-Enumeration von der Integral-Kontraktion ermöglicht, um eine effiziente Abbildung auf CPU- und GPU-Architekturen zu gewährleisten.

1. Operator-direkte Formulierung:
   Anstatt die Hamiltonian-Matrix explizit zu bilden, berechnet cuGUGA $\sigma = Hc$, indem es spinfreie Generatoren ($E_{pq}$) direkt auf CSFs anwendet. Die Wirkung dieser Generatoren ist spärlich; für eine gegebene CSF $|\Phi_j\rangle$ erzeugt $E_{pq}|\Phi_j\rangle$ eine Linearkombination einer geringen Anzahl verbundener CSFs.

2. DRT-Repräsentation und Indizierung:
   Der CSF-Raum wird als geschichteter gerichteter azyklischer Graph (DAG) dargestellt, bekannt als Shavitt-Graph oder Directed Row Table (DRT).

   • Ranking/Unranking: Dynamische Programmierung (DP) wird verwendet, um Suffix-Walk-Zählungen ($W(v)$) und Präfix-Summen ($\Pi(v, d)$) auf dem DRT zu berechnen. Dies ermöglicht eine Konstante-Zeit-Konvertierung zwischen CSF-Indizes und ihren entsprechenden Schritt-Sequenzen (Walks) auf dem Graphen.
   • Segment-Walks: Um verbundene CSFs zu finden, führt der Code eine „Segment-Walk“-Traversierung durch. Diese exploriert gültige Substitutionen von Schritten innerhalb eines spezifischen Orbital-Intervalls $[p_<, p_>]$, das durch den Generator $E_{pq}$ definiert ist, unter Einhaltung der Randknoten zur Sicherstellung der DRT-Validität.

3. Konstante-Zeit-Kopplungs-Evaluierung:
   Lokale Kopplungskoeffizienten (Segment-Faktoren) werden mittels einer Zwei-Level-Lookup-Table (LUT)-Strategie in konstanter Zeit evaluiert. Eine Finite-Case-Map ordnet lokale Muster kompakten Case-IDs zu, welche wiederum in ein vortabuliertes Array von Koeffizienten basierend auf dem lokalen Spin-Label indizieren. Dies eliminiert komplexe Branching-Logik während der Hot-Loop.

4. Intermediate-Weight-Formulierung:
   Für den Zwei-Elektronen-Beitrag verwendet die Methode eine Intermediate-Weight-Dekomposition. Zuerst werden spärliche Koeffizienten für die Wirkung eines einzelnen Generators ($E_{rs}$) enumeriert, die dann mit den Zwei-Elektronen-Integralen kontrahiert werden, um effektive Gewichte ($g^{(\mu j)}_{pq}$) zu bilden. Dies trennt die spärliche CSF-Enumeration von der dichten Integral-Kontraktion.

   • Backends: Die Implementierung unterstützt sowohl dichte Vier-Index-Integrale als auch Density-fitted (DF) oder Cholesky-faktorisierte Repräsentationen. Das DF/Cholesky-Backend reduziert die Kontraktion auf Sparse/Dense- und Dense/Dense-Matrixmultiplikationen (GEMM/SpMM).

5. GPU-Beschleunigungsstrategie:
   Um die irreguläre DRT-Traversierung an die SIMT-Architektur (Single Instruction, Multiple Threads) von GPUs anzupassen:

   • Datenlayout: DRT-Tabellen und Knoten-Labels werden als zusammenhängende Device-Arrays gespeichert, um Pointer-Chasing zu vermeiden und kohärente Speicherzugriffe (coalesced access) zu ermöglichen.
   • Count-Scan-Write: Da Segment-Walks eine variable Anzahl an Nachbarn erzeugen, wird eine Drei-Pass-Kernel-Strategie (Count, Exclusive Scan für Offsets, Write) verwendet, um Output-Buffer ohne dynamische Allokation zu füllen.
   • Batching: Der Solver wendet den Hamiltonian auf einen Block von Vektoren an, um die arithmetische Intensität zu maximieren, insbesondere für die Zwei-Elektronen-Kontraktionsstufe.
   • Präzision: Alle Kontraktionen und Eigenwert-Updates werden in Doppelpräzision (FP64) durchgeführt.

Hauptbeiträge

• Erster Operator-direkter GUGA GPU-Solver: cuGUGA implementiert einen vollständig CSF-direkten Solver, bei dem die irreguläre Graph-Traversierung und Akkumulation durch spezialisierte CUDA-Kernel gehandhabt werden, während dichte Kontraktionen an optimierte CUDA-Bibliotheken (cuBLAS, cuSPARSE) delegiert werden.
• Hardware-agnostische Primitiven: Die mathematische Kernformulierung trennt die spärliche Enumerations-Logik vom Integral-Backend, wodurch dieselben Primitiven effizient auf CPU und GPU laufen können.
• Performance-Optimierung: Die Verwendung von vortabulierten Segment-Faktoren und flachen DRT-Tabellen minimiert Warp-Divergenz und Speicherlatenz auf GPUs.

Ergebnisse
Die Implementierung wurde auf einem Intel Core i7-14700K CPU und einer NVIDIA GeForce RTX 4090 GPU benchmarkt.

• Genauigkeit: Der Solver reproduziert Referenzenergien auf dem Niveau von $10^{-11}$ $E_h$. Vergleiche zwischen CPU- und GPU-Backends zeigen Übereinstimmungen in den $\sigma$-Vektoren bis zu $10^{-14}$, und die Run-to-Run-Dispersion ist vernachlässigbar ($< 10^{-13}$).
• CPU-Performance: Das cuGUGA CPU-Backend liefert eine Beschleunigung von $\gtrsim 2\times$ gegenüber dem PySCF-Determinanten-Backend und eine Beschleunigung von $\gtrsim 4\times$ gegenüber dem PySCF-CSF-Backend für repräsentative CASCI-Kernel.
• GPU-Performance: Auf der RTX 4090 bietet das GPU-Backend eine bis zu $\sim 10\times$ höhere Geschwindigkeit gegenüber dem cuGUGA CPU-Backend für kleinere aktive Räume. Für repräsentative Systeme übersetzt sich dies in Gesamtsbeschleunigungen von über $20\times$ relativ zu PySCF(DET) und über $40\times$ relativ zu PySCF(CSF).
• Skalierungsverhalten: Die Beschleunigung nimmt ab, wenn der aktive Raum größer wird. Dies ist darauf zurückzuführen, dass die Arbeitslast zunehmend von FP64 GEMM-Operationen dominiert wird. Consumer-GPUs (wie die RTX 4090) haben eine begrenzte FP64-Durchsatzrate (ca. 1/64 von FP32), was die Beschleunigung für die kontraktionslastigen Stadien großer aktiver Räume einschränkt. Das Paper stellt fest, dass Data-Center-GPUs mit höheren FP64-Kapazitäten wahrscheinlich höhere Beschleunigungen aufrechterhalten würden.

Bedeutung
Das Paper positioniert cuGUGA als spezialisiertes Werkzeug für Fälle, in denen Spin-Adaption und CSF-direkte Sparsity kritisch sind und eine GPU-Beschleunigung des CI-Schritts erwünscht ist. Es adressiert den spezifischen architektonischen Mismatch zwischen traditionellen GUGA-Implementierungen (die auf pointer-lastigen Graph-Traversierungen basieren) und GPU-Ausführungsmodellen. Durch die saubere Trennung der spärlichen Enumeration der CSF-Kopplungen von den dichten Integral-Kontraktionen erreicht cuGUGA signifikante Leistungssteigerungen auf Consumer-Hardware bei gleichzeitiger Wahrung der rigorosen Spin-Reinheit und Genauigkeit des GUGA-Formalismus. Die Arbeit zeigt, dass operator-direkte GUGA-Methoden effektiv auf GPUs portiert werden können, was eine lebensfähige Alternative zu determinanten-basierten Ansätzen für stark korrelierte Systeme darstellt.