A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture

Die vorgestellte Arbeit stellt eine vollständig GPU-residente, sperrenfreie Multi-GPU-Architektur vor, die durch den vollständigen Umzug des Sieb-Generierungsprozesses auf die GPU und die Einführung eines asynchronen Work-Stealing-Pools die Goldbach-Vermutung bis zu $10^{13}$ mit einer Geschwindigkeit von 133,5 Sekunden auf einem Vier-GPU-System verifiziert und dabei eine algorithmische Beschleunigung von 45,6-fach gegenüber vorherigen Ansätzen erreicht.

Das Wesentliche

Stellen Sie sich vor, Sie wollen beweisen, dass jede gerade Zahl (ab 4) als Summe von zwei Primzahlen geschrieben werden kann. Das ist die berühmte Goldbach-Vermutung. Es ist wie ein riesiges Puzzle, bei dem man für jede gerade Zahl zwei passende Puzzleteile (Primzahlen) finden muss.

Bis vor kurzem war es wie folgt: Ein Computer (die CPU) hat die Puzzleteile sortiert und sie einem extrem schnellen Superhelden (der Grafikkarte/GPU) zugeworfen. Der Superheld hat blitzschnell geprüft, ob die Teile passen, und dann wieder gewartet, bis der Computer das nächste Paket geworfen hat. Der Superheld hat also viel Zeit damit verbracht, auf den Computer zu warten, statt zu arbeiten.

Dieses neue Papier beschreibt eine revolutionäre Änderung: Der Superheld macht jetzt alles selbst.

Hier ist die Erklärung der wichtigsten Neuerungen, einfach und mit Analogien:

1. Der "Selbstversorger"-Superheld (Vollständig auf der Grafikkarte)

In der alten Version musste der Computer (CPU) für jeden kleinen Abschnitt der Zahlen die Liste der Primzahlen vorbereiten und sie über ein langsames Kabel (PCIe-Bus) zur Grafikkarte schicken. Das war wie ein Koch, der jeden einzelnen Löffel Reis einzeln vom Lager zum Herd trägt, während der Herd eigentlich schon bereit ist, Millionen von Reisern zu kochen.

Die neue Lösung: Der Koch (die Grafikkarte) hat jetzt sein eigenes kleines Lagerhaus direkt neben dem Herd (im "L1 Shared Memory"). Er holt sich die Zutaten selbst, kocht das ganze Gericht und wirft nichts weg. Der Computer muss nur noch ein einziges kleines Signal senden: "Fang an!" und bekommt am Ende nur ein winziges Ergebnis zurück: "Alles erledigt!" oder "Hier ist ein Problem".

• Das Ergebnis: Die Grafikkarte arbeitet jetzt fast ohne Unterbrechung. Sie ist nicht mehr durch den langsamen Datenverkehr mit dem Computer gebremst.

2. Das "Diebstahl-System" ohne Wartezeit (Lock-Free Work-Stealing)

Stellen Sie sich ein Team von vier Superhelden vor, die ein riesiges Bergwerk abarbeiten sollen.

• Die alte Methode: Man teilte den Berg in vier gleich große Hälften. Wenn einer der Helden langsamer war (weil er vielleicht heißer wurde oder ein schlechteres Werkzeug hatte), warteten alle anderen auf ihn. Das war ineffizient.
• Die neue Methode: Es gibt keinen festen Plan. Jeder Held nimmt sich einfach das nächste Stück Berg, das noch niemand angefasst hat. Wenn ein Held fertig ist, schnappt er sich sofort das nächste Stück. Es gibt keine Staus und keine Wartezeiten.
• Der Trick: Alle Helden greifen auf eine gemeinsame Liste zu, ohne sich gegenseitig zu blockieren ("Lock-Free"). Das System passt sich automatisch an: Wenn ein Held schneller ist, erledigt er einfach mehr Arbeit.

3. Der Sicherheitsgurt (Mathematische Überwachung)

Da die Zahlen so riesig sind (bis zu 18.400.000.000.000.000.000), besteht die Gefahr, dass der Computer bei der Rechnung "überläuft" (wie ein Tacho, der bei 999.999 abbricht und bei 000.000 weiterzählt). Das könnte zu falschen Ergebnissen führen.

• Die Lösung: Das Programm hat extrem strenge mathematische Sicherheitsgurte eingebaut. Es überprüft jede Rechnung doppelt und dreifach, um sicherzustellen, dass keine Zahl "verloren geht" oder falsch berechnet wird. Es garantiert, dass das Ergebnis bis zu einer bestimmten Grenze absolut wasserdicht ist.

