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

This paper presents a fully device-resident, multi-GPU architecture that achieves near-zero host-device communication and 99.7% parallel efficiency through lock-free work-stealing and optimized shared-memory tiling, enabling the verification of Goldbach's conjecture up to $10^{13}$ in just 133.5 seconds on a four-GPU system with a 45.6× speedup over previous methods.

The Gist

Here is an explanation of the paper, translated from "academic speak" into everyday language using analogies.

The Big Picture: What are they trying to do?

Imagine a massive, infinite library where every book represents an even number (4, 6, 8, 10, etc.). A famous math puzzle called Goldbach's Conjecture claims that every single one of these books can be opened to find two "prime number" pages that add up to the book's number.

For example:

• Book #10 = Page 3 + Page 7 (Both are prime).
• Book #100 = Page 3 + Page 97.

Mathematicians have checked this up to huge numbers, but they want to go even higher. The problem is that checking these numbers one by one takes a long time. This paper is about building a super-fast, automated factory to check these books as quickly as possible.

The Old Factory (Version 1.0): The "Conveyor Belt" Problem

In the author's previous work, they built a factory using powerful computer chips called GPUs (the brains of video games and AI).

• The Setup: The GPU was the super-fast worker. The CPU (the main computer brain) was the manager.
• The Bottleneck: The manager (CPU) had to write down a list of "prime numbers" for every single batch of books, hand it to the worker (GPU), wait for the worker to finish, take the list back, write a new one, and hand it over again.
• The Analogy: Imagine a Formula 1 race car (the GPU) that can drive at 200 mph. But, every time it finishes a lap, it has to stop at the pit lane, wait for a mechanic (the CPU) to change the tires, and then wait for the mechanic to hand it a new map. Even though the car is fast, it spends 90% of its time sitting in the pit lane waiting. Adding more race cars didn't help because the mechanic was the slow part, not the cars.

The New Factory (Version 2.0): The "Self-Driving" Revolution

This new paper introduces a completely redesigned factory where the workers don't wait for the manager anymore.

1. The "Self-Contained" Worker (GPU-Native Sieving)

Instead of the manager handing over a list of primes, the workers now have a tiny, super-fast notebook (called L1 Shared Memory) built right into their workspace.

• The Change: The worker can now write their own list of primes, check the books, and move to the next batch instantly.
• The Result: The "pit stop" is gone. The race car never stops. It just drives. This made the process 45 times faster than before.

2. The "Free-for-All" Work Queue (Lock-Free Work-Stealing)

In the old system, the manager assigned specific batches to specific workers. If one worker was slightly slower (maybe their coffee was cold, or their chip was a bit older), the whole factory had to wait for them.

• The New System: Imagine a pile of unsorted books in the middle of the room. Any worker who finishes their current task just grabs the next available pile. If a worker is fast, they grab more. If they are slow, they grab fewer.
• The Result: No one stands around waiting. The system automatically balances itself. The paper shows that with 4 workers, the factory runs at 98.6% efficiency (almost perfect).

3. The "Safety Net" (Overflow Guards)

