CUDA Implementation of Brent's Algorithm

Master's project: parallelizing Brent's root-finding method on NVIDIA GPU via batch/ensemble parallelism. Each thread runs an independent Brent's instance on a different (function, parameter) tuple.

Hardware target

• NVIDIA RTX 3080 (Ampere, SM 8.6, fp64 1:64 ratio vs fp32)
• CUDA Toolkit 13.1, NVIDIA driver 591.74
• WSL2 Ubuntu 24.04, gcc 13.3, CMake 3.28

Build

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j

Binaries land in build/bin/:

• cpu_test: single-case CPU smoke test
• gpu_test: single-case GPU smoke test
• test_correctness: full correctness battery (used by ctest)
• bench_m1: benchmark sweep harness

Compile flags pinned for CPU/GPU bit-identical fp64: -ffp-contract=off (g++) and --fmad=false (nvcc).

Run correctness tests

ctest --test-dir build --output-on-failure

Registered tests:

• small_battery_cpu: 22 hand-crafted cases on CPU
• small_battery_gpu: 22 hand-crafted cases on GPU + |gpu - cpu| gate
• random_battery: 16384 random monotonic cubics on CPU and GPU
• edge_cases: tight bracket / pre-converged / just-barely-bracket cases on CPU and GPU

Hard pass criteria (all must hold per case):

• |cpu_root - r_true| < 1e-10
• |gpu_root - r_true| < 1e-10
• |gpu_root - cpu_root| < 1e-10
• cpu_converged == gpu_converged == true

Soft signals (logged, not gated): |cpu_root - python_root|, iter_count_delta.

Run the benchmark sweep

./build/bin/bench_m1

Sweeps batch sizes {2^10, 2^14, 2^18, 2^20, 2^22} for both cpu_baseline and gpu_v1_naive, 3 warmup + 10 measured trials per cell, with automatic retry-once on CV > 5%. Writes benchmarks/results/m1.csv with environment header and per-trial rows.

Calibration mode (empty-kernel launch overhead):

./build/bin/bench_m1 --noop-only

Demo

demo.sh launches cpu_test and gpu_test side-by-side in a synchronized tmux session so the speedup is visible in real time. Both panes are queued with the same batch size and the same RNG seed, and one Enter keystroke fires both at once.

./demo.sh                          # default batch 2^22
./demo.sh --batch 16777216         # any --batch N is passed through to both

Requires tmux (sudo apt install tmux on WSL2/Ubuntu) and a successful build (cpu_test and gpu_test must exist in build/bin/).

Inside the session: press Enter once to start both runs, watch the GPU pane print its DONE banner while the CPU pane is still showing progress ticks, then press Enter again to close the panes.

Regenerate Python goldens + bench inputs

The C++ correctness battery and bench harness consume CSV (goldens) and binary (bench inputs) files generated from the Python reference. After modifying python_reference/main.py, regenerate:

cd python_reference
uv sync                  # one-time: install numpy + matplotlib
uv run python main.py    # writes tests/batches/golden_*.csv and bench_inputs_2^N_*.bin

The binary bench_inputs_2^N_*.bin files are gitignored (~192 MB at 2^22) and are regenerated on demand.

Repository layout

src/
  common/include/         # cuda_check, cubic_eval, types: shared headers
  cpu_baseline/           # single-threaded C++ Brent's
  cuda_v1_naive/          # naive GPU port
benchmarks/
  bench_m1.cpp            # sweep harness
  results/                # CSV outputs (committed)
tests/
  test_correctness.cpp    # correctness battery
  batches/                # goldens (committed) + bench .bin (gitignored)
python_reference/
  brent.py                # ground-truth Python implementation
  main.py                 # generates goldens + bench inputs
docs/                     # final report, slides, project journal

Headline result

Median across 10 trials on RTX 3080 at 2^22 batch: 8.79x total runtime speedup over the single-threaded CPU baseline, with the kernel itself running 35.31x faster than the CPU baseline.