4. Die Ergebnisse: Ein Blitz im Vergleich zu einem Schneckentempo

Die Autoren haben ihre neue Methode auf modernster Hardware getestet (NVIDIA RTX 5090 Grafikkarten):

• Geschwindigkeit: Auf einer einzigen Grafikkarte ist die neue Methode 45-mal schneller als die alte Methode bei großen Zahlen. Das ist, als würde man eine Reise, die früher einen ganzen Tag dauerte, nun in wenigen Minuten schaffen.
• Skalierung: Mit vier Grafikkarten zusammen schaffen sie es, die Vermutung bis zur Zahl 10 Trillionen (10¹³) in nur 133,5 Sekunden zu überprüfen. Das ist schneller, als Sie diesen Satz lesen können.
• Zuverlässigkeit: Bei allen getesteten Zahlen wurde kein Gegenbeispiel gefunden. Die Vermutung hält also auch bei diesen extremen Zahlen stand.

Zusammenfassung

Dieses Papier zeigt, wie man ein mathematisches Problem löst, indem man die Kommunikation zwischen dem "Manager" (CPU) und dem "Arbeiter" (GPU) komplett neu organisiert. Statt dass der Manager den Arbeiter mit Arbeit füttert, bekommt der Arbeiter die Werkzeuge direkt in die Hand und arbeitet autonom. Durch eine clevere Organisation der Arbeitsteilung (Work-Stealing) und strenge Sicherheitschecks kann man nun riesige Zahlenmengen in Sekundenbruchteilen überprüfen, was früher Jahre gedauert hätte.

Es ist ein Beweis dafür, dass man durch intelligente Software-Architektur die Grenzen der Hardware oft noch weiter hinausschieben kann, als man dachte.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture" auf Deutsch:

1. Problemstellung

Die Goldbach-Vermutung besagt, dass jede gerade Zahl größer als 2 als Summe zweier Primzahlen dargestellt werden kann. Obwohl theoretische Fortschritte erzielt wurden, bleibt der Beweis offen, und die computergestützte Verifikation ist entscheidend.

• Bisherige Grenzen: Frühere GPU-Implementierungen (z. B. in der Vorgängerarbeit des Autors) litten unter einem Architektur-Engpass: Der Host-CPU musste für jedes Segment ein Sieb (Bitset) konstruieren und dieses über den PCIe-Bus an die GPU übertragen.
• Der Flaschenhals: Bei modernen GPUs waren die Berechnungskerne so schnell, dass sie auf die Datenübertragung von der CPU warteten. Dies führte dazu, dass zusätzliche GPUs keine signifikante Beschleunigung brachten, da das System durch die CPU-Sieb-Erstellung und die PCIe-Latenz limitiert war (I/O-bound), nicht durch die GPU-Rechenleistung.
• Speicherprobleme: Monolithische Speicherung von Primzahlen führte oft zu VRAM-Überlauf, was durch segmentierte Ansätze gelöst wurde, aber die CPU-Abhängigkeit blieb bestehen.

2. Methodik und Architektur

Das Paper stellt eine vollständig geräte-residente (GPU-native) Architektur (GoldbachGPU v2.0) vor, die die Abhängigkeit von der Host-CPU für die kritische Pfad-Berechnung vollständig eliminiert.

• GPU-Natives Segment-Sieben (L1 Shared Memory):

  • Das Sieb-Verfahren wurde vollständig auf die GPU verlagert.
  • Segmente werden in „Tiles" (Kacheln) von 32.768 ungeraden Zahlen unterteilt, die als 4 KB Bitsets in den L1 Shared Memory der GPU geladen werden. Dies passt perfekt in den verfügbaren Speicher moderner Architekturen (Ada Lovelace/Blackwell).
  • Die GPU-Threads sieben diese Kacheln kollaborativ unter Verwendung eines dauerhaft residenten Arrays kleiner Primzahlen.
  • Ergebnis: Es entfallen die großen PCIe-Transfers von Segment-Bitsets. Die CPU sendet nur noch einen 8-Byte-Atomaren Startindex und erhält ein 4-Byte-Ergebnis zurück.

• Lock-Free Work-Stealing Pool:

  • Statt statischer Workload-Partitionierung (die bei heterogener Hardware ineffizient ist) wird ein asynchroner, lock-freier Work-Stealing-Pool implementiert.
  • Ein atomarer 64-Bit-Zähler (g_next_seg_start) im Host-Speicher wird von jedem GPU-Worker-Thread mittels fetch_add angefragt, um das nächste Segment zu beanspruchen.
  • Dies ermöglicht eine automatische Lastverteilung und erreicht nahezu 100% Auslastung aller GPUs, unabhängig von deren Geschwindigkeit.