When you count to numbers as big as $10^{19}$ (that's a 1 followed by 19 zeros!), regular computer math can get confused and wrap around, like a car odometer rolling from 999,999 back to 000,000.

• The Fix: The author built strict "mathematical seatbelts." If the numbers get too big for the computer's standard math, the system switches to a special "128-bit" mode to ensure the count never lies. They proved the system is safe up to a specific ceiling ($1.84 \times 10^{19}$).

The Results: How Fast is it?

The author tested this new system on the latest, most powerful graphics cards (NVIDIA RTX 5090s).

• The Old Way: Checking numbers up to $10^{10}$ took a long time.
• The New Way: It does the same job 45 times faster.
• The Record:
  • One super-computer card checked up to 1 trillion ($10^{12}$) in just 36 seconds.
  • Four cards working together checked up to 10 trillion ($10^{13}$) in just 2 minutes and 13 seconds.

Why Does This Matter?

1. It's Open Source: The author didn't keep the secret. Anyone with a decent gaming PC can download the code and run these checks.
2. It Solves a Hardware Problem: It proves that you don't need a million-dollar supercomputer to do massive math; you just need to stop the computer from waiting on itself.
3. It's a Stepping Stone: While they haven't proven Goldbach's Conjecture (which is a math proof, not just a check), they have pushed the boundary of what we can verify further than ever before, giving mathematicians more confidence that the rule holds true.

Summary Analogy

Imagine trying to paint a massive wall.

• Version 1: You have a team of painters, but one person has to run back and forth to the supply closet to get paint for every single brushstroke. The painters are fast, but the runner is slow.
• Version 2: You give every painter their own personal, infinite supply of paint right in their pocket. They also have a system where they just grab the next empty patch of wall whenever they are free.
• Outcome: The wall gets painted in a fraction of the time, and adding more painters actually makes a difference because no one is waiting for the supply closet.

Technical Summary

Here is a detailed technical summary of the paper "A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture."

1. Problem Statement

Goldbach's conjecture posits that every even integer greater than 2 is the sum of two prime numbers. While verified up to $4 \times 10^{18}$ using distributed CPU clusters, scaling this verification further requires overcoming significant computational bottlenecks.

The author's prior work (GoldbachGPU v1) successfully addressed VRAM limitations by using a segmented sieve, reducing memory footprint to a constant 14 MB. However, this architecture introduced a new critical bottleneck: Host-Device I/O Latency.

• In v1, the CPU constructed the prime bitset for each segment and transferred it to the GPU via PCIe.
• On modern high-bandwidth GPUs, the verification kernel completed in fractions of a millisecond, leaving the GPU idle while waiting for the CPU to prepare the next segment.
• This made the system I/O-bound rather than compute-bound, preventing effective scaling across multiple GPUs (e.g., adding a second GPU yielded no speedup).

2. Methodology: GoldbachGPU v2.0

The paper proposes a fully device-resident, lock-free architecture that eliminates the host CPU from the critical verification path. The system is designed for heterogeneous multi-GPU clusters.

A. GPU-Native Segment Sieving (L1 Shared Memory)

Instead of the CPU generating segment bitsets, the sieve generation is migrated entirely to the GPU:

• Tiled Sieve: Segments are divided into tiles of 32,768 odd numbers (4 KB bitsets).
• L1 Optimization: These tiles are loaded directly into the GPU's L1 shared memory (48 KB per SM on Ada/Blackwell architectures).
• Process: GPU threads collaboratively sieve the tiles using a permanently resident, read-only array of base primes. Results are flushed to global VRAM.
• Impact: This eliminates the variable 14 MB PCIe transfer per segment. The host now only transfers a constant ~628 KB batch of small primes and receives a 4-byte result.

B. Lock-Free Asynchronous Work-Stealing Pool

To maximize multi-GPU efficiency, the system replaces static workload partitioning with a dynamic, lock-free approach:

• Atomic Claiming: A single 64-bit atomic counter (g_next_seg_start) in host memory tracks the next segment to process.
• Work-Stealing: Each GPU worker thread (one per physical GPU) performs an atomic fetch_add to claim the next segment.
• Benefits: This automatically balances load across GPUs with varying performance (due to thermal throttling or silicon binning) and achieves near-100% device utilization without mutex contention.

C. Zero-Copy Fast Path & Phase 2 Fallback

• Phase 1 (GPU): The GPU checks if $n = p + q$ for candidate primes $p \le 10^6$.
• Reduction: A device-side kernel counts "unverified" numbers.
• Fast Path: If the count is zero (which happens for all tested ranges), the result is a 4-byte scalar. No large data transfer occurs.
• Phase 2 (CPU Fallback): If unverified numbers exist, a PCIe transfer occurs, and the host CPU resolves them using a precomputed prime array and a 128-bit deterministic Miller-Rabin test. In practice, this phase is never invoked for $N \le 10^{13}$.

D. Mathematical Soundness & Safety

• Overflow Guards: Strict division-based guards prevent 64-bit integer overflow during sieve arithmetic (e.g., $p^2$ calculations).
• Deterministic Primality: The system uses a 12-witness deterministic Miller-Rabin test, proven correct for all $n < 2^{64}$.
• Upper Bound: The framework is mathematically sound up to $1.84 \times 10^{19}$(approx.$2^{63.8}$). Beyond this, 128-bit intermediate products would overflow, and the witness set guarantees no longer apply.

3. Key Contributions

1. Elimination of Host-Device Bottleneck: By moving the sieve generation to GPU L1 shared memory, the architecture shifts from I/O-bound to compute-bound, enabling true multi-GPU scaling.
2. Lock-Free Multi-GPU Scaling: Introduction of an atomic work-stealing pool that achieves >98% parallel efficiency across 4 GPUs, overcoming the "straggler" problem inherent in static partitioning.
3. Algorithmic Speedup: A 45.6× speedup over the previous host-coupled version at $N=10^{10}$ on identical hardware.
4. Record-Breaking Verification: Verification of Goldbach's conjecture up to $10^{13}$ in 133.5 seconds using a 4-GPU system (RTX 5090).
5. Open-Source Reproducibility: Full code availability with CLI support for flexible range partitioning across distributed nodes.

4. Results

Experiments were conducted on NVIDIA RTX 5090 GPUs (Blackwell architecture) using CUDA 12.8.1.

• Single GPU Performance:
  • Verified $10^{12}$ in 36.5 seconds.
  • Verified $10^{13}$in **365 seconds** (extrapolated from scaling data, actual 4-GPU run took 133.5s for$10^{13}$).
• Multi-GPU Scaling (at $N = 2 \times 10^{12}$):
  • 1 GPU: 80.87s
  • 2 GPUs: 40.55s (99.7% Parallel Efficiency)
  • 4 GPUs: 20.51s (98.6% Parallel Efficiency)
• Communication Overhead:
  • Host-to-Device transfer: ~0.628 MB per segment (constant).
  • Device-to-Host transfer: ~4 bytes per segment (scalar result).
  • Total D2H traffic for the entire run: 20 KB.
• Thermal Stability: Profiling showed minimal frequency throttling (<1.0% reduction) even during long single-GPU runs, with 4-GPU runs completing quickly enough to avoid significant thermal accumulation.

5. Significance

This work represents a paradigm shift in computational number theory verification on GPUs:

• Architectural Maturity: It demonstrates that GPUs can be fully self-sufficient for complex sieve operations, removing the dependency on CPU orchestration that previously limited scalability.
• Scalability: The lock-free design proves that heterogeneous GPU clusters can achieve near-linear scaling for this class of problems, a feat previously unattainable due to PCIe latency.
• Future Frontier: By pushing the verified limit to $10^{13}$in minutes (compared to years for CPU clusters) and establishing a soundness ceiling of$1.84 \times 10^{19}$, the framework sets a new baseline for empirical verification.
• Extensibility: The modular design (CLI --start flag) allows for easy distribution across HPC clusters, and the paper outlines clear paths for future work, such as bitwise bulk-marking kernels and 256-bit arithmetic to break the $2^{64}$ ceiling.

In summary, the paper successfully transforms Goldbach verification from a CPU-limited, I/O-bound task into a highly efficient, fully GPU-resident computation, achieving massive speedups and near-perfect parallel efficiency.