# cuda-fanout — reference CUDA primitive for lumbda

A reference implementation of "fan out a workload across CUDA cores"
as a primitive usable from any lumbda tier (Python, C, asm) without
linking the CUDA toolchain into lumbda's core build.

License: **AGPLv3** (matches lumbda).

## Why this shape

Lumbda's strength is tier portability: the same Scheme source runs
byte-identically across Python / C / asm implementations. Direct
libcudart linkage breaks this — the asm tier has no libc, the C tier
gains a hard dependency, and Python's path-of-least-resistance
(cupy / pycuda) doesn't match the other tiers' wire format.

Instead, this primitive is structured as a **leaf binary that every
tier spawns via its existing process-spawn primitive**:

```
            ┌───────── lumbda Python tier ─────────┐
            │ (cuda-shake-fanout '("00" "01") 32)  │
            │      ↓ subprocess.run                │
            │ shake256-fanout in.portal out.portal │
            └──────────────────────────────────────┘

            ┌───────── lumbda C tier ──────────────┐
            │ (cuda-shake-fanout ...)              │
            │      ↓ fork + execve                 │
            │ shake256-fanout in.portal out.portal │
            └──────────────────────────────────────┘

            ┌───────── lumbda asm tier ────────────┐
            │ (cuda-shake-fanout ...)              │
            │      ↓ syscall fork + execve         │
            │ shake256-fanout in.portal out.portal │
            └──────────────────────────────────────┘
```

Every tier inherits the GPU work without touching its build
dependencies. The CUDA toolchain stays isolated to this directory.

## Wire contract

**Input portal** (caller writes):
```
(cuda-shake-fanout
  (output-bytes 32)
  (inputs
    "deadbeef"
    "00ff00ff"
    ...))
```

**Output portal** (binary writes):
```
(cuda-shake-fanout-result
  (n 2)
  (output-bytes 32)
  (hashes
    "abc..."
    "def...")
  (timing-ms (load 0.4) (launch 0.1) (kernel 12.7) (write 0.3)))
```

The wire format is plain S-expressions so any tier's portal reader
already handles it (see `c/portal.c`, `lumbda.py` portal helpers,
`asm/portal.s`).

## What's in the box

| file | role |
|------|------|
| `shake256-fanout.cu` | CUDA kernel + host driver. Self-contained, no external EC math, just SHAKE256 fan-out. |
| `Makefile`           | nvcc build + `make test` + `make bench` |
| `test_roundtrip.py`  | validates output matches `hashlib.shake_256` (host reference) |
| `bench.py`           | timing comparison: Python `hashlib` host loop vs CUDA fan-out at N = 1k / 10k / 100k |
| `lumbda-call.lsp`    | reference Scheme wrapper showing how lumbda would expose this as `(cuda-shake-fanout inputs out-bytes)` once each tier registers it |

## Pure-lumbda end-to-end (Python tier today)

