[Bug] CUDA MSM dispatch selects a slower path for 1,025-8,192 points on RTX 5090

[peter941221]

Bug Report

VariableBase::msm tries CUDA when the BLS12-377 MSM has more than 1,024 scalars (dispatch site). On my RTX 5090, the CPU batched::msm path is faster than a successful direct CUDA call from 1,025 through 8,192 points. This is a performance issue, not a proof-correctness failure or a claim that CUDA is generally slower.

Changing only the local dispatch cutoff from > 1024 to > 8192 reduced median VarunaInst::prove time for one fixed Varuna V2 test circuit from 329.929 ms to 304.101 ms (21 repetitions per condition, 7.8%). Both conditions produced proofs that verified. The cutoff was restored after the experiment; I am not proposing 8,192 as a universal default.

Steps to Reproduce

1. Check out staging at 2c8839400e711a8085c1cb887a749c2c47848aba on a CUDA-capable machine. Use the repository-pinned Rust toolchain. On my machine CUDA Toolkit 12.8 builds; CUDA 13.0 hits a separate sm_70 build error.

2. Confirm the current CUDA MSM correctness test passes:

   NVCC=/usr/local/cuda-12.8/bin/nvcc cargo test -p snarkvm-algorithms --features cuda --lib test_msm_cuda --release --locked --no-fail-fast

3. Put the msm5090.rs reproducer included below at algorithms/examples/msm5090.rs and run:

   NVCC=/usr/local/cuda-12.8/bin/nvcc MSM_SEED=5090 MSM_REPEATS=21 cargo run --release --locked -p snarkvm-algorithms --example msm5090 --features cuda

   It fixes the input seed, warms each path once, times 21 calls, and compares CPU, direct snarkvm_algorithms_cuda::msm, and public VariableBase::msm outputs in affine form. The direct call makes a silent CPU fallback distinguishable from a successful CUDA call. All reported outputs matched; direct CUDA returned success at every measured size.

   Scalars	CPU batched	Direct CUDA	Public dispatch
   1,024	5.811 ms	19.422 ms	8.005 ms
   1,025	7.992 ms	16.263 ms	19.408 ms
   2,048	7.379 ms	22.902 ms	20.604 ms
   4,096	10.820 ms	19.476 ms	22.163 ms
   8,192	13.770 ms	20.857 ms	23.153 ms
   16,384	26.557 ms	25.219 ms	24.301 ms
   65,536	75.416 ms	34.897 ms	35.979 ms

4. For proving impact, put the varuna_prove5090.rs reproducer included below at algorithms/examples/varuna_prove5090.rs. It uses the repository's Varuna benchmark test-circuit shape: 10,000 constraints, 2,500 variables, multiplication depth 100, Varuna V2. It times only prove, outside SRS and circuit setup, then verifies the proof. Run the command below on the original source, then change just the MSM cutoff to > 8192, rerun, and restore it:

   NVCC=/usr/local/cuda-12.8/bin/nvcc PROVE_REPEATS=21 cargo run --release --locked -p snarkvm-algorithms --example varuna_prove5090 --features test,cuda

   Local cutoff	Median prove time	Proof verified
   Original > 1024	329.929 ms	Yes
   Experimental > 8192	304.101 ms	Yes

These are sequential rather than interleaved A/B runs on one WSL2 machine. The measured workload is a synthetic Varuna proof, not a credits.aleo/transfer_private transaction. The existing transaction proving benchmark would be useful for a real-transaction follow-up. No kernel-only or transfer-only timing is claimed.

Expected Behavior

The dispatch decision should not systematically select a substantially slower path for a range of MSM sizes on supported hardware. A useful next step would be a benchmark around the 1,024-point boundary and discussion of a device-aware or configurable cutoff; the correct policy needs data from more GPUs and workloads. I can contribute the two reproducers and measurements.

Environment

• snarkVM staging commit 2c8839400e711a8085c1cb887a749c2c47848aba; release build with --locked
• Ubuntu 24.04 under WSL2; Intel Core Ultra 7 270K Plus, 16 logical CPUs
• GeForce RTX 5090, compute capability 12.0, 32 GB VRAM, driver 617.14
• CUDA Toolkit 12.8.93 (nvcc); repository-pinned Rust 1.96
• Fixed input seed 5090; one warm-up and 21 timed calls per MSM size/condition

Reproducer source

algorithms/examples/msm5090.rs:

use snarkvm_algorithms::msm::{VariableBase, variable_base::batched};
use snarkvm_curves::{ProjectiveCurve, bls12_377::{Fr, G1Affine, G1Projective}};
use snarkvm_fields::PrimeField;
use snarkvm_utilities::{Uniform, rand::TestRng};
use std::{hint::black_box, time::Instant};

fn median_us(mut samples: Vec<u128>) -> u128 {
    samples.sort_unstable();
    samples[samples.len() / 2]
}

