# Form E — `cuda-bernstein-yang-inv` progress doc

Status: **DAY-1 SEQUENTIAL DESIGN LOSES — DO NOT PROMOTE**.

Decision point reached 2026-06-05. Halt rule from spec (HARD RULES,
"If 0x0A fails to outperform 0x05 by ≥ 5x at n=100k, STOP") tripped.
Implementation builds clean, byte-identity holds across all N, but
the kernel-time win does not exist. Document landed before any commit.

## What we built

Added op_id `0x0A mod-inv-batch` to `cgbn-batch-worker.cu` as a
Montgomery batched-inversion (the textbook 1 inv + 3(N-1) muls
trick). Shape: same BCGB wire payload as 0x05 (16 B header + 32 B
modulus + n × 32 B xs → 12 B header + n × 32 B inverses). New kernel
`mod_inv_batch_256_kernel` runs as **one cooperating CGBN instance
(TPI=8 threads, 1 block)** sweeping the n inputs sequentially through:

1. forward sweep building prefix products t[i] = t[i-1] * x[i] mod m
2. one `cgbn_modular_inverse` on t[n-1]
3. reverse sweep yielding result[i] from u and t[i-1]

Allocates an n-sized scratch buffer d_t on device. Op classified as
FAMILY_UN_MOD so the payload-size validator already accepted it.

Test harness `test_cgbn_known_answers.py` gained driver
`driver_mod_inv_batch` reusing the existing unary-with-modulus
template, `ensure_invertible=True`, gmpy2 reference. Default N sweep
extended to include 100k.

## Validation result — byte-identity PASSES

Built on 3090-ai (sm_86) clean, no warnings. Built on ai (sm_89)
clean, no warnings.

Test on 3090-ai:

```
PASS  mod-inv-batch secp256k1 prime   n=32
PASS  mod-inv-batch secp256k1 prime   n=1000
PASS  mod-inv-batch secp256k1 prime   n=10000
PASS  mod-inv-batch secp256k1 prime   n=100000
ALL PASS
```

All four N values produce result bytes identical to gmpy2's per-element
`invert(x[i], m)`. The algorithm is correct.

## Benchmark result — 0x0A LOSES TO 0x05

Bench harness `/tmp/bench_inv_batch.py` parses `kernel=X.XXms` from
worker stderr, single-shot per N, secp256k1 prime modulus.

3090-ai (RTX 3090):

| N         | 0x05 mod-inv kernel-ms | 0x0A inv-batch kernel-ms | ratio (0x05 / 0x0A) |
|-----------|-----------------------:|--------------------------:|--------------------:|
| 10,000    |                  0.520 |                    78.340 |               0.01× |
| 100,000   |                  2.540 |                   762.280 |               0.00× |
| 1,000,000 |                 21.100 |                  7763.450 |               0.00× |

Spec required ≥ 5× speedup at n=100k. We measure **~300× slowdown**.

## Why the day-1 design lost

The spec's premise was that 0x05 mod-inv runs at "42 Mops/s" and that
a single-thread sequential walk doing only modmuls would beat N
parallel mod-invs. Both halves of that premise turn out wrong on a
3090 with our existing parallel kernel:

- The existing parallel 0x05 hits ~**40 Gops/s** at n=1M (1e6 / 21.1
  ms ≈ 47 Mops/s — wait, that matches the spec, but 0x0A at n=1M
  costs 7.7 s for 3(N-1) ≈ 3M muls = 0.39 Mmuls/s on one CGBN
  instance). A single TPI=8 lockstep instance running sequentially is
  ~5 orders of magnitude slower than the SM-saturated kernel at the
  parallel modmul rate. We bought one inversion (saved ~21 ms / 1M
  inversions = ~21 ns each) at the cost of doing 3(N-1) muls
  sequentially through one 8-thread group that has no
  pipeline / overlap.
- Phase 1 / Phase 3 each carry a strict data dependency chain
  (t[i] depends on t[i-1]; reverse sweep on u and t[i-1]). With
  zero parallelism inside the chain, we are bound by latency × n,
  not throughput. 3 sequential modmuls × n at single-instance
  latency dominates.
- The existing 0x05 path **already amortises** through CGBN's
  parallel cooperative groups; it is not the per-inversion cost
  that hurts, it is N independent inversions getting pipelined
  across 82 SMs × 128 in-flight instances.

The arithmetic in the spec ("single thread 100k modmuls at ~0.005 µs
each = ~500 µs") assumed CGBN modmul on a single instance retires
at the device modmul rate. It does not — each mul-wide + rem-wide is
hundreds of warp-cycles of cooperative work bound by chain latency,
not by the kernel's aggregate throughput.

## What would actually win

Two pivots survive analysis:

1. **Per-block prefix scan.** Split the n inputs into B blocks of
   ~256 each. Within each block, a warp does a parallel scan of
   modmuls (log(B) depth instead of B). Cross-block reduction is
   sequential but only B steps. At n=100k with B=256, depth becomes
   ~log2(256) + 391 ≈ 399 sequential modmul-equivalents instead of
   100k. Phase 3 mirrors. This is the next implementation; spec
   already flagged it as the fall-back ("If you want to chase more,
   do per-block prefix scan next").
2. **True Bernstein-Yang safegcd CUDA kernel** — the original
   catalog target. Per-instance parallel inversion at ~3-10× over
   Fermat. Multi-day effort but novel territory & beats the existing
   0x05 path on per-inversion cost.

Day-1 trick (single sequential instance) carried zero leverage. Day-2
or later under approach (1) is the next ticket. We do not commit
0x0A as live — it would regress every consumer.

## Files touched (uncommitted, local)

- `~/git/lumbda/examples/cuda-fanout/cgbn-batch-worker.cu`
  — kernel + dispatch + family classification + cleanup
- `~/git/lumbda/examples/cuda-fanout/test_cgbn_known_answers.py`
  — driver + OPS registry entry + default-N sweep extended to 100k
- `~/git/lumbda/examples/cuda-fanout/plans/form-E-progress.md` — this doc

CATALOG.md & bend.html are NOT updated. Worker binaries on 3090-ai &
ai.foxhop.net rebuilt with the new op but **the live `:9091` /
`:9092` daemons remained pointed at the prior binary** until restart;
we did not restart them, so production traffic still uses the 9-op
build. Restart would expose the new op without harming existing ops
(0x01..0x09 untouched), but per the halt rule we do not promote.

## Recommended next step

Open form-E Day-2 ticket: rewrite `mod_inv_batch_256_kernel` as
per-block parallel scan (warp-shuffle reduce within block of 256
or 128 instances, cross-block sequential cleanup). Expected to clear
the 5× threshold at n=100k since Phase 1/3 chain depth drops from
100,000 to ~log2(B) + (100k / B). Reuse the same wire shape and
test harness — both are correct. Only the kernel changes.
