pallas-gpu: CUDA MSM for the Pallas Curve

• GPU-accelerated Pippenger MSM for the Pallas elliptic curve
• Four design iterations, each branched in git so you can browse the code at every stage
• Montgomery field arithmetic (CIOS, 8x32-bit limbs) on top of homogeneous projective EFD add-1998-cmo-2 formulas
• Persistent device memory pool, adaptive chunking (4K/16K/32K), Montgomery conversion handled GPU-side
• Plugs into Nova-GPU through a feature-gated MSM trait, leaving the upstream Microsoft Nova codebase otherwise unmodified

Overview

pallas-gpu is the CUDA implementation that backs my thesis. The thesis is the comparative study; this is the engineering artifact. The repository ships as a Rust crate with a CUDA backend, FFI bindings via bindgen, and Criterion benchmarks. Builds against any sm_80+ GPU (Ampere, Ada, Hopper) and integrates with Nova as an optional dependency behind a feature flag.

The Four Versions

Each version lives on its own branch so the design progression is browsable in git, not just narrated. The branches form a hierarchy, not alternatives: V3 wraps V2's kernel chain, and V4 runs an independent V3 pipeline on each device.

V1's bottleneck was a 16.7% SM occupancy ceiling caused by spinlock contention on the RTX 4080. V2 traded that for an O(n log n) sort that the GPU's sort hardware absorbs more efficiently than the spinlock absorbed contention. V3 hid host-to-device latency under kernel execution via concurrent streams. V4 generalised V3 along two axes: a batch API for proof-system-level concurrency (e.g. Nova's L/R commitment pair), and a multi-GPU extension that scales to the workloads a single 80 GB A100 cannot fit.

Architecture

┌─────────────────────────────────────────────────────────────┐
│  Pippenger MSM (pallas_msm.cu)                              │
│  ├── Window decomposition (8-bit, 32 windows)               │
│  ├── Shared-memory bucket accumulation (spinlocks)          │
│  ├── Cross-chunk bucket reduction                           │
│  ├── Bucket reduction (summation by parts)                  │
│  ├── Window combination (double-and-add)                    │
│  ├── Persistent GPU memory pool                             │
│  └── Serial fallback for < 64 points                        │
├─────────────────────────────────────────────────────────────┤
│  Elliptic Curve Operations (pallas_curve.cu)                │
│  ├── point_double      (homogeneous projective, a=0)        │
│  ├── point_add         (EFD add-1998-cmo-2)                 │
│  ├── point_add_mixed   (add-1998-cmo-2, Z2=1)               │
│  └── projective_to_affine (X/Z, Y/Z)                        │
├─────────────────────────────────────────────────────────────┤
│  Field Arithmetic (pallas_field.cu)                         │
│  ├── Montgomery multiplication (CIOS, 8x32-bit limbs)       │
│  ├── Field addition/subtraction (mod p)                     │
│  └── Field inversion (Fermat's little theorem)              │
└─────────────────────────────────────────────────────────────┘

Pallas Curve

Pallas is one half of the Pasta cycle. The two-cycle property is what lets Nova do recursive IVC without expensive non-native field arithmetic, which is why Pallas (rather than BN254 or BLS12-381) is the right MSM target for accelerating Nova specifically.

Nova Integration

The Nova integration is intentionally surgical:

1. src/provider/pallas_gpu.rs (in the Nova-GPU fork) wraps pallas-gpu's msm_u64 API and converts between halo2curves types and the crate's GPU-friendly limb arrays.
2. src/provider/pasta.rs conditionally dispatches MSM to the GPU when the pallas-gpu feature is enabled.
3. Cargo.toml declares pallas-gpu as an optional dependency behind a feature flag.

The rest of Nova is unmodified. Disabling the feature falls back to the CPU MSM path.

Performance

Single-GPU on an NVIDIA GeForce RTX 4080 (76 SMs, 16 GB, Compute 8.9), running the in-crate Criterion benchmark:

These are V1 numbers on a single consumer GPU. The thesis takes the same superstructure through V2/V3/V4 on Hofstra's StarHPC cluster and reaches 17.89x end-to-end on 8x NVIDIA A100 at n = 100M. The thesis writeup has the full cross-platform comparison and platform-selection table.

Tech Stack

• Rust 1.91.1 with FFI bindings to a per-architecture CUDA library compiled in build.rs via nvcc
• CUDA 12.0/12.4, targeting sm_80 (A100), sm_89 (RTX 4080), and sm_90 (H100)
• halo2curves 0.9.0 for Pallas/Vesta curve primitives on the Rust side
• Criterion for benchmarks; built-in unit tests cross-check every kernel against the CPU reference