• Phase-2-Fallback (CPU):

  • Die GPU prüft nur Primzahlen $p \le 10^6$. Falls keine Lösung gefunden wird (was empirisch extrem selten ist), übernimmt die CPU.
  • Die CPU nutzt eine vorkalkulierte Primzahl-Tabelle bis $10^8$ und einen deterministischen Miller-Rabin-Test (12-Basis) für größere Zahlen, um die Korrektheit zu garantieren.

• Sicherheitsgarantien:

  • Strenge mathematische Guard-Klauseln verhindern stille 64-Bit-Überläufe (z. B. durch Divisions-Checks statt Multiplikation).
  • Der Rahmen ist bis zu einer theoretischen Obergrenze von **$1,84 \times 10^{19}$** ($\approx 2^{63.8}$) beweisbar korrekt.

3. Schlüsselbeiträge

1. Eliminierung des Host-Device-Engpasses: Durch die Verlagerung des Sieb-Algorithmus in den GPU-Speicher (L1 Shared Memory) wird die Kommunikation auf ein Minimum reduziert (nur Primzahlen-Listen und ein Zähler).
2. Skalierbarkeit: Die Einführung des lock-freien Work-Stealing-Pools ermöglicht eine nahezu perfekte parallele Effizienz über mehrere GPUs hinweg.
3. Mathematische Korrektheit: Implementierung von 128-Bit-Arithmetik für den Miller-Rabin-Test und strenge Überlauf-Checks, um die Soundness bis zur 64-Bit-Grenze zu gewährleisten.
4. Open-Source-Reproduzierbarkeit: Der Code ist vollständig offen, unterstützt CLI-Parameter für flexible Deployment-Szenarien (z. B. Startwert-Parameter --start für verteilte Jobs) und läuft auf handelsüblicher Hardware.

4. Ergebnisse und Leistung

Die Tests wurden auf einem System mit NVIDIA RTX 5090 GPUs (Blackwell-Architektur) durchgeführt.

• Algorithmische Beschleunigung:

  • Auf identischer Hardware (RTX 5090) erreichte die neue Architektur bei $N = 10^{10}$ eine 45,6-fache Beschleunigung im Vergleich zur vorherigen Version (v1), die noch von der CPU abhängig war.
  • Die Beschleunigung wächst mit $N$, da der I/O-Overhead der alten Architektur proportional zur Anzahl der Segmente anstieg.

• Multi-GPU Skalierung:

  • 2 GPUs: 99,7% parallele Effizienz.
  • 4 GPUs: 98,6% parallele Effizienz.
  • Die GPU-Auslastung war durchgehend nahe 100%, was bestätigt, dass die GPUs nicht auf Daten warten mussten.

• Verifikationszeiten:

  • $10^{12}$: 36,5 Sekunden auf einer einzelnen RTX 5090.
  • $10^{13}$: 133,5 Sekunden auf einem 4-GPU-System.
  • In allen getesteten Bereichen bis $10^{13}$ wurden keine Gegenbeispiele gefunden.

5. Bedeutung und Ausblick

• Paradigmenwechsel: Das Paper beweist, dass die GPU-Verifikation von Goldbach nicht durch Speicherbeschränkungen oder I/O-Latenzen limitiert sein muss, wenn die Architektur vollständig geräte-resident gestaltet wird.
• Rekordverdächtige Skalierung: Es demonstriert erstmals eine effiziente Nutzung von Multi-GPU-Clustern für diese Art von Problem auf Consumer-Hardware, wobei die Skalierungseffizienz extrem hoch ist.
• Zukünftige Arbeiten:
  • Die Obergrenze von $1,84 \times 10^{19}$ ist durch die 64-Bit-Arithmetik und den Miller-Rabin-Test festgelegt. Ein Sprung darüber erfordert 128/256-Bit-Arithmetik und andere Primzahltests (z. B. Baillie-PSW).
  • Potenzielle weitere Optimierungen durch „Bitwise Bulk-Marking" (ähnlich wie bei CPU-Sieves) könnten den Durchsatz weiter steigern.
  • Die Architektur ist bereit für die Verteilung über HPC-Cluster mittels MPI oder Job-Schedulern, da sie bereits durch den --start-Parameter für verteilte Bereiche vorbereitet ist.

Zusammenfassend stellt diese Arbeit einen Meilenstein in der computergestützten Zahlentheorie dar, indem sie zeigt, wie moderne GPU-Architekturen durch geschickte Speicherhierarchie-Nutzung und lock-freie Synchronisation extreme Skalierbarkeit für mathematische Verifikationsaufgaben erreichen können.