prime-gap-gpu - a new GPU program to find prime gaps.

A fast prime gap searching tool.

Table of Contents

• Overview
• Setup

Overview

TBD

Setup

In general this is going to be easy under Ubuntu 24.04 or later

$ sudo apt install libgmp10 libgmp-dev
$ sudo apt install build-essential automake autoconf make
# CUDA is required but I'm not sure what apt install that is

$ sudo apt install libmpfr-dev libmpc-dev
$ python -m pip install --user gmpy2

$ git clone https://github.com/sethtroisi/prime-gap-gpu.git
$ cd prime-gap-gpu

make

or

(Not reccomeneded but here for clang-tidy maybe)
cmake -S . -B build -DCMAKE_BUILD_TYPE=RelWithDebInfo -DBITS=512
cd build
make

Misc

valgrind --suppressions=cuda.supp --leak-check=full ./gap_search_gpu -p 337 -d 2310 --mstart 10000000 --minc 200000 --max-prime 1 --min-merit 25 -v -v -v

compute-sanitizer --tool memcheck ./gap_search_gpu -p 151 -d 2310 --mstart 10000000 --minc 200000 --max-prime 1 --min-merit 25

compute-sanitizer --leak-check full ./gap_search_gpu -p 151 -d 2310 --mstart 10000000 --minc 200000 --max-prime 1 --min-merit 25

This has spotted many reads just past the end of composite and other slightly hard to size arrays.

TUNING

• -p prime (AKA log(K))
  • Decreasing means faster PRP and fewer PRP/m so O(n^2) if move below a threshold of 512, 768, 1024 bits.
  • First order effect of decreasing is CPU overflow may bog down more.
• --cpu-fraction
  • Increasing leads to less sparse sieves across X, trades off for more overflow work
  • Should lower (more sieving) till Waiting 4 sieves becomes 5-10%.
  • --cpu-fraction doesn't (significantly) change the total number of PRP tests. It moves PRP tests from main testing thread to overflow thread. This has some change in sieve level (bad) and some decrease in waiting 4 sieves (good).
• OVERFLOW_SIEVE_LIMIT: TODO
  • Trades CPU sieving for GPU time, look at total time : sieve from CPU OVERFLOW Timing
• overflow.cpp: stop_x
  • Increasing leads to less numbers running out of the sieved range (and overflowing to CPU)
  • Decreasing leads to faster sieving.
• max-prime better to increase at some point top primes never run
• minc: TODO add some metric to tune on.
• min-merit math | tuned ~5% past optimal. Reduces overflow by 3x at cost of 4-8% overall efficency.

These are likely set to good values

• OPEN_SIEVES 3-6 is probably great balance of enough unknown count smoothing while minimizing memory usage.
• GPU_BATCHES 2-3, 3 is probably better.
• WINDOW_BITS 4-5, 4 for 256, 5 for 512

Upgrades

• Consider choosing a consistent X to overflow at.
  • Pros:
    • If known before hand might simplify some of the CPU overflow sieve math & tracking
    • Can start sieves for next range ahead of time.
    • Don't have to track sieve_start per overflow
  • Cons:
    • Less dynamic flexibility
• On 2026/09/05 most time was spent in these places:
  • GPU Timing: 275% running, very low waiting 4 sieve, 7% misc, 15% wait done X.
    • Wait done is waiting for other batch to finish and possibly push_to_overflow.
  • GPUSieve
    • 4% wheel2, 9% small, 50% medium, 25% large, 15% copy.
  • CPUSieve
    • 16% spent in finalize, optimized from 40% with bitset, not sure how to improve.
    • This is mostly CPU time but could help reduce "wait 4 sieve" and possibly "wait done"
  • Overflow:
    • 1.8% overflow, 0.97% tested both sides
    • 99% of tests on GPU, 1% on CPU
    • 50% Sieve, 25% GPU misc, 10% GPU running
    • Using --cpu-threads=3 but averaging <2 running.
    • ~5% of total prime test.

TODO

• Test not doing tests->push_back(m_i) at gap_search_gpu.cpp 870.
• Over 4 days I leaked something like 30GB of RAM. I'd like to find where!

TODONE

• Wheel for divisors of d.
• Check a small percent of next_primes are actually prime
• Understand what sieve limit gmp is using for overflow
  • GMP is sieving to ~4M -> 10% less efficient
• Try changing vector<uint8_t> to vector<uint32_t>
  • This didn't seem to have any impact on speed, but I was told it might help in reduce mixed cache line access (8 vs 32 vs 64) control so I'll keep it.
• Offload overflow probab_prime back to the GPU
  • Sieve each m range, keep batch of these sieves
  • Make a GPUBatch of sieves and current index into coprime_X
• Converted active_m_i to bitset and do bitset operations instead of pushing to vectors.
• Sieve both next and prev primes in overflow.
  • freed up 3+ CPU cores
  • Allows for setting lower min_gap_to_continue which is ~5% more optimal.
• Understand why some X=12 have twice as many unknowns?
  • m * K % 3 is 1 or 2; and doesn't remove any factors from X=12
  • When X % 3 == 0 you end up with twice as many factors.
  • With X % 3 == {1, 2} half of factors get removed by 3, (1/4 with 5, 1/6 with 7)