Once `spawn-process-stdio` + `flush-port` land in lumbda's primitive
dispatch (they're in `lumbda.py` as of the cuda-fanout commit), the
full bend round-trip runs in pure Scheme — no Python mock worker
needed:

```bash
# In one shell, run the pure-Scheme gpu-worker:
cd examples/cuda-fanout
python3 -u ../../lumbda.py /tmp/launch-worker.lsp
  # → gpu-worker: ready cuda-shake-fanout ← ./shake256-fanout
  # → gpu-worker listening on port 8320 (BEND mnemonic — see below)

# In another shell, drive via bend!:
python3 ../../lumbda.py smoke-bend.lsp
  # === smoke-bend ===
  # 1. cost estimator picks local for 3 inputs (cost too small): OK
  # 2. worker available? #t
  # 3. bend! (cuda-shake-fanout '("00" "01" "deadbeef") 32):
  #    ("b8d01df8…" "94da6280…" "fa094fa8…")
  # All three hashes byte-identical to hashlib.shake_256.
```

Note `python3 -u` for the worker — lumbda's Python tier inherits
Python's default stdout buffering, which masks the "ready" /
"listening" status lines until the process exits. `-u` makes them
appear live. (Adding an explicit `flush-port` after the listening
print would fix this in the Scheme without needing `-u`.)

## Asm tier — `spawn-process-stdio` + `flush-port` now landed

The asm tier got both primitives in commit `4f03c48`:

```scheme
λ> (display (spawn-process-stdio "/bin/echo" (quote ("hi"))))
(#<port> . #<port>)
λ> (flush-port (car (spawn-process-stdio "/bin/true" (quote ()))))
;; (returns void)
```

Implementation: hand-written `pipe2 + fork + dup2 + execve` syscall
sequence (~200 LoC asm). `flush-port` is a no-op on asm tier because
ports are raw fds with no userspace buffering. See the commit message
for the stack-layout & critical `%r15`-is-the-heap-pointer note.

What works on asm today:

- `(load "wire.lsp")` — same wire protocol everywhere
- `(load "bend.lsp")` — function form (`bend-call`, `bend!-call`)
- `(bend!-call '(cuda-shake-fanout ("00" "01") 32))` over TCP to a
  Python or C worker

What doesn't:

- `(load "bend-macros.lsp")` — needs `define-syntax` (only on Python/C)
- `(load "gpu-worker.lsp")` — needs `spawn-process-stdio`

The asm tier remains a useful **client** for the bend pattern. Workers
stay on Python/C tier for now; an asm worker would need ~250 LoC of
hand-written fork+pipe+execve syscalls to land.

## How lumbda's core would integrate this

Three things, each ~20 lines per tier:

1. **Stable primitive name & dispatch entry**: `(cuda-shake-fanout
   inputs out-bytes)` in each tier's primitive table.
2. **Host detection**: at startup, check whether the binary exists
   at a known path (e.g. `~/.local/bin/cuda-shake-fanout` or
   `LUMBDA_CUDA_FANOUT_BIN`); if not, the primitive raises a clean
   `cuda-not-available` error.
3. **The Scheme wrapper** in `lumbda-call.lsp` (or equivalent inlined
   per tier).

No tier needs nvcc to build. No tier needs libcudart at runtime. The
GPU stays an opt-in capability per host.

## Generalizing past SHAKE256

`shake256-fanout` is a deliberately narrow example because SHAKE256 is
small, well-known, and easy to validate against `hashlib.shake_256`.
The same pattern extends to any embarrassingly-parallel CUDA workload
the lumbda ecosystem wants — propose new primitives per-workload:

- `cuda-shake-fanout`   — N hashes (this binary)
- `cuda-keccakp-fanout` — N raw Keccak permutations (future)
- `cuda-poly1305-fanout` — N MACs (future)

Each one ships as its own leaf binary; each one registers under its
own primitive name; each one is independently AGPLv3 alongside the
rest of the repo.

## Build & smoke test

```bash
make all                            # compile via nvcc
make test                           # round-trip vs hashlib.shake_256
make bench                          # device vs host timing grid
python3 bench_daemon.py ./shake256-fanout  # daemon vs per-spawn
```

## Measured performance — where the GPU actually wins (and loses)

**Setup:** RTX 3090 (10,496 CUDA cores, sm_86) + i9-12900K host,
Python `hashlib.shake_256` as the reference.

### Per-spawn mode — kernel-launch overhead dominates

For SHAKE256 specifically, the per-process CUDA context init eats
~200 ms regardless of workload. The actual kernel is 0.1–40 ms
depending on size. So the GPU loses to host hashlib at every size
we tested in per-spawn mode:

```
in_sz       N         total     host ms    dev ms    kernel ms    speedup
32          10,000    320 KB         6        282       0.12       0.02×
32          100,000   3.2 MB        60        322       0.24       0.19×
32          1,000,000 32 MB        606       1570       1.14       0.39×
32          3,000,000 96 MB       1818       4246       3.04       0.43×
1024        1,000     1 MB           3        239       0.25       0.01×
1024        100,000   102 MB       260       4753       1.72       0.05×
16384       10,000    164 MB       343      18638       2.66       0.02×
262144      1,000     262 MB       508     454171      39.07       0.00×
```

The 454 SECONDS at 262 MB is **portal parsing** of the 524 MB hex
text file — *not* the kernel (which is 39 ms). At the current
S-expression hex wire format, even our biggest kernels are dwarfed
by hex-string parsing.

**Conclusion: SHAKE256 alone is too light to amortize either init
overhead or hex parsing.** Host hashlib reads raw bytes and stays
unbeatable for this primitive.

### Daemon mode — 574× faster per-call

`shake256-fanout --daemon` keeps the CUDA context alive across many
requests. CUDA init pays once at startup; every subsequent call
is just kernel + I/O:

```
workload: 10 calls × 100 inputs × 32 bytes each

  host hashlib loop  :      0.6 ms total (0.06 ms/call)
  per-spawn fanout   :   1825.9 ms total (182.59 ms/call)
  daemon-mode init   :    109.2 ms  (one-time)
  daemon-mode calls  :      3.2 ms total (0.32 ms/call)

  daemon is 574× faster per call than per-spawn
  daemon end-to-end is 16× faster than per-spawn for 10 calls
```

The 574× factor is the actual win the `go-gpu` primitive should
inherit. Per-spawn mode is a debug tool; daemon mode is the
production architecture for workloads doing repeated fan-outs.

### Daemon protocol

```
shake256-fanout --daemon
  → reads commands on stdin, one per line:
    process <in.portal> <out.portal>     → fan-out, write result, "done <out>"
    quit                                 → clean shutdown, "bye"
  → response per command on stdout
```

This is exactly the interface a `(go-gpu …)` primitive in lumbda would
wrap: the per-tier dispatcher spawns one daemon per GPU host at boot,
then routes every `go-gpu` form's body through the existing daemon's
stdin. CUDA init never re-runs while lumbda is up.

### When the per-spawn mode IS the right tool

A few cases:
- **One-shot scripts** where init time doesn't matter
- **CI pipelines** that need fresh state per test
- **Debugging** with isolated CUDA contexts

In those cases the per-spawn binary is sufficient and the daemon is
overkill.

### Binary portal + daemon — GPU wins by 1.5–10×

Adding a length-prefixed binary input/output format (`--binary` flag
and `process-bin` daemon command) eliminates the hex-string parse
that was eating 99% of wall time at large workloads. With **both
binary format and daemon mode**, every cell of the bench grid flips
to a GPU win:

```
in_sz       N           total    host ms   dev ms  speedup
32          10,000      320 KB        5         1   5.45×
32          100,000     3.2 MB       47         5   9.95×
32          1,000,000   32 MB       470        47  10.11×
1024        100,000     102 MB      177        79   2.24×
16384       10,000      164 MB      231       124   1.86×
262144      1,000       262 MB      363       231   1.57×
```

Peak 10× at small-input × high-N. This is the natural shape of many
crypto protocols (commitments, Fiat-Shamir transforms, PoW search)
where each call hashes a small message but you make a lot of them.
The lumbda `(bend …)` primitive should default to binary format
under the hood; the S-expression layer is just the friendly client
contract.

Binary format wire (in):
```
u32 LE out_bytes
u32 LE n
for each i: u32 LE len_i | len_i bytes
```

Binary format wire (out):
```
u32 LE n | u32 LE out_bytes | n × out_bytes
```

### Workloads that genuinely shine on this architecture

SHAKE256 is too light. Workloads that actually win on GPU pour
compute into each thread:

- **Reversible bit-vector simulation** (our `ecdsa/cuda/sim_gpu.cu`
  does 12.8M ops × 2,295 threads = 30+ billion ops per kernel, 25 s
  on a 3090) — kernel dominates, init is noise.
- **Many-round Keccak / PBKDF2 / Argon2** at million-iteration counts.
- **Bulk EC scalar mul** (we used OpenMP for 13× win on CPU; on GPU
  the per-thread cost is the same but parallelism scales).

The `cuda-shake-fanout` example is intentionally small so the
build + test cycle is fast. The pattern (leaf binary + portal +
daemon) is the contribution.

## Provenance

Keccak permutation derived from FIPS 202 reference. The compact
distillation pattern (Markku-Juhani O. Saarinen's tiny-sha3, CC0 /
public domain) was the starting point and is re-licensed here under
AGPLv3 to align with lumbda. The first practical use was in
`~/git/www.foxhop.net/ecdsa/cuda/sim_gpu.cu` where on-device SHAKE
gave a 2.6× memory compression for batched reversible-circuit
simulation (writeup in `ecdsa/cuda/README.md`). This contribution
extracts the generic primitive from that workload-specific use.
