# Form A Day-2 progress — Montgomery batch inversion landed correctly but regressed throughput

Status: **STOPPED, no commit.** v2 kernel validates byte-identically against coincurve through n=1M but runs slower than Day-1 v1 across all tested batch sizes on 3090.

## What shipped (uncommitted, working tree)

`secp256k1-batch-mul.cu` now carries two kernel variants:

- `secp_mul_batch_kernel_v1` (renamed from `secp_mul_batch_kernel`) — Day-1 path, per-thread `_ModInv`.
- `v2_phase_a` / `v2_phase_b` / `v2_phase_c` / `v2_phase_d` — 4-launch Montgomery batch inversion pipeline.

CLI gates v2 via `--batch-inv` (default ON) or `--no-batch-inv` (selects v1). Stderr labels each run `[v1-per-thread-inv]` or `[v2-batch-inv]`.

## Algorithm landed correctly

Block decomposition: K = ceil(n / B) where B = 256.

1. **Phase A** (full-parallel, N threads): per-thread scalar_mul, writes (Jx, Jy, Jz) to global scratch `jac[n*12]`; writes effective z[i] = Jz (or 1 for infinity) to scratch `z[n*4]`.
2. **Phase B** (1 thread/block, K blocks): per-block prefix product c[i] = z[base..i] mod p; writes block_prod[b] = c[end-1].
3. **Phase C** (single thread total): walks left-to-right computing G_left[b] = product of block_prod[0..b-1]; one `_ModInv` on the global product G; walks right-to-left to produce u_entry[b] = (block_prod[0..b])^-1.
4. **Phase D** (1 thread/block, K blocks): walks each block backward i = end-1..base, computing z_inv[i] = u * c_global[i-1] where c_global[i-1] = G_left[b] * c[i-1] for i > base, else G_left[b] (b > 0) or 1 (b == 0); updates u *= z[i]; finishes affine projection (Zi^2, Zi^3, Ax, Ay); emits BE bytes.

## Validation — passes byte-identical

Coincurve oracle on 3090-ai (after `python3 -m venv ~/venv-secp && ~/venv-secp/bin/pip install coincurve`):

```
n=8 known-small             PASS
n=32 random                 PASS
n=1000 random               PASS
n=10000 random              PASS
n=100000 random             PASS
n=1000000 random            PASS
```

Math is correct. The "STOPPED" condition is throughput, not correctness.

## Throughput — v2 regresses across all N

Three runs each on 3090-ai, kernel ms reported by the worker:

| n       | v1 Mkeys/s | v1 kernel ms | v2 Mkeys/s | v2 kernel ms | v2 / v1 |
|---------|------------|--------------|------------|--------------|---------|
| 10,000  | 4.37       | 2.29         | 2.76       | 3.62         | 0.63x   |
| 100,000 | 7.43       | 13.47        | 5.97       | 16.74        | 0.80x   |
| 1,000,000 | 7.88     | 126.85       | 7.39       | 139.42       | 0.94x   |

(Note: today's measured Day-1 baseline at n=1M is 7.88 Mkeys/s — higher than the 6.51 Mkeys/s cited in the task prompt. v1 was re-benchmarked on the same box in the same session.)

## Root cause

`_ModInv` on a 3090 is not the bottleneck at this n. v1 already saturates at ~7.9 Mkeys/s at n=1M because **scalar_mul** dominates the kernel: 256 Jacobian doubles + ~128 adds per scalar, each calling 5-6 `_ModMult` / `_ModSqr`. That's ~2000 field mults per scalar in scalar_mul vs ~20-30 field mults amortized for the inversion. Replacing _ModInv with batch inversion saves a small fraction of total work.

The v2 implementation as designed makes the situation worse because:

- Phase B and Phase D use **1 thread per block** (block size 256). At n=1M that's 3906 active threads vs v1's 1M threads. 3090 has 82 SMs × 1536 max-resident-threads = ~125k concurrent threads; v2 leaves >97% of SM throughput idle in the prefix and suffix passes.
- Per-block serial walk in Phase D performs ~256 ModMult4 calls sequentially per thread; v1 spreads ModInv (~20-30 ModMult-equivalent ops) across all N threads in parallel.
- v2 adds ~120 MB of device scratch (`jac`, `z`, `c`, `block_prod`, `G_left`, `u_entry`) at n=1M plus extra kernel launches.

## What v2 needs to become a win

Two non-obvious follow-ups, neither in scope today:

1. **Warp-level prefix scan inside Phase B + suffix walk in Phase D.** Use Kogge-Stone or Sklansky scan with 32 threads/warp on the prefix product. At n=1M with B=256, each warp scans 8 elements — turns the serial 256-mult chain into 8 mults of warp-coordinated work. Block_size could grow to 1024 (warp == 32, scan 32 elements/warp).
2. **Move scalar_mul to a windowed ladder (precomputed G, 2G, ..., 256G).** Cuts scalar_mul cost ~4x and shifts the kernel's bottleneck onto inversion, where batching actually wins. Upstream `GPUGroup.h` carries the precomputed tables — vendoring that header is the Day-3+ move flagged in the original plan §2.

Neither follow-up was in the Day-2 mandate. Logical halt point.

## Files touched (uncommitted, in working tree)

- `examples/cuda-fanout/secp256k1-batch-mul.cu` — split v1/v2 kernels, added `--batch-inv` flag, v2 default-ON in flag wiring (but never reached commit because throughput failed).

## Rebuild + revert path

```
ssh 3090-ai.foxhop.net 'cd /home/fox/git/lumbda/examples/cuda-fanout && rm -f secp256k1-batch-mul && make secp256k1-batch-mul'
git -C ~/git/lumbda checkout -- examples/cuda-fanout/secp256k1-batch-mul.cu   # if reverting
```

Day-1 binary @ commit 7661788 stays canonical until Day-3 lands either the warp-scan inner kernel or the windowed-ladder scalar_mul.