fn time_repeated<T>(mut operation: impl FnMut() -> T, repeats: usize) -> (u128, T) {
    let mut samples = Vec::with_capacity(repeats);
    let mut result = operation(); // Warm-up, including CUDA context setup.
    for _ in 0..repeats {
        let start = Instant::now();
        result = black_box(operation());
        samples.push(start.elapsed().as_micros());
    }
    (median_us(samples), result)
}

fn main() {
    let repeats = std::env::var("MSM_REPEATS").ok().and_then(|s| s.parse().ok()).unwrap_or(7);
    assert!(repeats > 0);
    println!("size,path,median_us,status");
    let seed = std::env::var("MSM_SEED").ok().and_then(|s| s.parse().ok()).unwrap_or(5090);
    eprintln!("MSM_SEED={seed} MSM_REPEATS={repeats}");
    let mut rng = TestRng::from_seed(seed);
    for size in [512, 1024, 1025, 2048, 4096, 8192, 16384, 65536] {
        let bases: Vec<G1Affine> = (0..size).map(|_| G1Affine::rand(&mut rng)).collect();
        let scalars: Vec<<Fr as PrimeField>::BigInteger> =
            (0..size).map(|_| Fr::rand(&mut rng).to_bigint()).collect();

        let (cpu_us, cpu) = time_repeated(|| batched::msm(&bases, &scalars), repeats);
        println!("{size},cpu_batched,{cpu_us},ok");

        // Bypass VariableBase's silent CPU fallback.
        let direct = snarkvm_algorithms_cuda::msm::<G1Affine, G1Projective, <Fr as PrimeField>::BigInteger>(
            &bases, &scalars,
        );
        match direct {
            Ok(first) => {
                if first.to_affine() != cpu.to_affine() {
                    println!("{size},cuda_direct,0,MISMATCH");
                    continue;
                }
                let (gpu_us, gpu) = time_repeated(
                    || snarkvm_algorithms_cuda::msm::<G1Affine, G1Projective, <Fr as PrimeField>::BigInteger>(
                        &bases, &scalars,
                    ),
                    repeats,
                );
                let status = match gpu {
                    Ok(result) if result.to_affine() == cpu.to_affine() => "ok",
                    Ok(_) => "MISMATCH",
                    Err(_) => "ERROR_AFTER_WARMUP",
                };
                println!("{size},cuda_direct,{gpu_us},{status}");
            }
            Err(error) => println!("{size},cuda_direct,0,ERROR_CODE:{}", error.code),
        }

        let (dispatch_us, dispatch) = time_repeated(|| VariableBase::msm(&bases, &scalars), repeats);
        let status = if dispatch.to_affine() == cpu.to_affine() { "ok" } else { "MISMATCH" };
        println!("{size},public_dispatch,{dispatch_us},{status}");
    }
}

algorithms/examples/varuna_prove5090.rs:

use snarkvm_algorithms::{
    AlgebraicSponge, SNARK,
    crypto_hash::PoseidonSponge,
    snark::varuna::{TestCircuit, VarunaHidingMode, VarunaSNARK, VarunaVersion, ahp::AHPForR1CS},
};
use snarkvm_curves::bls12_377::{Bls12_377, Fq, Fr};
use snarkvm_utilities::TestRng;
use std::{hint::black_box, time::Instant};

type FS = PoseidonSponge<Fq, 2, 1>;
type VarunaInst = VarunaSNARK<Bls12_377, FS, VarunaHidingMode>;

fn main() {
    let repeats = std::env::var("PROVE_REPEATS").ok().and_then(|s| s.parse::<usize>().ok()).unwrap_or(7);
    assert!(repeats > 0);
    let mut rng = TestRng::from_seed(5090);
    let max_degree = AHPForR1CS::<Fr, VarunaHidingMode>::max_degree(1000, 1000, 1000).unwrap();
    let universal_srs = VarunaInst::universal_setup(max_degree).unwrap();
    let universal_prover = universal_srs.to_universal_prover().unwrap();
    let fs_parameters = FS::sample_parameters();
    let (circuit, public_inputs) = TestCircuit::gen_rand(100, 10_000, 2_500, &mut rng);
    let (proving_key, verifying_key) = VarunaInst::circuit_setup(&universal_srs, &circuit).unwrap();

    let mut samples = Vec::with_capacity(repeats);
    let mut last_proof = None;
    for iteration in 0..=repeats {
        let start = Instant::now();
        let proof = VarunaInst::prove(
            &universal_prover,
            &fs_parameters,
            &proving_key,
            VarunaVersion::V2,
            &circuit,
            &mut rng,
        ).unwrap();
        black_box(&proof);
        if iteration != 0 { samples.push(start.elapsed().as_micros()); }
        last_proof = Some(proof);
    }
    let universal_verifier = universal_srs.to_universal_verifier().unwrap();
    assert!(VarunaInst::verify(
        &universal_verifier,
        &fs_parameters,
        &verifying_key,
        VarunaVersion::V2,
        public_inputs.as_slice(),
        &last_proof.unwrap(),
    ).unwrap());
    samples.sort_unstable();
    println!("varuna_v2_prove_constraints=10000_variables=2500_repeats={repeats}_median_us={}_verified=true", samples[repeats / 2]);
}